Linesweeper

Juku의 컴퓨터 화면은 가로가 무한하지만 세로는 2 cm뿐이다. 이런 화면에서는 많은 컴퓨터 게임을 하기가 매우 불편하다. 모든 것을 아는 산타 할아버지가 Juku의 컴퓨터에 맞는 게임 몇 개를 가져다준다. 그중 하나가 Linesweeper다.

Linesweeper 게임판은 두 행과 무한한 개수의 열로 이루어진 표다. 열에는 정수 번호가 붙어 있다. 아래 행의 칸에는 지뢰가 있을 수 있지만, 지뢰의 위치는 알려져 있지 않다. 위 행의 각 칸에는 정수가 적혀 있는데, 이는 그 칸의 이웃 칸에 있는 지뢰의 개수다. 두 칸이 꼭짓점이나 변을 공유하면 두 칸은 이웃이다. 플레이어의 목표는 어느 칸에 지뢰가 있는지 찾는 것이다.

프로그램을 대충 짠 탓에 이 게임에는 이상한 버그가 몇 가지 있다.

• 첫 번째 게임의 위 행은 항상 모두 0이다.
• 게임마다 위 행은 직전 게임의 위 행과 정확히 한 칸만 다르다.
• 플레이어에게 보여 주는 위 행에 대응하는 아래 행이 실제로는 존재할 수 없는 경우가 있을 수 있다.

Juku는 이 게임을 꽤 잘한다. 대부분은 지뢰 위치를 스스로 알아내지만, 가끔은 힌트가 조금 필요하다. Juku는 항상 "$i$번 칸에 지뢰가 있나요?" 형태로 힌트를 요청한다. 이 질문에는 네 가지 답이 가능하다.

• 이 위 행에 대응하는 아래 행은 존재할 수 없다 (기호 !).
• 이 칸에 지뢰가 반드시 있음을 보일 수 있다 (기호 x).
• 이 칸에 지뢰가 반드시 없음을 보일 수 있다 (기호 o).
• 이 칸에는 지뢰가 있을 수도 있고 없을 수도 있다 (기호 ?).

힌트를 직접 주는 일은 번거로우니 프로그램이 대신하도록 하자.

형식적으로는 두 종류의 질의 $Q$개가 주어진다.

1. $i$와 $c$가 주어진다. Juku가 새 게임을 시작하는데, 이전 게임과 비교해 위 행의 $i$번째 칸에 적힌 수만 $c$로 바뀌어 있다.
2. $i$가 주어진다. Juku가 아래 행의 $i$번째 칸에 지뢰가 있는지 묻는다.

이 질의들에 답하는 프로그램을 작성하라.

첫 줄에 정수 $Q$ ($1 \le Q \le 2 \cdot 10^5$)가 주어진다.

이어서 $Q$개의 줄이 주어지며, 각 줄은 질의 하나를 나타낸다. 첫 번째 종류의 질의는 1 i c 형태 ($1 \le i \le 10^5$, $0 \le c \le 3$)이고, 두 번째 종류의 질의는 2 i 형태 ($1 \le i \le 10^5$)이다.

두 번째 종류의 질의마다 x, o, !, ? 중 하나의 기호를 한 줄에 출력한다.

첫 번째 예제에서 Juku는 다음 게임에서 처음으로 막힌다.

그림의 아래 행 배치가 유일하게 가능한 지뢰 배치임을 보일 수 있다.

세 번째 예제에서 Juku는 위 행이 모두 0인 첫 번째 게임에서부터 막힌다. 어떤 칸에도 지뢰가 있을 수 없는 것이 분명하므로, 44번 칸에도 지뢰가 없다.

같은 예제에서 Juku는 다음 게임에서도 막힌다. 이 게임의 게임판은 3번 칸에 적힌 수가 이제 1이라는 점만 이전 게임과 다르다.

이 위 행에 대응하는 아래 행은 존재할 수 없다. 3번 칸의 이웃 중 어느 한 곳에라도 지뢰가 있다면, 2번 칸이나 4번 칸에 0이 아닌 수가 적혀 있어야 하기 때문이다. Juku는 이 게임에서 두 번 힌트를 요청하며, 두 답은 모두 !다.

두 게임 뒤 그는 다시 막힌다. 게임판은 다음과 같다.

이번에도 아래 행의 배치가 유일하게 가능한 배치임을 보일 수 있다. 따라서 3번 칸에는 지뢰가 반드시 있고, 91191번 칸에는 지뢰가 반드시 없다.

두 번째 예제에서는 두 번째 종류의 질의 뒤에 첫 번째 종류의 질의가 나오므로, 이 테스트는 첫 번째 테스트 그룹에 나올 수 없다. 세 번째 예제에는 답이 !인 질의가 있으므로, 이 테스트는 첫 번째 테스트 그룹과 두 번째 테스트 그룹에 나올 수 없다.