Hide

Problem J
Röknet

Languages en is

In every computer a logical network can be found. These networks are used to evaluate boolean expressions and thus create the basis for more complex calculations that the computer performs. Logical networks consist of different objects that can up to two inputs and up to one output. An object takes boolean values as inputs and outputs a boolean value. These objects can then be connected together such that the output of one object is piped into the input of another. The objects thus create a network that boolean expressions travel through.

In this problem we intend to consider five kinds of objects:

  • OG has two inputs, if both are true then the output is true, but is false otherwise.

  • EDA has two inputs, if both are false then the output is false, but is otherwise true.

  • EKKI has one input, if the input is true it outputs false and outputs false otherwise.

  • INNTAK has no input and one output. INNTAK is a special object that is used to always send the same value to the output.

  • UTTAK has one input and no output. UTTAK is a special object that is sued to check what value is sent to its input.

In the following image we see an example of a logical network:

\includegraphics[width=0.8\textwidth ]{network.png}
Figure 1: Image of sample one

Given a description of such a logical network, can you calculate what values will be input to the UTTAK objects?

Input

The first line of the input contains the positive integer $N$, denoting the number of objects in the logical network. Then there are $N$ lines, one for each object. There are five kinds of lines depending on the object in question:

  • INNTAK name value denotes an object of the type INNTAK with the name name which outputs the value value.

  • UTTAK input denotes an unnamed object of the type UTTAK. The input of the object is connected to the object with the name input.

  • OG input1 input2 name denotes an OG object with the name name. Its inputs are connected to the outputs of the objects with the names input1 and input2.

  • EDA input1 input2 name denotes an EDA object with the name nafn. Its inputs are connected to the outputs of the objects with the names input1 and input2.

  • EKKI input name denotes an EKKI object with the name name. The input is connected to the object with the name input.

The names of the objects are unique and consist of upper and lower case letters. If the output of object $A$ is connected to the input of object $B$, then $A$ will appear before object $B$ in the input.

Output

For each object of type UTTAK one line should be printed with the name of the object and the value it receives as input; SATT if it is true and OSATT if it is false. These lines should be in the same order as the objects are given in the input.

Scoring

The solution will be tested on differently hard input data and the data is divided into groups as shown in the table below. The solution will then be scored according to how many groups are solved.

Group

Points

Constraints

1

20

$N \leq 100$, All objects are of the type INNTAK or UTTAK

2

30

$N \leq 100$

3

50

$N \leq 10^4$

Sample Input 1 Sample Output 1
11
INNTAK 1 SATT
INNTAK 2 SATT
EKKI 2 3
OG 1 3 4
INNTAK 8 SATT
EDA 8 4 9
UTTAK 9
INNTAK 5 OSATT
EDA 4 5 6
EKKI 6 7
UTTAK 7
9 SATT
7 SATT
Sample Input 2 Sample Output 2
6
INNTAK banani SATT
UTTAK banani
INNTAK epli OSATT
UTTAK epli
UTTAK banani
INNTAK gurka SATT
banani SATT
epli OSATT
banani SATT