행운의 바퀴

• 그냥 반대로 시뮬레이션하면 되는 문제이긴 한데 구현이 좀 까다롭다 (그리고 문제를 이해하는것도 좀 까다롭다)
• n개의 칸을 ?로 초기화한 다음, 바퀴가 마지막에 가리킨 문자를 첫번째 칸에 적고 거꾸로 시뮬레이션하면서 문자들을 칸에 채워나가면 된다. 그러다가 이미 채워진 칸을 다른 문자로 채워야 하는 경우가 생기거나, 다 채우고 났을때 ?가 아닌 글자가 중복되어서 등장하게 된다면 “!”를 출력하고 나머지 경우에는 칸을에 채워진 알파벳들을 출력하면 된다,
• 시간복잡도는 O(n)

"""Solution code for "BOJ 2840. 행운의 바퀴".

- Problem link: https://www.acmicpc.net/problem/2840
- Solution link: http://www.teferi.net/ps/problems/boj/2840
"""


def main():
    N, K = [int(x) for x in input().split()]
    turns = [input().split() for _ in range(K)]

    pos = 0
    wheel = ['?'] * N
    for S, ch in reversed(turns):
        if wheel[pos] not in (ch, '?'):
            answer = '!'
            break
        wheel[pos] = ch
        pos = (pos + int(S)) % N
    else:
        alphabets = [x for x in wheel if x != '?']        
        answer = (''.join(wheel)
                  if len(set(alphabets)) == len(alphabets) else '!')
    print(answer)


if __name__ == '__main__':
    main()