Problem Description

Mirko recently purchased a wheel of fortune. He wrote a capital English letter on each segment, like this (for example, sample $3$):

There are no duplicate letters, and the wheel rotates clockwise.

When the wheel spins, a pointer remains stationary (pointing to H in the figure). As we spin the wheel, the letter pointed to by the arrow changes accordingly.

Mirko spun the wheel $k$ times consecutively, recording how many times the pointed letter changed each time and the letter the pointer stopped at.

Slavko found the paper and wants to know what Mirko wrote on the segments of the wheel. Additionally, the total number of segments is known.

Input Format

The input consists of $k+1$ lines.

The first line contains two positive integers $n$, the number of segments on the wheel, and $k$, the number of spins.

The next $k$ lines represent the sequence of descriptions recorded by Mirko for each spin. Each line contains an integer $s$ and a capital letter $c$, indicating the number of times the pointed letter changed during that spin, and $c$ is the capital letter where the pointer stopped.

Output Format

If there is no wheel that satisfies the above requirements, output !.

Otherwise, output the letters on the wheel, starting from the letter where the pointer stopped after the last spin, and output them in a clockwise direction. If some letters cannot be determined, output ? in their place.

Sample Input and Output

Sample Input #1

3 3
1 A
2 B
3 C

Sample Output #1

!

Sample Input #2

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

Sample Output #2

B?A?C

Sample Input #3

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

Sample Output #3

HONITAVR

Notes

Data Size and Constraints

For $100\%$ of the data, $2 \le n \le 25, 1 \le k \le 100, 1 \le s \le 100$.

Notes

This problem is worth $50$ points.

Translated from COCI2010-2011 CONTEST #7 T2 KOLO

见题面 Input 部分

见题面 Output 部分