polski
Task Questions [A] (pyt)
Questions [A]
Memory limit: 32 MB
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.
Task
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.
Input
The first line of the input contains three integers 
, 
and 
,
separated by single spaces.
denotes the number of princes (numbered from 
to 
), 
- the number of variables (numbered from 
to 
),
- the number of actions.
You can assume that the following inequalities hold:
, 
, 
.
The following 
lines describe variables 
.
Each of these lines is of the form "
" (this notation contains single spaces),
where 
is one of characters 
, 
, 
, 
, 
, 
, 
and 
and 
are integers.
Depending on 
that occurs in the description of 
, different kinds of facts
about this variable are provided.
The meanings of the possible characters are described below:
=   |
 is an integer between  and  (inequality  holds then) |
+   |
 (in this case and all next ones  holds) |
-   |
 |
*  |
 |
/   |
 (integer part of the division) |
%   |
 (the remainder) |
>   |
 if  ;  in the opposite case |
This information is provided in the beginning of the game to all princes and also to the sorcerer.
The following 
lines describe the actions.
There can be following kinds of actions (the descriptions of actions contain single spaces):
- S
The value of 
was revealed to son number 
.
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).
The king asked son number 
whether he knew the value of 
.
He was answered YES and he passed this answer to the sorcerer
(Other sons will hear the answer only when action 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.)
Just like in the previous action, but the king received answer NO.
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 
.
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.
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.
The king told the sorcerer that variable 
has value 
.
The king asks the sorcerer what possible values - according to his current knowledge
- may 
have.
The king 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: 
,
, 
. Additionally, the number of all possibilities
(i.e. the product of values 
over all variables of type "
")
does not exceed 
.
In every theoretically possible valuation of variables, the absolute value of
each variables is not greater than
, and in case of operations "
" and "
"
is non-negative and 
is positive.
Variable 
may appear in the definition of 
only if 
.
Output
For every action of type Q, exactly one line should be written out, containing
a sequence of all possible values of 
, 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.
Example
For the input data:
| 3 7 16 | 3 princes, 7 variables, 16 actions |
| = 0 1 |  : crown colour of son 1 (0 = silver, 1 = golden) |
| = 0 1 |  : crown colour of son 2 |
| = 0 1 |  : crown colour of son 3 |
| + 1 2 |  |
| + 3 4 |  , what is in other words equal to the total number of golden crowns |
| = 3 3 |  |
| > 6 5 |  determines whether the number of golden crowns is less than 3 |
| S 1 7 | All sons know that there are less than 3 golden crowns. |
| S 2 7 | |
| S 3 7 | |
| M 1 7 | The sorcerer also knows that. |
| S 1 3 | Prince 1 can see the crown of prince 3. |
| S 2 3 | Prince 2 can see the crown of prince 3. |
| S 1 2 | Prince 1 can see the crown of prince 2. |
| X 3 3 | Does (according to the sorcerer) son 3 know his crown's colour? (no) |
| X 1 1 | Does (according to the sorcerer) son 1 know his crown's colour? (the sorcerer does not know that) |
| N 1 1 | Son 1 does not know his crown's colour. |
| A 0 0 | All sons are informed that 1 and 3 do not know their crown's colours. |
| N 2 2 | Son 2 answers that he still does not know his crown's colour. |
| X 3 3 | The sorcerer knows that son 3 still does not know his crown's colour (he did not hear 2's answer). |
| A 0 0 | |
| X 3 3 | Now son 3 knows. |
| Q 0 3 | The sorcerer also knows that prince 3 has crown of type 0. |
the correct result is:
NIE NIE WIEM NIE TAK 0
Task author: Eryk Kopczynski.