Mirko 最近买了一个幸运轮盘。他在轮盘的每个扇区上写了一个大写英文字母，就像这样（对应第三个样例）：

轮盘上的字母互不相同，且轮盘按顺时针方向旋转。在轮盘旋转时，有一个指针保持在固定位置（在上面的图片中，它指向 H）。当我们旋转轮盘时，指针所指向的字母也会相应地改变。

Mirko 连续旋转了轮盘 $K$ 次，每次他都记录下了指针指向的字母改变了多少次，以及旋转结束时指针指向的字母。

Slavko 找到了那张纸，现在想知道 Mirko 在轮盘的扇区上写了哪些字母。如果已知扇区的总数，请帮助他确定这些字母。

输入格式

输入的第一行包含整数 $N$（$2 \le N \le 25$），表示轮盘上的扇区数量，以及 $K$（$1 \le K \le 100$），表示旋转的次数。

接下来的 $K$ 行按顺序包含 Mirko 记录的每次旋转的描述。每行包含一个整数 $S$（$1 \le S \le 100$），表示在该次旋转期间指针指向的字母改变的次数，以及一个大写字母，表示旋转停止时指针指向的字母。

输出格式

如果不存在满足上述要求的轮盘，输出 !。

否则，输出轮盘上的字母序列，从最后一次旋转结束时指针指向的字母开始，按顺时针方向依次输出。如果某个扇区上的字母无法确定，则用 ? 代替。

样例

输入 1

3 3
1 A
2 B
3 C

输出 1

!

输入 2

5 6
1 A
2 B
5 B
1 C
2 A
2 B

输出 2

B?A?C

输入 3

8 8
4 V
3 I
7 T
7 A
6 R
5 N
1 O
9 H

输出 3

HONITAVR