Wheel of Fortune

Mirko recently bought a wheel of fortune with n sectors. He wrote a unique uppercase English letter on each sector, arranged in clockwise order. A fixed pointer is positioned at a particular place on the rim. When the wheel rotates, the pointer indicates different letters. Mirko spun the wheel k times. In each spin he recorded two pieces of information: the number of letter changes (i.e. the number of sectors the pointer passed) denoted by \(p_i\), and the letter at which the pointer stopped at the end of that spin.

Given the total number of sectors \(n\) and the record of spins, your task is to reconstruct the letters on the wheel. The answer should be given as the configuration of letters in clockwise order starting from the pointer's final position. If there is any inconsistency with a valid configuration, output an exclamation mark "!" instead. For sectors whose letter cannot be uniquely determined, output a question mark "?".

inputFormat

The first line contains two integers \(n\) and \(k\) (with \(1 \le n \le 26\) and \(1 \le k \le 100\)), representing the total number of sectors on the wheel and the number of spins respectively.

Each of the following \(k\) lines contains an integer \(p\) and an uppercase letter. The integer \(p\) indicates how many sectors the pointer passed (in a clockwise direction) during that spin, and the letter is the sector which the pointer points to after the spin.

outputFormat

Output a single string representing the arrangement of letters on the wheel, starting from the pointer's final position and proceeding in clockwise order. For any sector whose letter is not determined, output a '?' in its place. If the spins are inconsistent with any valid configuration, output "!".

sample

3 3
1 A
2 B
3 C

!