Mirko has recently bought a wheel of fortune. He wrote an uppercase letter of the English alphabet onto each wedge. No letter appears twice on the wheel, and the wheel spins in the clockwise direction. There is a pointer that stays in the same place while the wheel is spinning. When we spin the wheel, the letter to which the pointer is pointing changes accordingly.

Mirko spun the wheel \(K\) times in a row, and each time he wrote down how many times the pointed letter changed, and what letter was pointed to at the end of that spin.

Slavko found that paper, and would like to know what letters Mirko wrote onto the wedges of the wheel. Help him determine this, if the total number of wedges is known.

The first line of input contains integers \(N\) (\(2 \le N \le 25\)), the number of wedges on the wheel, and \(K\) (\(1 \le K \le 100\)), the number of spins.

The following \(K\) lines contain the descriptions Mirko wrote down for each spin, in order. Each line contains an integer \(S\) (\(1 \le S \le 100\)), the number of times the pointed letter changed during that spin, and an uppercase letter at which the pointer stopped.

If there is no wheel that meets the requirements described, output ‘!’.
Otherwise, output sequence of letters written onto the wheel, starting from the pointed letter at the end
of the last spin and proceeding clockwise. If some letter can’t be determined, output ‘?’ instead.
\(7^{th}\) round, April \(9^{th}\), 2011

riseoj 작성

출처 COCI 2010/2011 Contest 7