伊朗哈兹菲杯（Iranian Hazfi Cup）是每年举办一次的淘汰赛制足球赛事；即每场比赛的输家立即被淘汰，赢家晋级下一轮。每年有 $2^k$ 支球队参加该赛事（其中 $k$ 为正整数）。所有球队都在第一轮开始比赛，每轮结束后，当前仍在参赛的球队中有一半会被淘汰。第 $k$ 轮为决赛，两支球队争夺冠军。总共进行 $2^k - 1$ 场比赛。

哈兹菲杯的对阵表是在抽签仪式上在特邀嘉宾的见证下提前确定的。它决定了哪些球队在第一轮中交锋，以及如果它们晋级到后续轮次，可能会遇到哪些其他球队。具体来说，在抽签仪式上，所有 $2^k$ 支球队被随机分配到第一轮的 $1, 2, \dots, 2^k$ 号位置，如 $k = 3$ 时的图所示。

伊朗足球协会必须开始筹备 2023 年哈兹菲杯。由于许多特邀嘉宾今年可能会拒绝出席抽签仪式，协会决定使用与 2022 年哈兹菲杯相同的对阵表。不幸的是，去年的对阵表已经找不到了，但去年赛事的所有比赛结果都以任意顺序保存了下来。可以证明，从这些比赛结果中可以唯一确定对阵表。你的任务是从 2022 年哈兹菲杯的比赛结果中恢复对阵表，以便回答今年球迷们常问的以下问题：

• 在哪一轮中，两支球队 A 和 B 可能会交锋？

输入格式

输入的第一行包含两个空格分隔的整数 $k$ 和 $n$，其中 $k$ 表示比赛的轮数（$1 \le k \le 10$），$n$ 表示球迷提问的数量（$1 \le n \le 1000$）。

接下来的 $2^k - 1$ 行包含 2022 年哈兹菲杯的比赛结果，每行一个结果，顺序任意。每个比赛结果的格式如下：

• teamA gA - gB teamB

其中 teamA 和 teamB 是不同的、非空的、由小写英文字母组成的字符串，长度最多为 100，而 $g_A$ 和 $g_B$ 分别表示 teamA 和 teamB 射入的进球数（$g_A \ne g_B$）。如果平局，则通过点球大战决定胜者，比赛结果的格式如下：

• teamA g(pA) - g(pB) teamB

其中 $g$ 是两队在常规比赛中射入的进球数，而 $p_A$ 和 $p_B$ 分别是 teamA 和 teamB 在点球大战中的进球数（$p_A \ne p_B$）。所有进球数（即 $g_A$、$g_B$、$g$、$p_A$ 和 $p_B$）均为小于 100 的非负整数。请注意，输入中表示比赛结果的每一行都恰好包含 4 个空格字符。

输入以 $n$ 个查询结束。每个查询占独立的一行，包含两个不同的球队名称，由一个空格字符分隔。

输出格式

对于输入中的每个查询，在输出中独立的一行打印一个整数作为答案。

样例

输入样例 1

2 3
perspolis 1(4) - 1(3) esteghlal
sepahan 0 - 2 perspolis
esteghlal 4(1) - 4(0) shamoshak
shamoshak sepahan
shamoshak perspolis
esteghlal shamoshak

输出样例 1

2
2
1