Problem Description

There are $ N $ switches, each numbered as switch $ 1, 2, 3, ..., N $. Each switch has a state of either 0 or 1.

You can use $ M $ memories numbered $ N+1, N+2, ..., N+M $ to construct a circuit (the value of $ M $ is freely determined).

There are four types of memories, described below, with the corresponding memory number denoted as $ x $.

① AND Memory
Connected from two switches/memories, denoted as $ u, v $ $ (u < x, v < x) $. The value of memory $ x $ is 1 if the values of both switch/memory $ u $ and switch/memory $ v $ are 1; otherwise, it is 0.

② OR Memory
Connected from two switches/memories, denoted as $ u, v $ $ (u < x, v < x) $. The value of memory $ x $ is 1 if the value of either switch/memory $ u $ or switch/memory $ v $ is 1; otherwise, it is 0.

③ XOR Memory
Connected from two switches/memories, denoted as $ u, v $ $ (u < x, v < x) $. The value of memory $ x $ is 1 if exactly one of the values of switch/memory $ u $ or switch/memory $ v $ is 1; otherwise, it is 0.

④ NOT Memory
Connected from one switch/memory, denoted as $ u $ $ (u < x) $. The value of memory $ x $ is 1 if the value of switch/memory $ u $ is 0; otherwise, it is 0.

For example, consider the following circuit diagram:

For each state of the switches, the states of the memories are as shown in the table below:

Thus, only for the states {Switch1, Switch2, Switch3} = {$ 0, 1, 0 $}, {$ 1, 0, 0 $}, the value of Memory6 is $ 1 $.

Please solve the following two problems:

When T=1
There are $ 2^N $ possible states for the switches. Construct a circuit such that the value of memory $ N+M $ (or the switch if $ M=0 $) is 1 for exactly $ K $ of these states.

However, you must not use more than $ 2^{N}×4N $ memories.

When T=2
Construct a circuit such that the value of memory $ N+M $ (or the switch if $ M=0 $) is 1 only when the states of the switches are $ S_1, S_2, S_3, ..., S_K $.

However, you must not use more than $ 50,000 $ memories.

Input Format

The input is given from the standard input in the following format:

(☆) When $ T = 1 $

1 $ N $ $ K $

Here, $ N $ is the number of switches, and $ K $ is the number of states for which the value of memory $ N+M $ (or the switch if $ M=0 $) should be 1.

(★) When $ T = 2 $

2 $ N $ $ K $ $ S_1 $ $ S_2 $ $ S_3 $ $ : $ $ S_K $

Here, $ S_i $ represents the $ i $-th state among the $ K $ states for which the value of memory $ N+M $ (or the switch if $ M=0 $) should be 1.
$ S_i $ is represented as an $ N $-character string, where the $ i $-th character being 0 means the $ i $-th switch is 0, and 1 means the $ i $-th switch is 1.
For example, if $ N = 4 $ and $ S_i = $0101, it means the states where switches 2 and 4 are 1, and switches 1 and 3 are 0.

Output Format

Output the configuration of the logical circuit as follows:

$ M $ (information for memory $ N+1 $) (information for memory $ N+2 $) (information for memory $ N+3 $) $ : $ (information for memory $ N+M $)

The information for memory $ x $ should be output as follows:

For AND Memory

AND $ u $ $ v $

This indicates that memory $ x $ is connected from switch/memory $ u $ and switch/memory $ v $. $ u < x, v < x $ must be satisfied (though $ u = v $ is allowed).

For OR Memory

OR $ u $ $ v $

This indicates that memory $ x $ is connected from switch/memory $ u $ and switch/memory $ v $. $ u < x, v < x $ must be satisfied (though $ u = v $ is allowed).

For XOR Memory

XOR $ u $ $ v $

This indicates that memory $ x $ is connected from switch/memory $ u $ and switch/memory $ v $. $ u < x, v < x $ must be satisfied (though $ u = v $ is allowed).

For NOT Memory

NOT $ u $

This indicates that memory $ x $ is connected from switch/memory $ u $. $ u < x $ must be satisfied.

Sample Input and Output

Sample Input #1

1
3 2

Sample Output #1

3
XOR 1 2
NOT 3
AND 4 5

Sample Input #2

2
3 2
010
100

Sample Output #2

3
XOR 1 2
NOT 3
AND 4 5

Sample Input #3

1
5 24

Sample Output #3

1
OR 1 2

Sample Input #4

2
3 4
001
101
011
111

Sample Output #4

0

Notes/Hints

Constraints

• $1 \leq T \leq 2$
• $2 \leq N \leq 10$
• $1 \leq K \leq 2^{N}-1$
• $ T, N, K $ are integers

Subtasks and Scoring

This problem has two subtasks:

1. (30 points) $ T = 1 $.
2. (70 points) $ T = 2 $.

For Subtask 1, the score for each test case is determined as follows, with the minimum score across all test cases being the score for this subtask:

• $ 0 $ points if $ 2^{N}×4N < M $.
• $ 10 $ points if $2^{N}×2 < M \leq 2^{N}×4N$.
• $ 16 $ points if $N^2 < M \leq 2^{N}×2$.
• $ 23 $ points if $N-1 < M \leq N^2$.
• Full $ 30 $ points if $M \leq N-1$.

For Subtask 2, let $ L_2 $ be the maximum value of $ M $ across all test cases. The score for this subtask is determined as follows:

• $ 0 $ points if $50,001 \leq L_2$.
• $ 15 $ points if $4,201 \leq L_2 \leq 50,000$.
• $ 18 $ points if $3,101 \leq L_2 \leq 4,200$.
• $ 21 $ points if $2,101 \leq L_2 \leq 3,100$.
• $ 25 $ points if $1,601 \leq L_2 \leq 2,100$.
• $ 29 $ points if $1,201 \leq L_2 \leq 1,600$.
• $ 35 $ points if $751 \leq L_2 \leq 1,200$.
• $floor(70 - \frac{L_2 - 500}{8})$ points if $501 \leq L_2 \leq 750$.
• Full $ 70 $ points if $L_2 \leq 500$.

Sample Explanation 1

For this output, with $ N = 2 $ and $ M = 3 $, since $ M $ is between $ N $ and $ N^2 $, it scores $ 23 $ points.

见题面 Input 部分

见题面 Output 部分