配点: $100$ 点

問題文

$N$ 個のスイッチがあり，それぞれスイッチ $1, 2, 3, ..., N$ と番号付けられています．各スイッチは，0 か 1 のいずれか二通りの状態を持ちます．

さて，あなたは番号 $N+1, N+2, ..., N+M$ がついた $M$ 個のメモリを使って，回路を作ることができます．（$M$ の値は自由に決められます．）

メモリには，以下の $4$ 種類があります．以下の説明では，該当するメモリの番号を $x$ としています．

① AND メモリ
2 つのスイッチ/メモリから繋がっており，これらを番号 $u, v$ $(u < x, v < x)$ とします．番号 $x$ のメモリの値は，番号 $u$ がついたスイッチ/メモリの値・番号 $v$ がついたスイッチ/メモリの値が両方 1 であれば 1 となり，そうでなければ 0 となります．

② OR メモリ
2 つのスイッチ/メモリから繋がっており，これらを番号 $u, v$ $(u < x, v < x)$ とします．番号 $x$ のメモリの値は，番号 $u$ がついたスイッチ/メモリの値・番号 $v$ がついたスイッチ/メモリの値のうち片方でも 1 であれば 1 となり，そうでなければ 0 となります．

③ XOR メモリ
2 つのスイッチ/メモリから繋がっており，これらを番号 $u, v$ $(u < x, v < x)$ とします．番号 $x$ のメモリの値は，番号 $u$ がついたスイッチ/メモリの値・番号 $v$ がついたスイッチ/メモリの値のうち一つだけが 1 であれば 1 となり，そうでなければ 0 となります．

④ NOT メモリ
1 つのスイッチ/メモリから繋がっており，これを番号 $u (u < x)$ とします．番号 $x$ のメモリの値は，番号 $u$ がついたスイッチ/メモリの値が 0 であれば 1 となり，そうでなければ 0 となります．

例えば，以下の図のような回路を考えます．

この回路の場合，それぞれのスイッチの状態について各メモリの状態は，以下の表のようになります．

スイッチ1

スイッチ2

スイッチ3

メモリ4

メモリ5

メモリ6

0

0

0

0

1

0

0

0

1

0

0

0

0

1

0

1

1

1

0

1

1

1

0

0

1

0

0

1

1

1

1

0

1

1

0

0

1

1

0

0

1

0

1

1

1

0

0

0

そのため，{スイッチ1, スイッチ2, スイッチ3} の状態が {$0, 1, 0$}, {$1, 0, 0$} の 2 通りに限り，メモリ6 の値が $1$ となります．

それについて，以下の 2 つの問題を解いてください．

T=1 のとき
スイッチの状態は $2^N$ 通りありますが，そのうちちょうど $K$ 通りについて，番号 $N+M$ のメモリ（$M=0$ の場合はスイッチ）の値が $1$ となるような回路を一つ構成してください．

ただし，$2^{N}×4N$ 個を超えるメモリを使ってはいけません．

T = 2 のとき
スイッチの状態が $S_1, S_2, S_3, ..., S_K$ であるときに限り，番号 $N+M$ のメモリ（$M=0$ の場合はスイッチ）の値が $1$ となるような回路を一つ構成してください．

ただし，$50 \\ 000$ 個を超えるメモリを使ってはいけません．

制約

• $1 \\leq T \\leq 2$
• $2 \\leq N \\leq 10$
• $1 \\leq K \\leq 2^{N}-1$
• $T, N, K$ は整数

小課題・得点

この問題には，$2$ つの小課題があります．

1. (30 点) $T = 1$．
2. (70 点) $T = 2$．

小課題 1 において，各テストケースに対して以下のように得点が定められます．この小課題の全部のテストケースに対する最低得点がこの小課題の得点となります．

• $2^{N}×4N < M$ のとき，$0$ 点．
• $2^{N}×2 < M \\leq 2^{N}×4N$ のとき，$10$ 点．
• $N^2 < M \\leq 2^{N}×2$ のとき，$16$ 点．
• $N-1 < M \\leq N^2$ のとき，$23$ 点．
• $M \\leq N-1$ のとき，$30$ 点満点．

次に，小課題 2 において，すべてのテストケースにおける $M$ の最大値を $L_2$ としたとき，この小課題の得点は以下のようになります．

• $50 \\ 001 \\leq L_2$ のとき，$0$ 点．
• $4 \\ 201 \\leq L_2 \\leq 50 \\ 000$ のとき，$15$ 点．
• $3 \\ 101 \\leq L_2 \\leq 4 \\ 200$ のとき，$18$ 点．
• $2 \\ 101 \\leq L_2 \\leq 3 \\ 100$ のとき，$21$ 点．
• $1 \\ 601 \\leq L_2 \\leq 2 \\ 100$ のとき，$25$ 点．
• $1 \\ 201 \\leq L_2 \\leq 1 \\ 600$ のとき，$29$ 点．
• $751 \\leq L_2 \\leq 1 \\ 200$ のとき，$35$ 点．
• $501 \\leq L_2 \\leq 750$ のとき，$floor(70 - \\frac{L_2 - 500}{8})$ 点．
• $L_2 \\leq 500$ のとき，$70$ 点満点．

---

入力

入力は以下の形式で標準入力から与えられます．

(☆) $T = 1$ のとき

1 $N$ $K$

ただし，$N$ はスイッチの個数，$K$ は番号 $N+M$ のスイッチ（$M=0$ の場合メモリ）の値が 1 であるべき状態の通り数を意味します．

(★) $T = 2$ のとき

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

ここでは，$S_i$ は番号 $N+M$ のスイッチ ($M=0$ の場合メモリ) の値が 1 であるべき状態のうち，$i$ 番目のものです．
$S_i$ は $N$ 文字の文字列で表され，$i$ 文字目が 0 である場合は $i$ 番目のスイッチの状態が 0 である，$i$ 文字目が 1 である場合は $i$ 番目のスイッチの状態が 1 であることを意味します．
例えば，$N = 4$ で $S_i =$ 0101 の場合，スイッチ $2, 4$ が 1 であり，スイッチ $1, 3$ が 0 であるような状態のことを表します．

出力

以下のように，論理回路の構成方法を出力してください．

$M$ (番号 $N+1$ のメモリの情報) (番号 $N+2$ のメモリの情報) (番号 $N+3$ のメモリの情報) $:$ (番号 $N+M$ のメモリの情報)

番号 $x$ のメモリの情報は，以下のように出力してください．

AND メモリの場合

AND $u$ $v$

これは，番号 $u$ と $v$ のスイッチ/メモリから，番号 $x$ のメモリに繋がっていることを表します．$u < x, v < x$ を満たさなければなりません．（ただし $u = v$ でも構わない）

OR メモリの場合

OR $u$ $v$

これは，番号 $u$ と $v$ のスイッチ/メモリから，番号 $x$ のメモリに繋がっていることを表します．$u < x, v < x$ を満たさなければなりません．（ただし $u = v$ でも構わない）

XOR メモリの場合

XOR $u$ $v$

これは，番号 $u$ と $v$ のスイッチ/メモリから，番号 $x$ のメモリに繋がっていることを表します．$u < x, v < x$ を満たさなければなりません．（ただし $u = v$ でも構わない）

NOT メモリの場合

NOT $u$

これは，番号 $u$ のスイッチ/メモリから，番号 $x$ のメモリに繋がっていることを表します．$u < x$ を満たさなければなりません．

---

入力例 1

1
3 2

出力例 1

3
XOR 1 2
NOT 3
AND 4 5

この出力の場合，$N = 2$ に対して $M = 3$ であり，$N$ 以上 $N^2$ 以下なので $23$ 点となります．

---

入力例 2

2
3 2
010
100

出力例 2

3
XOR 1 2
NOT 3
AND 4 5

---

入力例 3

1
5 24

出力例 3

1
OR 1 2

---

入力例 4

2
3 4
001
101
011
111

出力例 4

0