轮盘游戏

Grade 0 Open Time Saturday, 29 December 2012, 4:20 pm
Discount 0.8 Time Discount Saturday, 29 December 2012, 4:20 pm
Allow late Yes Close Time Saturday, 29 December 2012, 4:20 pm
Input file wheel.in Output file wheel.out

小x有一些字母轮盘,轮盘面被分成了N部分,每部分上被标记了一个大写英文字符。并且保证这个英文字符只会出现一次。这个轮盘只会顺指针转动,并且有一个指针会指向一个字符。

例如下图中的轮盘分成8部分,每部分都有一个大写英文字符,此时指针指向 ‘H’ 。

wheel

   

小x玩轮盘的过程是这样的:转动轮盘m次,每次他都会记录转动过程中指针指向的字符改变次数ci和轮盘停下后指针指向的字符chi

小x将这m次的结果记录在了一张纸上,你能不能根据纸上的记录,还原轮盘上面的字母?

【输入】

每个测试文件包含多组数据,每组数据格式如下:

首先第一行包含两个整数:N (2 ≤ N ≤ 25)和m (1≤ m ≤ 100),意义如题目描述。

接下来m行,每行一个整数,分别是ci和chi。意义如题目描述

 

【输出】

对于每组数据,输出相应的结果:

如果记录上的值有矛盾,输出‘!

如果记录上的值可以确定一轮盘,那么按顺时针方向依次输出轮盘的字符,第一个字符为最后一次显示的字符的值,如果某个字符无法确定,在不确定的字符位置输出‘?

 【输入输出样例】

wheel.in

wheel.out

3 3

1 A

2 B

3 C

5 6

1 A

2 B

5 B

1 C

2 A

2 B

8 8

4 V

3 I

7 T

7 A

6 R

5 N

1 O

9 H

!

B?A?C

HONITAVR

wheel

第三组数组所示的轮盘

【样例解释】

第三组数据表示的轮盘最终状态就是表格中右图所示

【数据范围】

每个测试文件保证测试数据不超过5组。