돌림판(KOLO)

창민이는 얼마전에 돌림 판을 샀다. 이 판에는 아래 그림과 같이 알파벳 대문자가 각 영역에 적혀있다.(입력 예3 을 그림으로 나타낸 것이다.)

돌림판에는 어떠한 문자도 두 번 이상 나오지 않으며 돌릴 때는 그림과 같이 시계방향으로 돌린다. 화살표는 항상 어느 한자리 고정되어 있으며 위 그림에서는 H 를 가리키고 있다.

이 상태에서 돌림판을 돌렸다고 가정하자. 돌림판이 돌아가면 화살표가 가리키는 문자가 바뀌게 된다. 4번 바뀐 후에 멈추었다면 화살표는 T를 가리킨다. 이 상태에서 돌림판을 또 다시 돌렸을 때 2번 바뀐 후에 멈추었다면 화살표는 N 을 가리킨다.

창민이가 한 번 돌릴 때마다 바뀐 문자수와 가리키는 문자를 공백으로 구분하여 한 줄에 입력받는다. 이러한 일을 K번 한 결과가 주어질때 돌림판의 문자를 출력하는 프로그램을 작성하시오. 맨 마지막에 화살표가 가리키는 문자를 시작으로 시계방향 순서대로 한 줄에 출력한다.

입력

첫 행에 돌림판의 문자수 N(2≤N≤25)과 실행횟수 K(1≤K≤100)가 공백으로 구분하여 입력된다.

이 후 K 행에 걸쳐 바뀐 문자수 S(1≤S≤100) 과 화살표가 가리키는 문자 C(C는 알파벳 대문자)가 공백으로 구분하여 입력된다.

출력

입력데이터로 돌림판의 문자를 만들수 없는 경우 ! 를 출력한다.

문자의 일부를 알 수 없는 경우 ? 로 대치하여 출력하며 마지막에 화살표가 가리키는 문자를 시작으로 시계방향 순서대로 한 줄에 출력한다.

예제1

예제2

예제3

태그

출처

COCI 2010/2011 contest#7

돌림판(KOLO) 1초 32MB