Description

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

No letter appears more than once on the wheel, and the wheel rotates clockwise along its rim.

While the wheel rotates, there is a pointer that stays in the same position (in the picture above it points to H). When we rotate the wheel, the letter pointed to by the pointer changes accordingly.

Mirko spun the wheel $k$ times in a row. Each time, he recorded how many times the pointed letter changed during the spin, and which letter the pointer was pointing to when the spin ended.

Slavko found that piece of paper. She wants to know what Mirko wrote on the sectors of the wheel. Also, the total number of sectors is known.

Input Format

The input has $k + 1$ lines.

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

The next $k$ lines describe, in order, what Mirko recorded for each spin. Each line contains an integer $s$ and a capital letter $c$, where $s$ is the number of times the pointed letter changed during that spin, and $c$ is the capital letter at which the pointer stopped.

Output Format

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

Otherwise, output the letters on the wheel starting from the letter under the pointer after the last spin ends, and then in clockwise order. If some letters cannot be determined, output ? in the corresponding positions.

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

Hint

Constraints

For $100\%$ of the testdata, $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.

Translated by ChatGPT 5