질문 | cho.sh

문제

옛날에 바이투르(Bytour) 왕은 세 아들을 위한 게임을 하나 만들어, 자신의 고문이자 마법사인 바이텔레안(Bytelean)에게 다음과 같이 설명했다.

"나는 세 아들(1, 2, 3번)을 한 줄로 세우고, 각자의 머리에 금관 또는 은관을 씌웠다. 1번 아들은 2번과 3번의 관을 볼 수 있었고, 2번 아들은 3번의 관을 볼 수 있었다. 세 아들은 모두 금관이 최대 두 개뿐이라는 사실을 알고 있었다. 먼저 1번 아들에게 자기 관의 색을 아느냐고 물으니 모른다고 답했다. 이어서 2번 아들에게 같은 질문을 하니 그 역시 모른다고 답했다."

이 순간 바이텔레안은 왕의 말을 끊고, 3번 왕자가 어떤 관을 받았는지 이미 알겠다고 말했다. 어떻게 알았느냐는 물음에 그는 이렇게 답했다.

"만약 1번 왕자가 금관 두 개를 보았다면, 자기 관이 은관임을 알았을 것입니다(금관은 최대 두 개이므로). 그런데 모른다고 답했으니 그런 경우는 있을 수 없습니다. 다음으로, 만약 2번 왕자가 3번의 머리에서 금관을 보았다면, 자기 관이 은관임을 알았을 것입니다. 그렇지 않았다면 1번 왕자가 안다고 답했을 것이기 때문입니다. 그런데 2번도 몰랐으니, 3번 왕자의 관은 반드시 은관입니다."

여러분의 과제는 이런 상황을 일반적으로 흉내 내는 시뮬레이터를 구현하는 것이다. 왕이 왕자들과 마법사에게 물어볼 수 있는 사실(이 이야기에서는 관의 색)은 여러 개의 변수로 표현된다. 어떤 변수는 앞선 변수들로부터 계산되고, 나머지 변수는 가질 수 있는 값의 범위만 주어진다. 정확한 형식은 입력 절에 설명되어 있다.

표준 입력으로 상황의 설명을 읽어들여, 마법사가 내놓아야 할 답을 계산하고, 그 결과를 표준 출력에 쓰는 프로그램을 작성하라.

입력

첫째 줄에는 공백 하나로 구분된 세 정수 $P$ , $V$ , $A$ 가 주어진다. $P$ 는 왕자의 수(1번부터 $P$ 번까지), $V$ 는 변수의 수(1번부터 $V$ 번까지), $A$ 는 행동(action)의 수이다. $1 \le P \le 10$ , $1 \le V \le 600$ , $1 \le A \le 600$ 을 만족한다.

이어지는 $V$ 개의 줄은 변수 $v_1, v_2, \ldots, v_V$ 를 설명한다. 각 줄은 Z A B 형식(공백 하나로 구분)이며, $Z$ 는 문자 =, +, -, *, /, %, > 중 하나이고 $A$ , $B$ 는 정수이다. $Z$ 에 따라 의미가 다르다.

줄	의미
`= A B`	$v_i$ 는 $A \le v_i \le B$ 인 정수이다(이때 $-10^6 \le A \le B \le 10^6$ ).
`+ A B`	$v_i = v_A + v_B$ (이 줄과 아래 모든 줄에서 $1 \le A, B < i$ ).
`- A B`	$v_i = v_A - v_B$ .
`* A B`	$v_i = v_A \cdot v_B$ .
`/ A B`	$v_i = v_A / v_B$ (나눗셈의 정수 부분).
`% A B`	$v_i = v_A \bmod v_B$ (나머지).
`> A B`	$v_A > v_B$ 이면 $v_i = 1$ , 아니면 $v_i = 0$ .

이 정보는 게임 시작 시 모든 왕자와 마법사에게 주어진다.

이어지는 $A$ 개의 줄은 행동을 설명한다(공백 하나로 구분).

S g n: $v_n$ 의 값이 왕자 $g$ 에게 공개된다. 이 값이 왕자 $g$ 에게 공개되었다는 사실은 모든 왕자와 마법사에게 알려지지만, 값 자체는 알려지지 않는다.
T g n: 왕이 왕자 $g$ 에게 $v_n$ 의 값을 아는지 묻는다. 답은 YES이고, 왕은 이를 마법사에게 전한다. 다른 왕자들은 A 행동이 수행될 때에만 이 답을 듣는다. 따라서 여러 왕자가 서로의 답에 영향을 받지 않고 "동시에" 답할 수 있다.
N g n: 위와 같지만 답이 NO이다.
X g n: 같은 질문을 하지만, 왕은 왕자의 답을 마법사에게 전하지 않고 대신 마법사에게 그 답을 추측하게 한다. 마법사는 YES, NO, 또는 모르겠음으로 답한다(모르겠음은 왕자 $g$ 가 답을 알았는지 마법사가 확신할 수 없다는 뜻이다). 이 행동에서 왕은 왕자 $g$ 의 실제 답을 마법사에게 알리지 않으며, 마법사의 추측도 왕자들에게 전하지 않는다. (마법사의 답은 출력 절에 따라 폴란드어로 출력한다.)
A 0 0: 모든 왕자는 직전 A 행동 이후 왕이 던진 모든 질문(T, N, X 행동)에 대해 다른 왕자들이 내놓은 답을 전달받는다. 이 행동에서 왕은 X 행동으로 받은 답을 마법사에게 알리지 않는다.
M w n: 왕이 마법사에게 변수 $v_n$ 의 값이 $w$ 라고 알려준다.
Q 0 n: 왕이 마법사에게, 현재 아는 것에 비추어 $v_n$ 이 가질 수 있는 값이 무엇인지 묻는다. 마법사의 답은 왕자들에게 전달되지 않는다.

왕자들과 마법사는 모두 완벽하게 추론한다. 즉, 매 순간 처음 주어진 범위와 지금까지 일어난 모든 일로부터 유도되는 모든 사실을 알아낼 수 있다. 또한 이들 각자는 모두가 완벽하게 추론한다는 것을 안다.

추가 보장: 가능한 값 배정의 수(= 유형인 모든 변수에 대한 $B_i - A_i + 1$ 의 곱)는 $600$ 을 넘지 않는다. 이론적으로 가능한 모든 값 배정에서 각 변수의 절댓값은 $10^6$ 이하이며, /와 % 연산에서는 $v_A$ 가 음이 아니고 $v_B$ 가 양수이다. 변수 $v_X$ 는 $X < Y$ 일 때에만 $v_Y$ 의 정의에 나타날 수 있다.

출력

각 X 행동에 대해, TAK(YES), NIE(NO), 또는 NIE WIEM(모르겠음) 중 하나를 담은 한 줄을 출력한다.

각 Q 행동에 대해, $v_n$ 이 가질 수 있는 모든 값을 가장 작은 것부터 가장 큰 것까지 공백 하나로 구분하여 한 줄에 출력한다.

출력하는 줄들은 대응하는 행동이 입력에 나타난 순서와 같은 순서로 출력해야 한다(행동의 종류와 무관하게).