KUPCオンサイト京都会場である総合研究7号館の1階には、マッサージチェアが設置されている。

今、3人の学生と3台のマッサージチェアが一直線に並んでいる。 3人の学生のいる座標は x = a_1,a_2,a_3 であり、3台のマッサージチェアが置かれている座標は x = b_1,b_2,b_3 である。 i 番目の学生が j 番目のマッサージチェアに座るためには |a_i-b_j| だけ移動する必要がある。 1台のマッサージチェアには複数人座ることができないものとして、3人全員がマッサージチェアに座る時の移動距離の合計の最小値を出力せよ。

a_1 a_2 a_3 b_1 b_2 b_3

入出力例

入力例1

1 2 3 4 5 6

出力例1

9

入力例2

1 2 3 2 4 0

出力例2

2

ゲーム好きな結衣さんはかねてからの希望が通り、ゲーム好きな教授の研究室に配属されることになった。

そこの研究室では、1以上1000以下の整数で毎日変わる 暗証番号 で部屋がロックされている。そして、部屋に入るには、AI に質問して暗証番号を当てるゲームをする必要があった。

AI には１種類の質問ができる。AI に1以上1000以下の整数 x を与えると AI は暗証番号が x で割り切れるかどうかを返答する。暗証番号の入力はセキュリティ上１回しかできない。暗証番号の入力と AI への質問は合計で QLE 回まで行える。

最初は楽しめていた結衣さんも、いいかげん毎日ゲームをするのにうんざりしてきたので、暗証番号を当てるプログラムを書くことにした。

入出力形式

プログラムはある数字が暗証番号を割り切れるかどうかをAIに聞くことができる。 例えば C/C++で10が暗証番号を割り切れるか聞く場合は

 printf(“? 10\n”); fflush(stdout);

とする．次に、

 char judge[2]; scanf(“%s”, judge);

とすると変数 judge に AI の返答が入る。

またC/C++で15を暗証番号として入力する場合は

printf(“! 15\n”); fflush(stdout);

とする．

制約

• 暗証番号は1以上1000以下の整数である。
• AIに与える整数 x は1以上1000以下でなければならない。
• QLE = 200
• judge \in \{Y, N\}

この問題の判定には、10点分のテストケースのグループが設定されている。このグループに含まれるテストケースは上記の制約に加えて下記の制約も満たす。

• QLE = 1000

入出力例

ゲームの説明
プログラムの出力
プログラムへの入力

 100 で暗証番号が割り切れるかを聞いている
? 100

AIの返答で、100 では暗証番号は割り切れないことを表す
N
 67 で暗証番号を割り切れるかを聞いている
? 67

AIの返答で、67 では暗証番号は割り切れないことを表す
N
 555 で暗証番号を割り切れるかを聞いている
? 555

AIの返答で、555 で暗証番号は割り切れることを表す
Y
 555 と暗証番号を入力している 
! 555

KUPCオンサイト京都会場である総合研究7号館は、各階に談話室が設けられている。 室内には大きなホワイトボードとプロジェクタとスクリーン、きれいな机と椅子が設置されていて、基本的に誰でも自由に使うことができる。 談話室に集まってプログラミングコンテストに参加する人たちもいて、7号館の住人は何かとお世話になっている部屋である。

今日は談話室で、京子さんと結衣さんの2人が、相性度を測るために占いをしている。 この占いでは長さ N,M の2つの数列 A=(a_1,...,a_N) と B=(b_1,...,b_M) を使う。 占いは以下の手順で行われる。

1. 京子さんと結衣さんの間で2つの整数 N,M を決めた後、Q 個の約束をする。各約束は2つの整数 c_i,d_i で表され、数列 A の c_i 番目の数字と数列 B の d_i 番目の数字が同じでなければならないことを指す。約束を一つでも破ってしまったら、二人の相性度は0となる。
2. 京子さんは長さ N の数列 A=(a_1,...,a_N) をひとつ頭の中に思い浮かべる。同様に、結衣さんは長さ M の数列 B=(b_1,...,b_M) をひとつ頭の中に思い浮かべる。
3. 京子さんと結衣さんは、それぞれ自分の思い浮かべた数列の数字を繰り返しホワイトボードに書いていく。より厳密には、i(≥1) 回目の書き込みで、京子さんは数列 A の ((i-1) mod N)+ 1 番目の数字を、結衣さんは数列 B の ((i-1) mod M)+ 1 番目の数字を、同時にホワイトボードに書く。x mod y は x を y で割った余りを指す。t 回目の書き込みで、二人が同時に書いた数字が異なる場合、相性占いを終了し、二人の相性度は t となる。
4. 手順3が 10^{10} 回以上続いてしまうと、結衣さんは占いに飽きてしまい、二人の相性度は0となる。

京子さんはたった今、結衣さんと Q 個の約束をしたところである。京子さんは今からしようとしている占いで最大いくつの相性度を得られるのか非常に気にしているので、談話室にいたあなたは相性の最大値を計算してあげることにした。

N M Q
c_1 d_1
…
c_Q d_Q

入出力例

入力例1

3 2 0

出力例1

4

入力例2

3 6 0

出力例2

6

入力例3

3 2 1
3 2

出力例3

3

入力例4

3 3 2
1 3
3 1

出力例4

2

入力例5

4 4 3
1 4
3 4
4 4

出力例5

3

あるところに，バイナリ文字列を好む王様がいた． 王様は，等しい長さの二つのバイナリ文字列がどれくらい似ているかを調べるために， ハミング距離を計算することを得意としていた．

ハミング距離とは，文字が異なる箇所の個数で定義される距離尺度である． 例えば，1011101と1001001は3文字目と5文字目が異なるので， ハミング距離は2である． ハミング距離は，異なる長さのバイナリ文字列の間には定義されないことに注意すること．

あるとき王様は，バイナリ文字列 s_1 とのハミング距離が d_1 であり， バイナリ文字列 s_2 とのハミング距離が d_2 であるようなバイナリ文字列がいくつあるのかが気になった．

あなたは王様のために，そのような条件をみたすバイナリ文字列がいくつ存在するか計算するプログラムを書かなければならない． ただし，その個数は膨大になる場合があるので，10^{9} + 7 で割った余りを出力すること．

s_1
d_1
s_2
d_2

入出力例

入力例1

1000
2
0100
2

出力例1

4

1110, 1101, 0010, 0001の4つのバイナリ文字列が条件を満たす．

入力例2

1000
2
0100
1

出力例2

0

入力例3

0000111011111100111110001000011101010111
22
1111010000001001111110111111001111011110
13

出力例3

734254418

問題文

N \times M の長方形状の領域がある． この領域を以下の2種類のピースをどちらも1つ以上用いて， 重ならないように隙間なく敷き詰めたい． ピースは回転させても良いが，領域からはみ出してはいけない．

果たして敷き詰めることは可能なのだろうか？ 可能ならば Possible を，不可能ならば Impossible を出力せよ．

C
N_1 M_1
…
N_C M_C

制約

• 1 \leq C \leq 10000
• 1 \leq N_i \leq 100000
• 1 \leq M_i \leq 100000
• 入力値はすべて整数である．

入出力例

入力例1

6
2 4
4 4
8 6
100 100
3 3
23456 23456

出力例1

Impossible
Possible
Possible
Possible
Impossible
Possible

2番目と3番目のクエリについての敷き詰め方の例を以下に示す．

二次元平面上に N 匹のきつねがいる． i 番目のきつねのx座標は x_i で，y座標は y_i である．

きつねたちは，特別な力を使って遠く離れた仲間たちと連絡をとりあうことができる． 二匹のきつねの力の強さを p_1, p_2 とし，きつねの間のユークリッド距離を D としたとき， p_1 + p_2 \geq D ならば彼らは連絡をとりあうことができる． ただし，i 番目のきつねと j 番目のきつねのユークリッド距離は \sqrt{ (x_i - x_j) ^ {2} + (y_i - y_j) ^ {2} } である． i 番目のきつねの力の強さは，初め d_i で，コスト c_i を支払うたびに強さを1上昇させることができる．

ここで， N 匹のきつねの間に連絡網 T を作ることを考える． T は N 匹のきつねを頂点とした全域木であり，N - 1 個の辺 (u_1, v_1), …, (u_{N - 1}, v_{N - 1}) からなる．すなわち i = 1, …, N-1 について u_i 番目のきつねと v_i 番目のきつねが辺で結ばれている ． 連絡網 T を作るためには， T 中の任意の辺 (u, v) に対して u番目のきつね と v番目のきつね は連絡をとりあうことができるようにする必要がある． たとえ他のきつねを経由して連絡することができるときも， u 番目のきつね と v 番目のきつね が直接連絡をとりあう状態でなければならない．

必要なコストがなるべく小さくなるようにきつねの力の強さを上昇させたとき， T を作るためのコストはいくつになるか求めなさい．

N
x_1 y_1
…
x_N y_N
d_1 c_1
…
d_N c_N
u_1 v_1
…
u_{N-1} v_{N-1}

入出力例

入力例1

3
0 0
3 0
-3 0
1 100
1 3
1 3
1 2
1 3

出力例1

6

2匹目のきつねと3匹目のきつねの力をそれぞれ1上昇させるのが最善である．

入力例2

3
0 0
3 0
-3 0
1 5
1 3
1 3
1 2
1 3

出力例2

5

1匹目のきつねの力を1上昇させるのが最善である．

入力例3

4
0 0
7 0
-7 0
0 5
2 5
2 1
2 1
2 10
1 2
1 3
1 4

出力例3

9

1匹目のきつねの力を1, 2匹目と3匹目のきつねの力をそれぞれ2上昇させるのが最善である．

入力例4

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

出力例4

3

2匹目のきつねの力を3上昇させるのが最善である．

この問題はリアクティブ形式の問題である． つまり，あなたは応答プログラムとあるゲームを行う．

あなたのプログラムは，はじめに，入力として2つの整数 N と D が与えられる． それにたいして，長さ N の 0/1 列を出力する． すると，応答プログラムは，2人の小人，京子さんと結衣さんをこの列の上のどこかに配置する．このときの京子さんの位置を i とし，結衣さんの位置をjとする． また、このとき京子さんと結衣さんは必ず D だけ離れている． (|i-j| = D である)． あなたは常に2人の位置にある文字を知ることができる．

この条件の下で，あなたは応答プログラムと京子さんと結衣さんの位置関係を特定するゲームを行う．あなたは応答プログラムに命令を渡し，京子さんまたは結衣さんのどちらか一方を左右に1つずつ動かすことができる．2人の初期位置は列の端から十分遠く設定されるので、命令によって2人のどちらかが列の端から飛び出してしまう場合を考慮する必要はない．そして最後に2人の位置関係を特定し i < j または j < i なのかを応答プログラムに入力せよ．位置関係の入力は1回しか行えない．命令は位置関係の入力と合計で50回まで行える．

できるだけ少ない移動回数で i < j なのか j < iなのかを特定せよ.

N D

printf("011\n"); fflush(stdout);

scanf("%d %d", &a, &b);

printf(“Move(A,1)\n”); fflush(stdout);

scanf(“%d %d”, &a, &b);

printf(“Move(B,-1)\n”); fflush(stdout);

scanf(“%d %d”, &a, &b);

制約

• 10000 \leq N \leq 100000
• 1 \leq D \leq N-1
• 入力値はすべて整数である．
• 命令は位置関係の入力と合計で50回まで行える
• 2人の初期位置は列の端から十分遠く設定されるので、命令によって2人のどちらかが列の端から飛び出してしまう場合を考慮する必要はない
• この問題の時間制限は6秒に設定されているが、このうち最大2秒程度が応答プログラムが2人の初期位置を決めるために使われる

採点方式

• C \leq 5 ならば 900点
• C \gt 5 ならば 900 / (C - 4) 点となる。

入出力例

説明
プログラムの出力
プログラムへの入力

あなたが出力する0/1列の長さと2人の間隔が与えられる
10000 100
長さ10000の 0/1 列を出力する
010101 … 010101

京子さんと結衣さんの位置の文字が返される
0 1
京子さんを1つ右に動かす
Move(A,1)

京子さんと結衣さんの位置の文字が返される
1 1
結衣さんを1つ左に動かす
Move(B,-1)

京子さんと結衣さんの位置の文字が返される
1 0
京子さんの初期位置が結衣さんの初期位置より左にあったと確定する
i<j

初期位置から距離 L 離れた目的地まで直線上のコースに沿って自転車を走らせるゲームをする．

このゲームでは，初期位置から目的地までのルートの途中，自転車が地上を走れる場所が限定されている． ここで，自転車が地上を走れる場所を地面と呼ぶ． 地面は N 個の区間 [a_i,b_i](i=1,…,N) によって表され， 初期位置からの距離 x が，ある i に対して a_i \leq x \leq b_i を満たす場合，その地点で自転車が地上を走れることを意味する．

自転車は自動的に一定の速度で前へ走るが，自転車が地上を走っている場合，プレイヤーは自転車をジャンプさせる事ができる． ジャンプをすると，自転車はその瞬間から空中に飛び，ちょうど距離 W 進んだところで着地する． 空中を飛んでいる間は，地面以外の区間を通過する事が可能だが，着地地点は地面でなければならない． また，着地地点がゴールを超えることは許されない． ジャンプは1回のゲーム中に何回でも可能であり，着地後直ちに再びジャンプすることも可能である． 一連のジャンプを終えると，自転車は再び自動的に前へ走る．

地面以外を走らせることなく自転車をゴールまで到達させるとき，必要なジャンプの最小回数を求めよ． ただし，どのようにジャンプさせても自転車をゴールまで到達させることが不可能な場合は -1 を出力せよ．

図H. 入力例1における自転車の走らせ方の例

N L W
a_1 b_1
…
a_N b_N

入出力例

入力例1

2 10 4
0 4
6 10

出力例1

1

入力例2

5 40 10
0 1
9 11
19 21
29 31
39 40

出力例2

4

入力例3

4 13 6
0 1
2 3
5 6
12 13

出力例3

2

入力例4

2 10 7
0 1
9 10

出力例4

-1

時は30世紀，きつねのしえるは雨を司る神としてKUPC国の降雨量を管理している． KUPC国は N 個の地域に分割されており，しえるはそれぞれの地域にまんべんなく雨を降らさなければならない． しえるは呪文をとなえて雨を降らせる． 呪文は M 種類あり，それぞれ 1 から M まで番号づけられている． i 番目の呪文には湿潤の地域 a_i と乾燥の地域 b_i とが定められており， a_i 番目の地域には雨が 2 降り，b_i 番目の地域には雨が降らず， それ以外の N-2 箇所の地域には雨が 1 降る． また，i 番目の呪文を実行するのに d_i 日の日数を要する．

まず，最初に K 個の呪文 (c_1,...,c_{K}) が実行される． しえるは，その K 個の呪文が実行された後にいくつかの呪文を実行して，各地域の合計雨量を等しくしたいと思っている． K 個の呪文が実行されてから，各地域の合計雨量を等しくするのに最低何日かかるか出力せよ． ただし，各地域の合計雨量を等しく出来ない場合は -1 を出力せよ．

N M K
c_1 … c_{K}
a_1 b_1 d_1
…
a_M b_{M} d_M

制約

• 2 \leq N \leq 10000
• 1 \leq M \leq 20000
• 1 \leq K \leq 15
• 1 \leq c_i \leq M
• 1 \leq a_i \leq N
• 1 \leq b_i \leq N
• a_i \neq b_i
• 1 \leq d_i \leq 3
• 入力値はすべて整数である．

この問題の判定には，30点分のテストケースのグループが設定されている．このグループに含まれるテストケースは上記の制約に加えて下記の制約も満たす．

• K = 1

入出力例

入力例1

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

出力例1

9

3,5,7,9,10番目の呪文を実行すれば9日で各地域に同じ量の雨を降らせる事ができる．

入力例2

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

出力例2

-1

入力例3

2 2 2
1 1
1 2 2
2 1 3

出力例3

6

入力例4

2 2 2
1 2
1 2 2
2 1 3

出力例4

0

入力例5

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

出力例5

6

あなたは最初の日に 0 円持っているとする。 毎日 P 円のお小遣いをもらえるので 何日かかけて合計で N 枚のカードを買いたい。 カードは1日に最低 0 枚、最大 M 枚買うことができる。
あなたがある日に k 枚 (k = 1, 2, ..., M) のカードを買う場合には x_1 + x_2 + ... + x_k 円を支払わなければならない。 1枚も買わない場合には、お小遣いは減らない。
x_1 \leq P が保証されている。
N 枚のカードを買うには最短で何日かかる求めよ。

N M P
x_1
…
x_M

入出力例

入力例1

9 4 4
1
2
3
4

出力例1

4

例えば、初めの3日間にカードを2枚ずつ買うとすると、1日あたり1+2=3 円支払う。 4日目は、その日にもらえる4円と合わせて7円使うことができるので、1+2+3=6円で3枚のカードを買い、4日で9枚のカードを買うことができる。

入力例2

8 4 3
3
1
1
1

出力例2

4

この入力例は部分点の制約を満たしていない。

KUPCに参加しているあなたは、不運にもコーディング中にモンスターの集団に妨害されてしまった。 優秀なプログラマーであるあなたは、モンスターに対して適切な文字列で攻撃して退治しなければならないのであった。

モンスターは N 体いる。各モンスターにはそれぞれ弱点があり、i 番目 ( i=1,….,N )のモンスターの弱点は文字列S_iで表される。 i 番目のモンスターが文字列 T で攻撃されたとき、T が S_i の部分文字列であるならばそのモンスターは |T| のダメージを受ける。 部分文字列でない場合はダメージは 0 になる。

あなたは文字列 T を一つ決めて、N 体のモンスターに T で一度ずつ攻撃する。 この時、N 体のモンスターに与えるダメージの総和を最大にするような T を求め、ダメージの総和を出力せよ。
ただし、ダメージが 0 のモンスターがいても良い。

文字列 x について、|x| は x の長さを意味する。
文字列 x と文字列 y について、 x = y_i y_{i+1} … y_{i+l-1} (1 \leq i \leq |y|, 0 \leq l \leq |y|-i+1) であるとき、x は y の部分文字列であると言う。 ただし y_i (i = 1,…,|y|) は、 y の i 番目の文字を意味する。

N
S_1
…
S_N

入出力例

入力例1

3
aab
ab
ac

出力例1

4

文字列"a"で攻撃すると 1, 2, 3 番目のモンスターにそれぞれ 1 ダメージを与え、ダメージの総和は 3 である。
文字列"ab"で攻撃すると 1, 2 番目のモンスターにそれぞれ 2 ダメージを与え、ダメージの総和は 4 である。 この時、ダメージの総和は最大になる。

入力例2

2
abcde
cd

出力例2

5

べき乗数の数の集合を以下で定める.

• 1 はべき乗数
• x がべき乗数なら 2^x, 3^x, 5^x, 7^xもべき乗数.
• 上の２つの条件からべき乗数と定まる数のみがべき乗数

(注) {b_1}\^{b_2}\^...\^{b_N} はべき乗を右から優先して計算した値を意味する. 例えば 2\^3\^2=2\^9=512 である.

N
b_1
b_2
…
b_N

制約

• 1 \leq N \leq 1000
• b_i∈\{2,3,5,7\}

この問題の判定には，50点分のテストケースのグループが設定されている．このグループに含まれるテストケースは上記の制約に加えて下記の制約も満たす．

• 1 ≤ N ≤ 4

入出力例

入力例1

2
3
2

出力例1

7

3^2=9 より小さいべき乗数は 1,2,3,4,5,7,8 の7個である.

入力例2

3
2
7
5

出力例2

100

入力例2

32
2
2
2
2
3
3
3
3
5
5
5
5
7
7
7
7
2
2
2
2
3
3
3
3
5
5
5
5
7
7
7
7

出力例2

223914000

10^9+7 で割ったあまりを出力する.