题目描述

Mirko 最近购买了一个命运之轮。 他在每个扇形上写了一个大写英文字母，像这样（比如样例 $3$）：

轮中没有字母重复出现，而且轮沿顺时针方向旋转。

轮旋转时，有一个指针停留在同一位置（上图中指向 H）。 当我们旋转盘时，指针所指向的字母相应地发生变化。

Mirko 连续旋转了 $k$ 次，每次都记录了箭头指向的字母改变了多少次，以及旋转结束时所指的字母。

Slavko 找到了那张纸，她想知道 Mirko 在车轮的扇形上写了些什么。另外，扇形的总数是已知的。

输入格式

输入数据共 $k+1$ 行。

第一行，$2$ 个正整数 $n$，表示车轮上的楔子数，以及 $k$，表示旋转数。

接下来 $k$ 行表示 Mirko 为每次旋转记录的顺序描述。 每行包含一个整数 $s$ 和一个大写字母 $c$，表示该旋转期间指向的字母发生更改的次数，$c$ 表示指针停止处的大写字母。

输出格式

如果没有满足上述要求的盘，则输出 $\texttt !$。

否则，盘上的字母，从最后一次旋转结束时的尖头字母开始，然后顺时针方向输出。如果无法确定某些字母，则在对应的位置输出 $\texttt ?$。

3 3
1 A
2 B
3 C

!

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

B?A?C

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

HONITAVR

提示

数据规模及约定

对于 $100\%$ 的数据，$2 \le n \le 25, 1 \le k \le 100, 1 \le s \le 100$。

说明

本题满分 $50$ 分。

译自 COCI2010-2011 CONTEST #7 T2 KOLO