P6703 [COCI 2010/2011 #7] KOLO

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.

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.

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.

#### 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](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #7](https://hsin.hr/coci/archive/2010_2011/contest7_tasks.pdf) T2 KOLO. Translated by ChatGPT 5