問題文

TTPC (Tottemo Tanoshii Programming Contest) は、2015 年に 1 回目が開催され、その後 A 年ごと (A は正の整数) に開催されるコンテストです。

より正確には、TTPC は 2015 + A \times n (n は非負整数) と表すことができる年に開催され、それ以外の年には開催されません。

また、TTPC は、2015 年の他にも X 年と Y 年に開催されることが分かっています。

このとき、A としてあり得る整数を 昇順に 全て出力してください。

制約

• X, Y は整数
• 2015 < X < Y \leq 10^{12}

入力例 1

2019 2023

出力例 1

1
2
4

例えば A = 4 の場合、2019 = 2015 + A \times 1, 2023 = 2015 + A \times 2 と表せます。

A=1, A=2 の場合でも同様に表すことができ、逆に、それ以外の数を A にした場合では表せません。

入力例 2

999999999995 1000000000000

出力例 2

1
5

制約に注意してください。

入力例 3

2019 2022

出力例 3

1

Tokyo Tech Programming Contest は 2015 年、2019 年、2022 年 に開催されました。

問題文

あなたは X 円が入った魔法の財布を持っています。

この財布に魔法を使うと、あなたは財布に入っている金額を 10 進の文字列と見て任意に並び替えることができます。 例えば、120 円が入った魔法の財布に魔法を使うと、入っている金額を 12 円、 21 円、 102 円、 120 円、 201 円、 210 円のいずれかに変えることができます(先頭の 0 は無視されます)。

あなたはこれから魔法の財布を持って N 個のお店を順番に訪れます。 i 番目のお店 (1 ≤ i ≤ N) では A_i 円の商品が 1 つ売っており、もし魔法の財布に A_i 円以上入っていれば、魔法の財布から A_i 円を支払ってその商品を買うことができます。

魔法は好きなときに好きなだけ使うことができます。あなたは最大で商品をいくつ買うことができますか？

制約

• 入力はすべて整数
• 1 \le N \le 100
• 1 \le X < 10^4
• 1 \le A_i < 10^4 (1 ≤ i ≤ N)

入力例 1

2 120
142 90

出力例 1

2

最初のお店に行く前に魔法を使って所持金を 120 円から 201 円に変えると、商品を買うことができます。またこのとき魔法の財布には 59 円が残るので、さらに魔法を使って財布の中身を 95 円に変えると次のお店でも商品を買うことができます。 最初に財布の中身を 210 円にすると最初のお店で商品を買えますが、財布の中身が 68 円となり次のお店で商品を買うことができません。

入力例 2

1 119
911

出力例 2

1

X 円を上回る商品を購入できる場合があることに注意してください。

入力例 3

5 1000
900 90 900 9 900

出力例 3

3

0 で始まるように並べ替えることもできます。

入力例 4

7 1171
6328 2419 8302 7503 1744 8495 1522

出力例 4

5

問題文

長さ N の整数列 A = (A_1, \dots, A_N), B = (B_1, \dots, B_N), C = (C_1, \dots, C_N), D = (D_1, \dots, D_N), E = (E_1, \dots, E_N) が与えられます。

以下の値を 998244353 で割ったあまりを求めてください。

• \displaystyle\sum_{i=1}^{N}\sum_{j=1}^{N}\sum_{k=1}^{N}\sum_{l=1}^{N}\sum_{m=1}^{N}\mathrm{med}(A_i,B_j,C_k,D_l,E_m)

ただし、\mathrm{med}(a,b,c,d,e) は a,b,c,d,e の中央値を表します。

制約

• 入力はすべて整数
• 1 \le N \le 10^5
• 0 ≤ A_i, B_i, C_i, D_i, E_i < 998244353 (1 \le i \le N)

入力例 1

1
1
2
3
4
5

出力例 1

3

\mathrm{med}(1,2,3,4,5) = 3 なので答えは 3 です。

入力例 2

3
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2

出力例 2

486

問題文

頂点に 1, 2, \dots, N の番号が付いた、頂点 1 を根とする N 頂点の根付き木があります。i 番目の辺 (1 ≤ i ≤ N - 1) は頂点 U_i と頂点 V_i を結んでいます。

木の各頂点は白か黒で塗られており、頂点 i (1 ≤ i ≤ N) は A_i = 0 のとき白で、A_i = 1 のとき黒で塗られています。

木を黒くしたい黒木さんは、以下の操作を 0 回以上の任意の回数行って、黒で塗られている頂点の数を最大化します。

• 葉である頂点 x を 1 つ選び、根から x までのパスに含まれる頂点 (両端を含む) の色を反転させる (白で塗られている場合は黒に、黒で塗られている場合は白に塗り直す)。

黒木さんは何個の頂点が黒に塗られた木を得ることができるでしょうか？

制約

• 入力はすべて整数
• 2 \leq N \leq 10^5
• 0 \leq A_i \leq 1 (1 ≤ i ≤ N)
• 1 \leq U_i, V_i \leq N (1 ≤ i ≤ N - 1)
• 与えられるグラフは木である

入力例 1

5
1 0 0 1 0
1 2
1 3
3 4
3 5

出力例 1

5

以下のように操作をすると頂点をすべて黒で塗られた状態にすることができます。

1. 頂点 2 を選ぶ。これによって頂点 1 は白に、頂点 2 は黒になる。
2. 頂点 5 を選ぶ。これによって頂点 1 は黒に、頂点 3 は黒に、頂点 5 は黒になる。

入力例 2

6
1 1 0 0 1 0
3 1
2 5
1 2
4 1
2 6

出力例 2

5

入力例 3

9
1 0 1 0 1 0 1 0 1
2 9
1 2
6 9
3 8
4 5
5 9
2 8
7 8

出力例 3

6

問題文

大学 A と大学 B は統合することになりました。大学 A の大学名は A 、大学 B の大学名は B です。統合後の新しい大学名 C を考えましょう。具体的には、以下のようにして C を定めます。

• A の空でない部分列を 1 つとって a とする。
• B の空でない部分列を 1 つとって b とする。
• C を a と b をこの順で連結した文字列とする。

Q 個の文字列 S_1, S_2, \dots, S_Q が与えられます。それぞれの文字列が C としてあり得るかどうか判定し、あり得る場合は、|\text{len}(a) - \text{len}(b)| としてあり得る最小値を求めてください。( \text{len}(x) は x の長さを表す)

制約

• Q は整数である。
• 1 ≤ Q ≤ 10^6
• A, B, S_1, S_2, \dots, S_Q は英小文字・英大文字・空白からなる文字列である。
• 1 ≤ \text{len}(A), \text{len}(B) ≤ 10^5
• 2 ≤ \text{len}(S_i) ≤ 10^5 (1 ≤ i ≤ Q)
• \displaystyle\left(\sum_{i = 1}^Q\text{len}(S_i)\right) ≤ 2 \times 10^6

部分点

• Q ≤ 20 を満たすデータセットに正解すると 100 点が与えられる。

入力例 1

Tokyo Institute of Technology
Tokyo Medical and Dental University
10
The University
Tokyo University
kyoto University
Tokyo Tech
TMDU
Kyoto University
The University of Tokyo
Tokyo Technology and Medical and Dental University
   Tehnoooorsty
Tokyo

出力例 1

10
4
4
-1
2
-1
-1
-1
3
1

• S_1 = {}The University について、a = {}Th 、b = {}e University とすると、C = {}The University とできます。このとき、|\text{len}(a) - \text{len}(b)| = 10 となります。
• S_4 = {}Tokyo Tech について、b は空であってはいけないことに注意してください。
• 一般的な問題と異なり、空白も文字列の一部であることに注意してください。

問題文

整数列 L = (L_1, L_2, \dots, L_N) と R = (R_1, R_2, \dots, R_N) が与えられます。 以下の条件を満たす実数列 A = (A_1, A_2, \dots, A_N) が存在するか判定してください。

• 1 \leq i \leq N を満たすすべての整数 i に対して L_i \leq A_i \leq R_i が成り立つ。
• 2 \leq i \leq N-1 を満たすすべての整数 i に対して A_{i-1} + A_{i+1} \geq 2 A_i が成り立つ。

制約

• 入力はすべて整数
• 3 \leq N \leq 3 \times 10^5
• 1 \leq L_i \leq R_i \leq 10^9 (1 ≤ i ≤ N)

入力例 1

4
2 1 2 5
4 6 5 8

出力例 1

Yes

例えば A = (4, 1.5, 3, 7) が条件を満たします。

入力例 2

3
1 4 2
3 7 4

出力例 2

No

条件を満たす A は存在しません。

問題文

整数列 L = (L_1, L_2, \dots, L_N) と R = (R_1, R_2, \dots, R_N) が与えられます。 以下の条件を満たす整数列 A = (A_1, A_2, \dots, A_N) の個数を 998244353 で割ったあまりを求めてください。

• 1 \leq i \leq N を満たすすべての整数 i に対して L_i \leq A_i \leq R_i が成り立つ。
• ある整数 d が存在して、1 \leq i \leq N-1 を満たすすべての整数 i に対して A_{i+1} - A_i = d が成り立つ。

制約

• 入力はすべて整数
• 2 \leq N \leq 3 \times 10^5
• 1 \leq L_i \leq R_i \leq 10^{12} (1 \le i \le N)

部分点

以下の条件を満たすデータセットに正解した場合は 100 点が与えられる。

• 1 \leq L_i \leq R_i \leq 10^5 (1 \le i \le N)

入力例 1

3
5 5 2
7 6 7

出力例 1

6

例えば A = (7, 5, 3) が条件を満たします。

入力例 2

4
2 3 1 6
5 6 4 8

出力例 2

0

注意

この問題のメモリ制限は 256 MB です。

問題文

N 頂点 M 辺の有向グラフが与えられます。頂点には 1 から N の番号が、辺には 1 から M の番号がついています。辺 i (1 ≤ i ≤ M) は頂点 A_i から頂点 B_i に向かう辺です。

あなたは、このグラフの各頂点を色 1, …, N のいずれかで塗ります。ただし、頂点 i (1 ≤ i ≤ N) に塗る色を c_i としたとき、以下の条件を満たす必要があります。

• 任意の組 (i, j) (1 ≤ i < j ≤ N) について、c_i = c_j ならば、頂点 i から頂点 j へのパスか、頂点 j から頂点 i へのパスのいずれか (両方でもよい) が存在する。

\max\{c_1, …, c_N\} が最小になる塗り方を 1 つ構築してください。

制約

• 入力はすべて整数
• 1 ≤ N ≤ 7 \times 10^3
• 0 ≤ M ≤ 7 \times 10^3
• 1 ≤ A_i, B_i ≤ N (1 ≤ i ≤ M)
• A_i ≠ B_i (1 ≤ i ≤ M)
• (A_i, B_i) ≠ (A_j, B_j) (1 ≤ i < j ≤ M)

入力例 1

5 5
1 4
2 3
1 3
2 5
5 1

出力例 1

1 1 1 2 1

頂点 2 → 5 → 1 → 4 のパスがあるので、頂点 1, 2, 4, 5 を同じ色に塗ることができます。

頂点 3, 4 間にはパスが存在しないので、2 色以上は必要です。

入力例 2

5 7
1 2
2 1
4 3
5 1
5 4
4 1
4 5

出力例 2

2 2 1 1 1

入力例 3

8 6
6 1
3 4
3 6
2 3
4 1
6 4

出力例 3

4 4 4 4 3 4 2 1

問題文

整数 N,M,K と N 頂点 M 辺の無向グラフが与えられます。グラフの頂点には 1 から N の番号が、辺には 1 から M の番号が付けられています。辺 i (1 ≤ i ≤ M) は頂点 A_i と頂点 B_i の間をつないでいて、辺上には非負整数 C_i が置かれています。

Q 個のクエリが与えられます。i 番目 (1 ≤ i ≤ Q) のクエリでは、整数 D_{i} が与えられるので、次の条件を全て満たす整数の組 (u,v) の個数を求めてください。

• 1\le u\lt v\le N
• (C_{j} \oplus D_{i})\lt K を満たすような辺 j のみを通って、頂点 u から頂点 v まで移動することが可能

ただし \oplus はビット単位 \text{XOR} 演算を表します。

制約

• 入力は全て整数
• 2\le N\le 10^{5}
• 1\le M\le 10^{5}
• 0\le K\lt 2^{30}
• 1\le A_{i} \lt B_{i}\le N (1 ≤ i ≤ M)
• 0\le C_{i}\lt 2^{30} (1 ≤ i ≤ M)
• 1\le Q\le 10^{5}
• 0\le D_{i}\lt 2^{30} (1 ≤ i ≤ Q)

入力例 1

4 5 5
1 2 17
1 3 4
2 3 20
2 4 3
3 4 5
4
0
7
16
167

出力例 1

2
6
3
0

• 1 番目のクエリでは、辺 2,4 のみを通ることができます。
• 2 番目のクエリでは、辺 2,4,5 のみを通ることができます。
• 3 番目のクエリでは、辺 1,3 のみを通ることができます。
• 4 番目のクエリでは、どの辺も通ることができません。

入力例 2

9 13 488888932
2 7 771479959
3 8 783850182
5 7 430673756
6 8 350738034
4 9 400768807
2 3 83653266
1 2 829786563
5 8 357613791
7 9 579696618
3 7 423191200
3 5 867380255
1 9 907715012
6 9 1033650694
8
498260055
144262908
117665696
848664012
983408133
32610599
478007408
134182829

出力例 2

16
7
5
13
13
16
16
5

問題文

N 頂点 M 辺の有向グラフが与えられます。頂点には 1 から N の番号が、辺には 1 から M の番号が付けられていて、辺 i (1 ≤ i ≤ M) は頂点 A_i から頂点 B_i への辺です。このグラフに自己ループは存在するかもしれませんが、多重辺はありません。どの頂点からも辺が 1 本以上出ていることが保証されます。
頂点のうち K 個には宝石が置かれています。i 番目 (1 ≤ i ≤ K) の宝石は頂点 V_i にあり、価値は W_i です。

このグラフを使って First 君と Second 君がゲームをします。ゲーム開始時、First 君は頂点 F に、Second 君は頂点 S にいます。First 君から始めて、First 君と Second 君が交互に以下の操作を行います。

• 自分が今いる頂点から出ている辺を 1 つ選び、その辺に沿って次の頂点まで移動する。移動した頂点に宝石があればそれを手に入れ、その宝石はグラフ上から取り除かれる。

全ての宝石を取るか、ゲーム中にあった盤面と同じ盤面 (手番、各プレイヤーの位置、残っている宝石が全く同じ状態) が再び登場するとゲームは終了します。

お互いに、(自分の取る宝石の価値の合計) - (相手の取る宝石の価値の合計) ができるだけ大きくなるように行動するとき、ゲーム終了時の (First 君の取る宝石の価値の合計) - (Second 君の取る宝石の価値の合計) を求めてください。

制約

• 入力は全て整数
• 2 ≤ N ≤ 30
• 1 ≤ F, S ≤ N
• 1 ≤ A_i, B_i ≤ N (1 ≤ i ≤ M)
• (A_i, B_i) ≠ (A_j, B_j) (1 ≤ i < j ≤ M)
• どの x (1 \le x \le N) に対しても A_i = x なる i が存在する
• 1 ≤ K ≤ 10
• 1 ≤ V_1 < \dots < V_K ≤ N
• V_i \notin \{F, S\} (1 ≤ i ≤ K)
• 1 ≤ W_i ≤ 10^8 (1 ≤ i ≤ K)

入力例 1

5 16 1 1
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 2
3 4
3 5
4 2
4 3
4 5
5 2
5 3
5 4
4
2 4
3 84
4 38
5 96

出力例 1

46

どの頂点からでもどの宝石も取ることができます。ゲームは以下のように進行します。

• First 君が頂点 1 から頂点 5 に移動し、価値が 96 の宝石を得る。
• Second 君が頂点 1 から頂点 3 に移動し、価値が 84 の宝石を得る。
• First 君が頂点 5 から頂点 4 に移動し、価値が 38 の宝石を得る。
• Second 君が頂点 3 から頂点 2 に移動し、価値が 4 の宝石を得る。

したがって、答えは (96 + 38) - (84 + 4) = 46 です。

入力例 2

8 16 8 4
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 1
1 5
2 6
3 7
4 8
5 1
6 2
7 3
8 4
6
1 29
2 34
3 41
5 7
6 26
7 94

出力例 2

-23

入力例 3

5 5 2 1
1 1
2 3
3 4
4 5
5 2
2
4 1000000
5 100000

出力例 3

1100000

入力例 4

10 20 1 2
1 4
1 7
2 2
2 4
3 6
3 3
4 8
4 7
5 7
5 1
6 9
6 2
7 9
7 3
8 8
8 6
9 7
9 8
10 10
10 2
8
3 92067840
4 2874502
5 36253165
6 70758738
7 4768969
8 16029185
9 16207515
10 44912151

出力例 4

132484345

問題文

Alice と Bob と Chris はこれから N 回じゃんけんをします。 ただし、各々が出す手には次のような制限があります。

• Alice は グー をちょうど A_R 回、 パー をちょうど A_P 回、 チョキ をちょうど A_S 回 出す。
• Bob は グー をちょうど B_R 回、 パー をちょうど B_P 回、 チョキ をちょうど B_S 回 出す。
• Chris は グー をちょうど C_R 回、 パー をちょうど C_P 回、 チョキ をちょうど C_S 回 出す。

Alice と Bob と Chris はとても仲良しなので、 N 回すべてで あいこ になるようにしたいです。 N 回のじゃんけんにわたる 3 人の手の出し方であってこれを達成する方法の数を 998244353 で割ったあまりを求めてください。

制約

• 入力はすべて整数
• 1\le N\le 1.5\times 10^{6}
• 0\le A_R,A_P,A_S,B_R,B_P,B_S,C_R,C_P,C_S\le 1.5\times 10^{6}
• A_R+A_P+A_S=B_R+B_P+B_S=C_R+C_P+C_S=N

入力例 1

2
2 0 0 1 1 0 1 0 1

出力例 1

2

じゃんけんを 2 回行います。Alice は 2 回とも グー を出します。Bobが グー を出すときにChrisも グー を出せば 2 回ともあいこになります。Bobが 1 回目に グー を出すか 2 回目に グー を出すかの 2 通りが 2 回ともあいこになる方法として考えられます。

入力例 2

3
0 1 2 3 0 0 1 1 1

出力例 2

0

残念ながら、3 回すべてのじゃんけんであいこにすることはできません。

入力例 3

333333
111111 111111 111111 111111 111111 111111 111111 111111 111111

出力例 3

383902959

問題文

正整数 N,M が与えられます。

(0,1,...,NM-1) の順列 P=(P_{0},P_{1},...,P_{NM-1}) のうち、以下の条件を満たすものの個数を 998244353 で割ったあまりを求めてください。

• 0\le i\lt NM を満たす全ての整数 i について、 \left\lfloor \frac{i}{M} \right\rfloor \neq \left\lfloor \frac{P_{i}}{M}\right\rfloor が成り立つ。

ただし、 \left\lfloor X \right\rfloor は X 以下の最大の整数を表します。

制約

• 入力はすべて整数
• 2\le N \le 1000
• 1\le M \le 1000

入力例 1

2 2

出力例 1

4

条件を満たす順列は P=(2,3,0,1),(2,3,1,0),(3,2,0,1),(3,2,1,0) の 4 種類です。

例えば、 P=(3,0,1,2) は i=3 のとき、\left\lfloor \frac{3}{2} \right\rfloor = \left\lfloor \frac{2}{2}\right\rfloor=1 となるため、条件を満たしません。

入力例 2

5 1

出力例 2

44

M=1 のときは条件の式は i\neq P_{i} と同値になります。

入力例 3

167 91

出力例 3

284830080

問題文

正整数 N, M が与えられます。N 個の正整数の組 (x_1,x_2,\dots ,x_N) であって \displaystyle\prod_{i=1}^{N}x_i=M を満たすものすべての集合を \bm{X} とします。

\displaystyle\sum_{(x_1,x_2,\dots ,x_N)\in \bm{X}}\prod_{i=1}^{N} (x_i+A_i) を 998244353 で割ったあまりを求めてください。

制約

• 入力はすべて整数
• 1\le N\le 2\times 10^5
• 1\le M\le 10^{12}
• 0\le A_i\lt 998244353 (1\le i\le N)

入力例 1

2 3
0 1

出力例 1

10

x_1\times x_2=3 を満たす正整数の組 (x_1,x_2) は (1,3),(3,1) の 2 組存在します。これらに対する \prod_{i=1}^{N} (x_i+A_i) の値はそれぞれ (1+0)\times (3+1)=4,(3+0)\times (1+1)=6 なので、これらの和である 10 が答えになります。

入力例 2

5 1
0 1 2 3 4

出力例 2

120

x_1=x_2=x_3=x_4=x_5=1 に対する \prod_{i=1}^{N} (x_i+A_i) の値は (1+0)\times (1+1)\times (1+2)\times (1+3)\times (1+4)=120 です。

入力例 3

10 314159265358
0 1 2 3 4 5 6 7 8 9

出力例 3

658270849

問題文

整数 K と 3 次元上の N 個の点 (x_1,y_1,z_1), \dots, (x_N,y_N,z_N) が与えられます。

N 点 (K x_1,K y_1,K z_1), \dots, (K x_N,K y_N,K z_N) の凸包の内部または境界に含まれる点であって座標がすべて整数であるようなものの個数を 998244353 で割ったあまりを求めてください。

制約

• 入力はすべて整数
• 4 \leq N \leq 100
• 1 \leq K \leq 10^{15}
• \sout{-2 \times 10^3 \leq x_i,y_i,z_i \leq 2 \times 10^3} (1 ≤ i ≤ N)
• \color{red}-2 \times 10^2 \leq x_i,y_i,z_i \leq 2 \times 10^2 (1 ≤ i ≤ N)
• (x_i,y_i,z_i) \neq (x_j,y_j,z_j) (1 ≤ i < j ≤ N)
• N 個の点すべてを通る平面は存在しない

入力例 1

4 2
0 0 0
1 0 0
0 1 0
0 0 1

出力例 1

10

4 点 (0,0,0),(2,0,0),(0,2,0),(0,0,2) の凸包の内部と境界に含まれる座標が整数の点は (0,0,0),(1,0,0),(2,0,0),(0,1,0),(1,1,0),(0,2,0),(0,0,1),(1,0,1),(0,1,1),(0,0,2) の 10 個です。

入力例 2

4 10000
0 0 0
1 0 0
0 1 0
0 0 1

出力例 2

59878050

4 点 (0,0,0),(10000,0,0),(0,10000,0),(0,0,10000) の凸包に含まれる座標が整数の点は 166\,766\,685\,001 個なので、これを 998244353 で割ったあまりである 59878050 を出力します。

入力例 3

8 314159265358979
5 -3 -3
-5 -3 -3
0 5 -3
0 0 10
4 2 6
-4 2 6
0 -5 6
0 0 -5

出力例 3

152811018

簡単な問題文

謎のモノイド (M, \oplus) と、これを計算する CPU が 4 個あります。

整数 N が与えられるので、M の列 A = (A_1, A_2, …, A_N) から A の累積 \oplus を 4 並列で計算してください。
その際、操作回数を最小化してください。

厳密な問題文

整数 N が与えられます。以下の (独自言語の) プログラムを作成してください。その際、命令数を最小化してください。

プログラムの仕様

このプログラムでは、2004 個の変数 A[1], A[2], …, A[2000], C_1, C_2, C_3, C_4 を扱うことができる。各変数は整数列を 1 つ持つことができ、A[i] (1 ≤ i ≤ 2000) の初期値は A[i] = (i) である。
( (i) は i のみからなる整数列を表す。)

プログラムの実行終了時点で、以下の条件が満たされなければならない。

• i = 1, 2, …, N のそれぞれについて、A[i] = (1, 2, …, i) である。

プログラムの形式

プログラムの 1 行目にはプログラムの命令数を表す整数 L が書かれる。
プログラムの 2 行目から 4L+1 行目には L 個の命令が 4 行ずつ書かれる。命令は上から下に順次実行される。

命令は 12 個の整数 c_1, a_1, b_1, c_2, a_2, b_2, c_3, a_3, b_3, c_4, a_4, b_4で書かれる。各整数は 1 以上 2000 以下でなければならない。
各命令では以下の操作を順に行う。

1. C_1 に \text{concat}(A[a_1], A[b_1]) を代入する。
2. C_2 に \text{concat}(A[a_2], A[b_2]) を代入する。
3. C_3 に \text{concat}(A[a_3], A[b_3]) を代入する。
4. C_4 に \text{concat}(A[a_4], A[b_4]) を代入する。
5. A[c_1] に C_1 を代入する。
6. A[c_2] に C_2 を代入する。
7. A[c_3] に C_3 を代入する。
8. A[c_4] に C_4 を代入する。

ここで、\text{concat}(x, y) とは、整数列 x, y をこの順で連結した整数列を表す。

制約

• N は整数
• 2 ≤ N ≤ 10^3

部分点

• 2 ≤ N ≤ 16 を満たすデータセットに正解した場合は 200 点が与えられる。
• 17 ≤ N ≤ 10^3 を満たすデータセットに正解した場合は 300 点が与えられる。

入力例 1

2

出力例 1

1
2 1 2
2000 2000 2000
2000 2000 2000
2000 2000 2000

1 回目の命令で、A[2] は (1, 2) に、A[2000] は (2000, 2000) に変化します。

実行終了時点で A[1] = (1), A[2] = (1, 2) となっているので、これは仕様を満たすプログラムです。

入力例 2

4

出力例 2

2
2 1 2
4 3 4
2000 2000 2000
2000 2000 2000
3 2 3
4 2 4
2000 2000 2000
2000 2000 2000

1 回目の命令で、A[2] は (1, 2) に、A[4] は (3, 4) に、A[2000] は (2000, 2000) に変化します。
2 回目の命令で、A[3] は (1, 2, 3) に、A[4] は (1, 2, 3, 4) に、A[2000] は (2000, 2000, 2000, 2000) に変化します。

実行終了時点で A[1] = (1), A[2] = (1, 2), A[3] = (1, 2, 3), A[4] = (1, 2, 3, 4) となっているので、これは仕様を満たすプログラムです。