RXD and logic gates

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 524288/524288 K (Java/Others)

Description

ioXDR is a master in logic circuits. One day he comes up with a special logic gate.
It requires 3 input bits $a, b, c$. It would then make $c = c ~xor~ (a ~and~b)$ and remain $a$ and $b$ unchanged, where $and$ means bitwise and and $xor$ means bitwise exclusive or.
ioXDR has a boolean function $f(x_1,x_2, \dots, x_m)$, where $x_i \in \{0, 1\}$ and $f(x_1,x_2, \dots x_m) \in \{0, 1\}$.
He wants to design a circuit and could simulate the boolean function.
He has $m$ input bits, and $1$ output bit, and some extra bits. The number of extra bits and the initial value of extra bits could be determined freely. The initial value of output bit could also be set freely.
**This problem is judged by SPJ, so any valid answer could be accepted**
$m\leq 8$

Input

For each test case, the first line consists of an integer $m$, corresponding to the number of input bits.
For the next $2^m$ lines, there is a string with the length of $m$, which only consists of 01, and an integer $\in \{0, 1\}$, which describes the boolean function.
There are 50 test cases.

Output

For each test case, the first line you need to output an $0,1$ integer, which means the initial value of the output bit.
The next line you need to output an integer $t$, which means the number of the extra bits.
The next $t$ lines, in each line you have to output an 01 integer to describe the initial value of extra bits.
**The input bits are labeled as 1 ~ m, the output bit is labeled as m + 1, the extra bits are labeled as m + 2 ~ m + t + 1**
The next line you need to ouput an integer $n$, which means the number of logic gates.
The next $n$ lines, in each line you have to give us $3$ **different** integers $1\leq a, b, c\leq m + t + 1$, which means one logic gate.
**The simulator would simulate from top to bottom**
You have to guarantee that $n, t\leq 800$

Sample Input

1
0 1
1 0

Sample Output

1
1
1
1
1 3 2

liuyiding

Source

2017 Multi-University Training Contest - Te