問題文

衛藤君は後期から京都大学で対面授業を受けます。

前期はオンライン講義のみであったため、衛藤君は大学の構造に慣れていません。

そこであらかじめ教室の移動にかかる時間を見積もろうと考えています。

N個の教室の座標が与えられます。i 番目の教室の座標は (x_i,y_i) です。

はじめ 1 番目の教室にいるとして、順番に N 番目の教室まで移動するときの移動距離の総和を求めてください。

ただし、座標 (a,b) から座標 (c,d) までの移動距離は |a-c|+|b-d| です。

制約

• 1 \leq N \leq 100
• -100 \leq x_i, y_i \leq 100 (1 \leq i \leq N)
• 入力は全て整数である。

入力例 1

3
1 2
2 3
4 6

出力例 1

7

1 番目と 2 番目の教室の距離は |1-2|+|2-3|=2 であり 2 番目の教室と 3 番目の教室の距離は |2-4|+|3-6|=5 となるので、移動距離の総和は 2+5=7 です。

入力例 2

1
0 0

出力例 2

0

教室がひとつしかないため、移動する必要はありません。

入力例 3

4
-2 3
1 4
5 2
4 -2

出力例 3

15

問題文

1 から N までの番号が付けられた N 枚の紙があり、それぞれの紙には整数が K 個ずつ書かれています。

i 番目の紙に書いてある整数は v_{i,1}, v_{i,2}, \ldots v_{i,K} です。

それぞれの紙から独立に 1 つずつ整数を選び、i 番目の紙から選んだ整数が i 項目になるような数列を作ることを考えます。

このような数列の作り方はK^N通りありますが、そのうち広義単調増加なものは何通りでしょうか？答えは非常に大きくなる可能性があるため、10^9+7 で割ったあまりを求めてください。

ただし、数列 A=(a_1, a_2, \ldots , a_N) が広義単調増加であるとは、全ての i (1 \leq i \leq N-1) に対して a_i \leq a_{i+1} が成り立つことをいいます。

制約

• 1 \leq N \leq 100
• 1 \leq K \leq 10000
• 1 \leq v_{i,1} < v_{i,2} < \cdots < v_{i,K} \leq 10^9 (1 \le i \le N)
• 入力はすべて整数である。

入力例 1

2 2
2 4
1 5

出力例 1

2

ありえる数列は以下の 4 つです。

• (2,1)
• (2,5)
• (4,1)
• (4,5)

このうち広義単調増加なものは (2,5) と (4,5) であるため、答えは 2 です。

入力例 2

2 3
4 5 6
1 2 3

出力例 2

0

どのように整数を選んでも広義単調増加にできない場合もあります。

入力例 3

20 20
2 8 12 17 19 29 41 53 57 62 63 65 67 70 71 74 76 77 96 100
2 3 9 13 15 16 20 26 28 33 38 39 46 51 58 59 74 92 93 99
2 5 6 9 19 20 22 24 26 35 41 45 56 60 62 74 76 81 83 96
3 7 10 11 13 15 17 20 22 26 34 35 43 59 68 78 82 83 85 93
1 7 11 14 17 26 37 41 45 49 62 63 64 67 71 74 88 89 91 94
12 15 17 19 22 24 28 29 31 46 50 51 55 59 64 65 74 79 91 95
7 11 17 22 23 27 29 33 37 39 45 50 51 52 62 67 69 71 85 90
9 11 12 18 22 30 40 41 43 49 51 59 62 71 74 94 95 96 99 100
15 17 21 23 24 28 33 39 44 45 48 52 54 59 72 76 88 89 99 100
1 6 12 13 14 21 25 37 48 49 56 57 71 72 77 79 83 85 93 98
10 20 22 25 34 45 49 52 58 60 62 67 69 74 75 77 81 84 96 97
6 7 23 36 41 43 45 46 50 51 52 57 58 61 73 74 85 87 94 97
4 20 26 36 37 41 44 45 47 51 56 57 72 73 74 79 86 91 97 98
8 10 17 24 25 29 31 32 34 46 53 57 60 71 74 78 79 80 90 91
12 15 16 17 27 32 33 35 41 51 55 56 58 67 69 71 74 89 90 91
4 13 17 24 25 27 39 40 43 48 51 54 61 62 63 68 72 76 87 90
8 10 12 18 22 37 40 43 46 50 51 58 59 65 74 85 86 89 96 98
1 9 16 17 19 34 37 50 54 55 57 58 59 69 72 76 77 84 92 99
3 10 11 12 13 17 24 28 36 39 45 49 50 58 74 78 79 80 84 93
5 15 16 20 22 24 29 41 44 55 56 60 62 63 68 73 85 86 93 100

出力例 3

188926982

10^9+7 で割った余りを出力するように注意してください．

問題文

これは output-only 問題です。入力は与えられません。

すいばかくんはグリッドと部分文字列が大好きです。 あなたは英小文字が書き込まれた正方形のグリッドをすいばかくんにプレゼントしようとしています。 すいばかくんは几帳面なので、プレゼントされたグリッドに対して以下の作業を行います。

• グリッドの一辺の長さを N とし、i 行 j 列目に書かれた英小文字を c_{i, j} で表す。
• 全ての i, j, p (1 \leq i, j \leq N, j+1 \leq p \leq N) に対し, c_{i, j}, c_{i, j+1}, \ldots, c_{i, p} をこの順に並べてできる文字列を紙に書き出す。
• 全ての i, j, q (1 \leq i, j \leq N, i+1 \leq q \leq N) に対し, c_{i, j}, c_{i+1, j}, \ldots, c_{q, j} をこの順に並べてできる文字列を紙に書き出す。

以上の作業の後、紙には N^2 (N-1) 個の文字列が書かれています。 これらの文字列に重複する文字列が存在する場合、すいばかくんは悲しみ、溶けてしまいます。

あなたはすいばかくんを悲しませずにできるだけ大きなグリッドをプレゼントしたいです。 そのようなグリッドを一つ出力してください。

部分点

• 出力したグリッドから得られる文字列に重複する文字列が存在しない場合 Accepted と判定され、グリッド一辺の長さを N として \min(200, \max(20 N - 60, 0)) 点が与えられる。
• そうでない場合、Wrong Answer と表示され、点数は与えられない。
• システムの都合上、Accepted で X 点を獲得した場合、それまでに提出した Accepted な解法のうち X 点 未満のものは全て誤答としてカウントされ、ペナルティが発生するので注意すること。

問題文

長さが 1,3,5,7,...,2N-1 の棒がそれぞれ 1 本ずつ、合計 N 本の棒があります。

あなたは棒売りから、店で売るために棒を接着剤で繋げて棒の長さを揃えるよう頼まれました。

接着後に 2 本以上の棒が残り、接着後に残る全ての棒の長さが等しくなるような棒の接着方法を一つ出力してください。

そのような接着方法が存在しない場合はimpossibleを出力してください。

ただし複数の棒を接着するとき、接着後の棒の長さは接着に使用した棒の長さの和になり、棒を捨てることや切断することはできません。

制約

• 入力は全て整数である。
• 2 \leq N \leq 10^5

入力例 1

4

出力例 1

2
2 1 7
2 3 5

長さ 1,3,5,7 の棒を 1, 7 と 3, 5 に分けてそれぞれ接着すると、長さ 8 の棒が 2 つ得られ、これは条件を満たします。

入力例 2

2

出力例 2

impossible

長さ 1 と長さ 3 の 2 本をどのように接着しても、同じ長さの 2 本以上の棒になりません。

入力例 3

3

出力例 3

impossible

長さ 1,3,5 の 3 本しかない場合も条件を満たす接着方法が存在しません。

問題文

-10^9 以上 10^9 以下の整数からなる、長さ N の数列 A=(a_0,...,a_{N-1}),B=(b_0,...,b_{N-1}),C=(c_0,...,c_{N-1}) が与えられます。

いま、数列 A をいくつかの連続する部分列に分割することを考えています。 分割とは、以下の 3 条件を満たす整数列 D=(d_0,...,d_r) によって表されます。

• d_0=0
• d_r=N
• d_i < d_{i+1} (0 \leq i < r)

すなわち、各 i について [d_i,d_{i+1}) が連続する区間を表しており、数列全体がこの r 個の区間の和集合になっています。

分割 D に対してスコアを返す関数 f を次で定義します。

分割をうまく選んだときの、f の最大値を求めてください。

制約

• 入力はすべて整数である。
• 1 \leq N \leq 2 \times 10^5
• -10^9 \leq a_i,b_i,c_i \leq 10^9(0 \leq i < N)

入力例 1

2
1 -1
-1 4
1 -2

出力例 1

1

D=(0,2) のとき、スコアは b_0+c_1+a_0+a_1=-3 となります。

D=(0,1,2) のとき、スコアは \min(b_0+c_0+a_0,b_1+c_1+a_1)=\min(1,1)=1 となります。

入力例 2

1
1000000000
1000000000
1000000000

出力例 2

3000000000

オーバーフローに注意してください。

入力例 3

11
-323225375 -897098227 -795978453 501188072 409939326 -362890219 969123048 962633819 252457646 694824070 -406990840
-696821643 -663750226 -570551722 670541392 172964990 399404695 -305728788 -157617655 -801518744 -328729631 -160335217
-465411342 -660775657 515997870 -34787742 628368976 84800619 -728713779 573207953 115652694 -686953578 -215986240

出力例 3

91174984

問題文

頂点が H 行 W 列に並んだグリッドグラフがあります。

上から i 番目、左から j 番目 (1 \le i \le H, 1 \le j \le W) の頂点を (i, j) と表します。

広義単調増加 な正整数列 A, B, C, D があり、それぞれの長さは H-1, W, H, W-1 です。

頂点 (i, j) と頂点 (i+1, j) は、重みが A_i + B_j である無向辺で結ばれています。(1 \le i \le H-1, 1 \le j \le W)

頂点 (i, j) と頂点 (i, j+1) は、重みが C_i + D_j である無向辺で結ばれています。(1 \le i \le H, 1 \le j \le W-1)

これら以外の辺は存在しません。

このグラフの最小全域木に含まれる辺の重みの和を求めてください。

制約

• 2 \le H \le 10^5
• 2 \le W \le 10^5
• 1 \le A_i \le 10^6 (1 \le i \le H-1)
• 1 \le B_j \le 10^6 (1 \le j \le W)
• 1 \le C_i \le 10^6 (1 \le i \le H)
• 1 \le D_j \le 10^6 (1 \le j \le W-1)
• A_i \le A_{i+1} (1 \le i \le H-2)
• B_j \le B_{j+1} (1 \le j \le W-1)
• C_i \le C_{i+1} (1 \le i \le H-1)
• D_j \le D_{j+1} (1 \le j \le W-2)

入力例 1

2 3
1
1 3 6
1 4
1 2

出力例 1

17

与えられたグラフは上の図のようになります。

このグラフの最小全域木に含まれる辺の重みの和は 17 です。

入力例 2

4 3
1 13 15
3 6 11
3 6 6 11
9 17

出力例 2

173

問題文

タプリスちゃんは数列が好きです。

タプリスちゃんは現在、長さ 1 の数列 A = (1) を持っています。

タプリスちゃんは A に対して、以下のいずれかの操作を選んで行うことを N 回繰り返すことにしました。以下、数列 A の前から i~(1 \leq i \leq |A|) 番目の要素を a_i と書くことにします。

• A の末尾に 1 または M を追加する
• 1 \leq i < |A| である整数 i を 1 つ選択する。a_i < x < a_{i + 1} または a_i > x > a_{i + 1} が成り立つような整数 x を a_i と a_{i + 1} の間に追加する

i 回目の操作を行ったあとの数列 A を S_i と書くことにします。

数列の列 S_1, S_2, \ldots, S_N としてありえるものの種類数を 998244353 で割った余りを求めてください。

制約

• 1 \leq N \leq 3000
• 2 \leq M \leq 10^8

入力例 1

2 3

出力例 1

5

まず最初の操作で A の末尾に 3 を追加すると、A = (1, 3) となります。

次に 2 回目の操作で A の 1 と 3 の間に 2 を追加すると、A = (1, 2, 3) となります。

よってこのように操作を行ったとき、S_1 = (1, 3), S_2 = (1, 2, 3) となります。

この他に考えられるのは、

• S_1 = (1, 1), S_2 = (1, 1, 1) となる場合
• S_1 = (1, 1), S_2 = (1, 1, 3) となる場合
• S_1 = (1, 3), S_2 = (1, 3, 3) となる場合
• S_1 = (1, 3), S_2 = (1, 3, 1) となる場合

の 4 通りです。よって答えは 5 となります。

入力例 2

1024 52689658

出力例 2

654836147

998244353 で割った余りを出力してください。

問題文

H 行 W 列のグリッドがあります。グリッドの各マスには、皿が置かれているマスと皿が置かれていないマスがあります。

皿が置かれているマスのうち、いくつかのマスに豆が置いてあります。それぞれの豆は区別でき、1 つの皿には複数の豆を乗せることができます。

このグリッドを使って、AliceとBobは次のようなゲームをしようと考えています。

• Aliceを先手として、手番を交互に繰り返す。
• 自分の手番では、後述する「手番における豆の動かし方」に沿って豆を1つ動かす。動かせる豆が存在しない場合、即座に手番のプレイヤーは敗北し、手番でないプレイヤーは勝利する。

両者が最適に行動したとき、どちらが勝利するか答えてください。

手番における豆の動かし方

以下、i 行 j 列目の座標を (i,j) と表記する。(1 \leq i \leq H, 1 \leq j \leq W)

まず豆を 1 つ選ぶ。この豆の現在位置を (i,j) とすると、以下の 3 種類の動きで条件をすべて満たすもののうち、1 種類を 1 度だけ行う。

• 3 種類の動き

  • i+1 \leq H のとき、(i+1,j) に移動させる。
  • j=1 のとき、(i,W) に移動させる。そうでないとき、(i,j-1) に移動させる。
  • j=W のとき、(i,1) に移動させる。そうでないとき、(i,j+1) に移動させる。

• 条件

  • 移動先のマスに皿がある。
  • 選んだ豆が初めて移動先のマスに訪れる。

制約

• 1 \leq H,W \leq 1000
• H,W は整数である。

入力例 1

2 3
B.#
#..

出力例 1

Alice

はじめ、豆は (1,1) にあります。

• Aliceの 1 回目の手番では、豆を (1,2) に移動させるしかありません。
• Bobの 1 回目の手番では、豆を (2,2) に移動させるしかありません。
• Aliceの 2 回目の手番では、豆を (2,3) に移動させるしかありません。
• Bobの 2 回目の手番では、豆を動かすことができません。

したがって、Bobの敗北となり、Aliceの勝利となります。

入力例 2

1 1
B

出力例 2

Bob

入力例 3

1 3
B#.

出力例 3

Alice

豆を (1,1) から (1,3) へ動かせることに注意してください。

入力例 4

5 18
#.#..#.#..###..###
##...#.#..#.#..#..
#....#.#..###..#..
##...#.#..#....#..
#.#..###..#....###

出力例 4

Bob

豆が存在しないこともあります。

問題文

N 頂点 M 辺の無向単純連結グラフがあります。

このグラフの頂点には 1 から N までの番号がついていて、辺には 1 から M までの番号がついています。

辺 i (1 \le i \le M) は頂点 u_i と頂点 v_i を結んでいます。

このグラフには、次のような特別な性質があります。

• どの辺 i (1 \le i \le M) についても、頂点 u_i と v_i を結ぶパスで、辺 i を使わないものが存在する。

このようなパスを「辺 i の迂回パス」と呼ぶことにします。1 つの辺の迂回パスは複数存在するかもしれません。

グラフの各辺を、色 1 から色 M までの M 個の色のうちの 1 つを選んで塗ることにします。このとき、次の条件を満たさなければなりません。

• 同じ頂点に接続している 2 つの辺は、異なる色で塗られていなければならない。
• どの辺についても、その辺の迂回パスで、次を満たすものが少なくとも 1 つ存在している。
  • パスが含むすべての辺に使われている色は 8 種類以下である。(※)

このような色の塗り方を 1 つ求めてください。

さらに、そのように色を塗ったグラフの各辺について、上の (※) を満たす迂回パスを 1 つずつ求めてください。（出力方法が特殊なので、詳しくは出力を見てください。）

下記の制約のもとで、このような塗り方は必ず存在することが示せます。

制約

• 3 \le N \le 5555
• 3 \le M \le \min(N(N-1)/2, 9999)
• 1 \le u_i < v_i \le N
• 1 \le i < j \le N に対して、(u_i, v_i) \neq (u_j, v_j)
• 与えられるグラフは連結である。
• どの辺 i (1 \le i \le M) についても、頂点 u_i と v_i を結ぶパスで、辺 i を使わないものが存在する。

部分点

• N \le 111 かつ M \le 222 を満たすデータセットに正解した場合は、10 点が与えられる。
• 追加制約のないデータセットに正解した場合は、上記とは別に 390 点が与えられる。

入力例1

10 11
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
1 10
1 4

出力例1

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

辺 1 の迂回パスとして、辺 2 から辺 10 までの辺を使うものがありますが、これらの辺に使われている色は、色 2 から色 10 までの 9 種類なので、このパスは問題文の条件 (※) を満たしません。

しかし、辺 1 の迂回パスとして、辺 2, 3, 11 を使うものがあります。これらの辺に使われている色は、色 2, 3, 5 の 3 種類なので、このパスは問題文の条件 (※) を満たします。

問題文

これはインタラクティブな要素がある問題です。

Alice は 1 から N までの整数を並び替えた順列 a_1, a_2, \ldots, a_N を隠し持っています。隠し事が嫌いな Bob はなんとかしてこの順列を特定したいです。できるだけこの順列を隠したい Alice は順列のサイズ N と以下の 2 つのタイプの質問の答えのみを教えてくれます。

• タイプ 1: 3 つの異なる整数 i,j,k(1 \leq i,j,k \leq N) を選び、Alice に聞きます。すると、Alice は a_i,a_j,a_k の 3 つの整数の中央値を答えます。
• タイプ 2: 2 つの異なる整数 i,j(1 \leq i,j \leq N) を選び、Alice に聞きます。すると、Alice は a_i, a_j の小さい方の添え字を答えます。つまり、a_i < a_j であれば i, そうでなければ j を答えます。

ただし、Alice はあまり順列の情報を与えたくないので、タイプ 1 の質問には 2N 回、タイプ 2 の質問には 2 回しか答えません。さらに、Alice はいじわるなので、Bob のこれまでの質問に対する返答に矛盾しない範囲で順列の並びを途中で変えてしまうかもしれません。

Bob はとても忙しいので、熟考して質問することができません。Bob の代わりに、質問をして順列を当てるプログラムを作成し、彼を助けてください。

制約

• 4 \leq N \leq 6 \times 10^4

部分点

• タイプ 1 の質問の上限は 3N 回、タイプ 2 の質問の上限は 3 回である。この上限を超えて質問をした場合は Query Limit Exceeded となる。
• 質問回数が上限を超えず、かつ正しい順列を出力したとき、20 点が得られる。
• タイプ 1 の質問が 2N 回以内、かつタイプ 2 の質問が 2 回以内であり、さらに正しい順列を出力したとき、満点が得られる。

入出力

最初に順列のサイズ N が 1 行で与えられる。

N

タイプ 1 の質問をするときは次の形式に従って出力すること。

? 1 i j k

i,j,k は 1 から N までの相異なる整数でなければならない。末尾には改行を出力すること。

タイプ 1 の質問の答えは以下の形式で与えられる。

m

m は 1 から N までの整数である。これは a_i,a_j,a_k の 3 つの整数の中央値である。

タイプ 2 の質問をするときは次の形式に従って出力すること。

? 2 i j

i,j は 1 から N までの相異なる整数でなければならない。末尾には改行を出力すること。

タイプ 2 の質問の答えは以下の形式で与えられる。

k

k は i または j である。a_i < a_j であれば i, そうでなければ j が出力される。

タイプ 1 の質問の上限は 3N 回、タイプ 2 の質問の上限は 3 回である。この上限を超えて質問をした場合は Query Limit Exceeded となる。

質問を何回かした後、順列を当てる必要がある。その際は次の形式に従って出力すること。

! a_1 a_2 a_3 \cdots a_N

順列を出力した後、あなたのプログラムは直ちに終了しなければならない。終了しなかった場合のジャッジ結果は不定である。

また、これら以外のフォーマットで出力した場合のジャッジ結果も不定である。

各出力の後には、出力をフラッシュする必要があることに注意せよ。例えば、タイプ 1 の質問をする際、 C では

printf("? 1 %d %d %d\n", i, j, k); fflush(stdout);

C++ では

cout<<"? 1 "<<i<<" "<<j<<" "<<k<<endl;

と出力すればよい。

順列は最初から固定されていないテストケースがあるので注意せよ。

入出力例

順列が "3,5,4,1,2" である場合に、以下のような入出力が考えられる。

これは入出力の一つの例であり、意味のある入出力をしているとは限らない。

問題文

N_1 + N_2 頂点 M 辺からなる単純無向 2 部グラフがあります。

このグラフの頂点には 1 から N_1 + N_2 までの番号がついていて、辺には 1 から M までの番号がついています。

辺 i は頂点 a_i と頂点 b_i を結んでいます。

ここで a_i, b_i は、1 \le a_i \le N_1 および N_1 + 1 \le b_i \le N_1 + N_2 を満たします。

M 本すべての辺がある状態での、頂点 i の次数を C_i とおきます。

​ あなたは次の操作をできるだけ多くの回数行おうとしています。 ​

操作

• 頂点 i の現在の次数を D_i とおく。
• まだ消していない辺を 1 つ選んで消す。
• ただし、選ぶ辺の番号を x としたとき、次の条件をすべて満たさなければならない。
  • D_{a_x} を 2 で割った余りは C_{b_x} を 2 で割った余りと一致しなければならない。
  • D_{b_x} を 2 で割った余りは C_{a_x} を 2 で割った余りと一致しなければならない。

行える操作の回数の最大値を求め、さらにそれを達成する操作列を 1 つ求めてください。

制約

• 1 \le N_1 \le 3000
• 1 \le N_2 \le 3000
• 1 \le M \le \min(3000, N_1 N_2)
• 1 \le a_i \le N_1 (1 \le i \le M)
• N_1 + 1 \le b_i \le N_1 + N_2 (1 \le i \le M)
• 1 \le i < j \le M に対して、(a_i, b_i) \neq (a_j, b_j)

入力例1

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

出力例1

3
1 4 2

C_1 = 3, C_2 = 2, C_3 = 1, C_4 = 2, C_5 = 2 です。

現在 D_1 = 3, D_2 = 2, D_3 = 1, D_4 = 2, D_5 = 2 なので、操作によって消せる辺は、

• 頂点 1 と頂点 3 を結ぶ辺 1
• 頂点 2 と頂点 4 を結ぶ辺 4
• 頂点 2 と頂点 5 を結ぶ辺 5

だけです。

操作によって辺 1 を消すと、D_1 = 2, D_2 = 2, D_3 = 0, D_4 = 2, D_5 = 2 となります。

したがって、次の操作によって消せる辺は、

• 頂点 2 と頂点 4 を結ぶ辺 4
• 頂点 2 と頂点 5 を結ぶ辺 5

だけになります。

辺 4 を消すと、D_1 = 2, D_2 = 1, D_3 = 0, D_4 = 1, D_5 = 2 となります。

次に消せる辺は、

• 頂点 1 と頂点 4 を結ぶ辺 2

だけになります。

辺 2 を消すと、D_1 = 1, D_2 = 1, D_3 = 0, D_4 = 0, D_5 = 2 となり、消せる辺は残っていません。

上の例では 3 回の操作を行いましたが、どのように操作をしても、3 回より多くの操作を行うことはできません。

したがって、求める答えは 3 になります。

入力例2

1 2 2
1 2
1 3

出力例2

0

どの辺も選ぶことができません。

入力例3

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

出力例3

5
1 7 6 2 4

問題文

これはインタラクティブな要素がある問題です。

Alice は 1 から N までの整数を並び替えた順列を隠し持っています。Alice には Bob という友達がいます。Bob は隠し事が嫌いなので、この順列を特定しようと質問してくることが予想されます。その質問をなるべくかわして特定されないようにするため、Alice は Oscar と模擬訓練を行って練習することにしました。

模擬訓練は質問フェーズと解答フェーズからなります。質問フェーズでは、Alice は順列に関するいくつかの質問に答えなければなりません。その後の解答フェーズでは、質問の解答に矛盾しない順列 a_1, a_2, \ldots, a_N を 2 つ構成しなければなりません。

質問フェーズでは、いくつかの質問が与えられるので順番に答えてください。はじめ、Oscar のスタミナ S は 2N であり、質問するたびにスタミナを消費します。質問には 3 種類あり、以下の形式で与えられます。

• タイプ 1: 3 つの相異なる整数 i,j,k が与えられる。3 つの整数 a_i,a_j,a_k の中央値となるべき整数 m を回答せよ。m は 1 以上 N 以下でなければならない。この質問をすると Oscar のスタミナ S は 2 減少する。

• タイプ 2: 2 つの異なる整数 i,j が与えられる。a_i < a_j となるべきであれば i を、a_i > a_j となるべきであれば j を回答せよ。この質問をすると Oscar のスタミナ S は 2 減少する。

• タイプ 3: 2 つの異なる整数 i,j が与えられる。a_i,a_j の最小値となるべき整数 x を回答せよ。x は 1 以上 N 以下でなければならない。この質問をすると Oscar のスタミナ S は 1 減少する。

質問には必ず答える必要があります。また、Oscar は疲れてしまうので、 質問した後に Oscar のスタミナ S が 2 以下になることはありません。

質問フェーズが終了すると、解答フェーズとなります。

解答フェーズでは、2 つの 1 から N までの整数を並び替えた順列 a_1, a_2, \ldots, a_N と b_1, b_2, \ldots, b_N を Oscar に伝えます。この 2 つの順列は、それぞれの質問フェーズでのすべての回答に矛盾しない順列であり、a_i \neq b_i となる i の個数が \left\lceil \frac{S}{2} \right\rceil 以上であれば、Oscar は混乱します。ここでの S は、Oscar がすべての質問を終えた後のスタミナです。Oscar が混乱するような 2 つの順列を伝えることができれば Alice の勝ちです。このような 2 つの順列を構成できることが証明できます。

Alice にとって Oscar が混乱するような 2 つの順列を探し出すのは非常に難しく、意気消沈してしまいました。どのような質問が来ても Oscar が混乱するような 2 つの順列を出力するプログラムを作成し、Alice を元気づけてください。

制約

• 4 \leq N \leq 5 \times 10^4
• N は整数

入出力

最初に順列のサイズ N が 1 行で与えられる。

N

その後、タイプ 1,2,3 の質問、もしくは解答フェーズの開始を表す記号が入力として与えられる。

タイプ 1 の質問は以下の形式で与えられる。

? 1 i j k

i,j,k は 1 から N までの相異なる整数である。

次に、質問への回答を以下の形式で出力すること。

m

m は 1 から N までの整数でなければならない。さらに、これは a_i,a_j,a_k の 3 つの整数の中央値であり、b_i,b_j,b_k の 3 つの整数の中央値である必要がある。末尾には改行を出力すること。

タイプ 2 の質問は以下の形式で与えられる。

? 2 i j

i,j は 1 から N までの相異なる整数である。

次に、質問への回答を以下の形式で出力すること。

p

p は i または j の整数でなければならない。さらに、p=i であれば a_i < a_j かつ b_i < b_j、p=j であれば a_i > a_j かつ b_i > b_j である必要がある。末尾には改行を出力すること。

タイプ 3 の質問は以下の形式で与えられる。

? 3 i j

i,j は 1 から N までの相異なる整数である。

次に、質問への回答を以下の形式で出力すること。

x

x は x=\min(a_i,a_j)=\min(b_i,b_j) を満たす必要がある。末尾には改行を出力すること。

解答フェーズに移るとき、以下の形式で解答フェーズの開始を表す記号が与えられる。

!

この後、 2 つの順列を以下の形式で出力すること。

a_1 a_2 \cdots a_N
b_1 b_2 \cdots b_N

Bob の残りのスタミナが S の時、順列 a_i \neq b_i となる i の個数が \left\lceil \frac{S}{2} \right\rceil 以上である必要がある。末尾には改行を出力すること。 2 つの順列を出力した後、あなたのプログラムは直ちに終了しなければならない。終了しなかった場合のジャッジ結果は不定である。

また、これら以外のフォーマットで出力した場合のジャッジ結果も不定である。

各出力の後には、出力をフラッシュする必要があることに注意せよ。例えば、タイプ 1 の質問に対して答える際、 C では

printf("%d\n", m); fflush(stdout);

C++ では

cout<<m<<endl;

と出力すればよい。

入出力例

以下のような入出力が考えられる。

これは入出力の一つの例であり、意味のある入出力をしているとは限らない。

問題文

括弧列は、( と ) からなる文字列です。 正しい括弧列を、次のいずれかの条件を満たすものと定義します。

• 空文字列
• 正しい括弧列 A が存在し、( , A , ) をこの順に結合した文字列
• 空でない正しい括弧列 S,T が存在し、S , T をこの順に結合した文字列

いま、N 個の互いに区別できる箱があります。

あなたは N 個の箱それぞれに正しい括弧列を入れようと考えています。ただし、次の2つの条件をともに満たすように入れる必要があります。

• N 個の箱に含まれる ( の個数の合計が M になる。
• 長さが 2 \times K である括弧列はどの箱にも入れてはならない。

条件を満たす入れ方の総数を 998244353 で割ったあまりを求めてください。

ただし、2 つの入れ方が異なることを、「ある箱が存在し、そこに入れた括弧列が異なること」と定義します。

制約

• 1 \leq N \leq 10^6
• 1 \leq M \leq 10^6
• 1 \leq K \leq M

部分点

• 1 \leq N,M \leq 2000 を満たすデータセットに正解した場合は、10 点が与えられる。
• 追加制約のないデータセットに正解した場合は、上記とは別に 490 点が与えられる。

入力例 1

2 2 1

出力例 1

4

• (()) , 空
• ()() , 空
• 空 , (())
• 空 , ()()

の 4 通りです。

入力例 2

1 1 1

出力例 2

0

入力例 3

24 120 30

出力例 3

379268651