시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|

1 초 | 128 MB | 0 | 0 | 0 | 0.000% |

One day king Bytour invented a game for his sons. He described the game to his counsellor, sorcerer Bytelean, in the following way:

*I ordered my three sons (numbered with integers 1, 2, 3) to stand in a row and I placed a golden or a silver crown upon the head of each of them. Son number 1 could then see crowns of sons 2 and 3 and son number 2 saw the the third son's crown. Each of the sons knew that there were at most two golden crowns in total. After that I asked son number 1, if he knew his crown's colour. He answered that he did not know. After that I asked son number 2, if he knew his crown's colour. He also answered that he did not know.*

At this moment Bytelean interrupted Bytour and told that he already knew what crown prince 3 received. Bytour asked him, how did he know that. He answered in the following way:

*If prince 1 saw two golden crowns, then he would know that he received a silver one (because there are at most two golden crowns). He answered NO, so this situation could not take place. Now if prince 2 saw a golden crown on third prince's head, then he would know that he received a silver one - in the opposite case prince 1 would answer YES. So he did not know that. So it is sure that prince 3 has a silver crown.*

Your task is to implement a (quite) general simulator of such situations. Facts, about which the king can ask the princes and the sorcerer (in the preceding situation it was the crown's type) are encoded as a sequence of *variables*. Some of them are somehow related to the previous variables and for the remaining ones only the ranges of their value are known. A more detailed description of the issue that is to be solved is contained in section *Input*.

Write a program that:

- reads a description of a situation from the standard input,
- computes the answers that the sorcerer should give,
- writes the result to the standard output.

The first line of the input contains three integers *P*, *V* and *A*, separated by single spaces. *P* denotes the number of princes (numbered from 1 to *P*), *V* - the number of variables (numbered from 1 to *V*), *A* - the number of actions. You can assume that the following inequalities hold: 1 ≤ *P* ≤ 10, 1 ≤ *V* ≤ 600, 1 ≤ *A* ≤ 600.

The following *V* lines describe variables *v*_{1}, *v*_{2}, ..., *v _{V}*. Each of these lines is of the form "

*Z*_{i} *A*_{i} *B*_{i}

" (this notation contains single spaces), where `=`

, `+`

, `-`

, `*`

, `/`

, `%`

, `>`

and `= A` |
v is an integer between _{i}A and _{i}B (inequality -1 000 000 ≤ _{i}A ≤ _{i}B ≤ 1 000 000 holds then)_{i} |

`+ A` |
v = _{i}v + _{Ai}v (in this case and all next ones 1 ≤ _{Bi}A, _{i}B < _{i}i holds) |

`- A` |
v = _{i}v - _{Ai}v_{Bi} |

`* A` |
v = _{i}v * _{Ai}v_{Bi} |

`/ A` |
v = _{i}v / _{Ai}v (integer part of the division)_{Bi} |

`% A` |
v = _{i}v mod _{Ai}v (the remainder)_{Bi} |

`> A` |
v = 1 if _{i}v > _{Ai}v; _{Bi}v = 0 in the opposite case_{i} |

This information is provided in the beginning of the game to all princes and also to the sorcerer.

The following *A* lines describe the actions. There can be following kinds of actions (the descriptions of actions contain single spaces):

`S g n`

The value of

*v*was revealed to son number_{n}*g*. The fact of revelation of this value to the son was revealed to all princes and to the sorcerer (this does not mean that they were provided with the value itself).`T g n`

The king asked son number

*g*whether he knew the value of*v*. He was answered YES and he passed this answer to the sorcerer (Other sons will hear the answer only when action_{n}`A`

is performed - thanks to this a few of them can answer questions `simultaneously' and the answers of some of them will not be used by others.)`N g n`

Just like in the previous action, but the king received answer NO.

`X g n`

Just like in the previous action, but the king did not pass the answer to the sorcerer, but asked him to guess the answer. The sorcerer answers YES, NO or I DON'T KNOW (the answer I DON'T KNOW means that the sorcerer is not sure whether the son knew the answer to the king's question). During this action the king

*does not inform*the sorcerer about the actual answer of prince*g*. The king also*does not pass*the sorcerer's answer to the princes.WARNING! The sorcerer's answers are sent to the standard output in Polish.

`A 0 0`

All son's are provided with answers of all other sons to all previously asked king's questions (answers given during actions

`T`

,`N`

and`X`

). In this action the king also*does not inform*the sorcerer about the answers that he received in actions of type`X`

.`M w n`

The king told the sorcerer that variable

*v*has value_{n}*w*.`Q 0 n`

The king asks the sorcerer what possible values - according to his current knowledge - may

*v*have. The king_{n}*does not pass*the sorcerer's answer to the princes.

It should be assumed that both the princes and the sorcerer perform perfect reasoning, meaning that at every moment they are able to deduce all facts that are implied by limitations revealed by the king in the beginning of the game and by what has happened in the game so far. Additionally, each of them knows that all of them perform perfect reasoning.

**Limitations:** The following limitations hold: 1 ≤ *P* ≤ 10, 1 ≤ *V* ≤ 600, 1 ≤ *A* ≤ 600. Additionally, the number of all possibilities (i.e. the product of values *B _{i}* -

`-`

") does not exceed 600. In every theoretically possible valuation of variables, the absolute value of each variables is not greater than 1 000 000, and in case of operations "`/`

" and "`%`

" For every action of type `Q`

, exactly one line should be written out, containing a sequence of all possible values of *v _{n}*, from the smallest one to the greatest one, separated by single spaces. For every action of type

`X`

, one line containing `TAK`

(meaning YES), `NIE`

(meaning NO) or `NIE WIEM`

(meaning I DON'T KNOW) should be written out. The answers should be written to the output in the order of appearance of actions (in the input) that they apply to; the order is independent from the types of these actions.3 7 16 = 0 1 = 0 1 = 0 1 + 1 2 + 3 4 = 3 3 > 6 5 S 1 7 S 2 7 S 3 7 M 1 7 S 1 3 S 2 3 S 1 2 X 3 3 X 1 1 N 1 1 A 0 0 N 2 2 X 3 3 A 0 0 X 3 3 Q 0 3

NIE NIE WIEM NIE TAK 0

Contest > Algorithmic Engagements > PA 2008 5-3번