A - Who Ate the Cake?

Time Limit: 2 sec / Memory Limit: 1024 MB

### 制約

• 1\leq A,B\leq 3
• 入力は全て整数

### 入力

A B


### 入力例 1

1 2


### 出力例 1

3


### 入力例 2

1 1


### 出力例 2

-1


### 入力例 3

3 1


### 出力例 3

2


Score : 100 points

### Problem Statement

Takahashi's cake has been eaten by someone. There are three suspects: person 1, person 2, and person 3.

There are two witnesses, Ringo and Snuke. Ringo remembers that person A is not the culprit, and Snuke remembers that person B is not the culprit.

Determine if the culprit can be uniquely identified based on the memories of the two witnesses. If the culprit can be identified, print the person's number.

### Constraints

• 1 \leq A, B \leq 3
• All input values are integers.

### Input

The input is given from Standard Input in the following format:

A B


### Output

If the culprit can be uniquely identified based on the memories of the two witnesses, print the person's number; otherwise, print -1.

### Sample Input 1

1 2


### Sample Output 1

3


From the memories of the two witnesses, it can be determined that person 3 is the culprit.

### Sample Input 2

1 1


### Sample Output 2

-1


From the memories of the two witnesses, it cannot be determined whether person 2 or person 3 is the culprit. Therefore, print -1.

### Sample Input 3

3 1


### Sample Output 3

2

B - Piano 2

Time Limit: 2 sec / Memory Limit: 1024 MB

### 制約

• 1\leq N,M \leq 100
• 1\leq A_i,B_j \leq 200
• A_1, A_2, \dots, A_N, B_1, B_2, \dots, B_M は相異なる
• 入力はすべて整数

### 入力

N M
A_1 A_2 \dots A_N
B_1 B_2 \dots B_M


### 出力

A に現れる要素が C において2つ連続するならば Yes を、そうでないなら No を出力せよ。

### 入力例 1

3 2
3 2 5
4 1


### 出力例 1

Yes


C=(1,2,3,4,5) です。A に現れる 2,3C で連続しているため、Yes を出力します。

### 入力例 2

3 2
3 1 5
4 2


### 出力例 2

No


C=(1,2,3,4,5) です。A に現れる要素が C で連続している箇所はないため、No を出力します。

### 入力例 3

1 1
1
2


### 出力例 3

No


Score : 200 points

### Problem Statement

You are given a sequence A=(A_1,A_2,\dots,A_N) of length N and a sequence B=(B_1,B_2,\dots,B_M) of length M. Here, all elements of A and B are pairwise distinct. Determine whether the sequence C=(C_1,C_2,\dots,C_{N+M}) formed by sorting all elements of A and B in ascending order contains two consecutive elements appearing in A.

### Constraints

• 1 \leq N, M \leq 100
• 1 \leq A_i, B_j \leq 200
• A_1, A_2, \dots, A_N, B_1, B_2, \dots, B_M are distinct.
• All input values are integers.

### Input

The input is given from Standard Input in the following format:

N M
A_1 A_2 \dots A_N
B_1 B_2 \dots B_M


### Output

If C contains two consecutive elements appearing in A, print Yes; otherwise, print No.

### Sample Input 1

3 2
3 2 5
4 1


### Sample Output 1

Yes


C=(1,2,3,4,5). Since 2 and 3 from A occur consecutively in C, print Yes.

### Sample Input 2

3 2
3 1 5
4 2


### Sample Output 2

No


C=(1,2,3,4,5). Since no two elements from A occur consecutively in C, print No.

### Sample Input 3

1 1
1
2


### Sample Output 3

No

C - Bingo 2

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

N 行、横 N 列のマス目があり、上から i 行目、左から j 列目のマスには整数 N\times (i-1)+j が書かれています。

ここで、ビンゴを達成するとは以下のいずれかのうち少なくとも一つ満たされることを言います。

• マス目の横の列であって、列に含まれる N 個のマスすべてに印がついているものが存在する
• マス目の縦の列であって、列に含まれる N 個のマスすべてに印がついているものが存在する
• マス目の対角線の列であって、列に含まれる N 個のマスすべてに印がついているものが存在する

### 制約

• 2\leq N\leq 2\times 10^3
• 1\leq T\leq \min(N^2,2\times 10^5)
• 1\leq A_i\leq N^2
• i\neq j ならば A_i\neq A_j
• 入力は全て整数

### 入力

N T
A_1 A_2 \ldots A_T


### 出力

T ターンの中でビンゴを達成するならば初めてビンゴを達成するターンを、そうでないならば -1 を出力せよ。

### 入力例 1

3 5
5 1 8 9 7


### 出力例 1

4


マス目の状態は以下のように変化します。初めてビンゴを達成するのは 4 ターン目です。

### 入力例 2

3 5
4 2 9 7 5


### 出力例 2

-1


5 ターンの中でビンゴを達成できないので -1 を出力してください。

### 入力例 3

4 12
13 9 6 5 2 7 16 14 8 3 10 11


### 出力例 3

9


Score : 300 points

### Problem Statement

There is an N \times N grid, where the cell at the i-th row from the top and the j-th column from the left contains the integer N \times (i-1) + j.

Over T turns, integers will be announced. On Turn i, the integer A_i is announced, and the cell containing A_i is marked. Determine the turn on which Bingo is achieved for the first time. If Bingo is not achieved within T turns, print -1.

Here, achieving Bingo means satisfying at least one of the following conditions:

• There exists a row in which all N cells are marked.
• There exists a column in which all N cells are marked.
• There exists a diagonal line (from top-left to bottom-right or from top-right to bottom-left) in which all N cells are marked.

### Constraints

• 2 \leq N \leq 2 \times 10^3
• 1 \leq T \leq \min(N^2, 2 \times 10^5)
• 1 \leq A_i \leq N^2
• A_i \neq A_j if i \neq j.
• All input values are integers.

### Input

The input is given from Standard Input in the following format:

N T
A_1 A_2 \ldots A_T


### Output

If Bingo is achieved within T turns, print the turn number on which Bingo is achieved for the first time; otherwise, print -1.

### Sample Input 1

3 5
5 1 8 9 7


### Sample Output 1

4


The state of the grid changes as follows. Bingo is achieved for the first time on Turn 4.

### Sample Input 2

3 5
4 2 9 7 5


### Sample Output 2

-1


Bingo is not achieved within five turns, so print -1.

### Sample Input 3

4 12
13 9 6 5 2 7 16 14 8 3 10 11


### Sample Output 3

9

D - Intersecting Intervals

Time Limit: 3 sec / Memory Limit: 1024 MB

### 問題文

N 個の実数の区間が与えられます。i\,(1 \leq i \leq N) 番目の区間は [l_i,r_i] です。i 番目の区間と j 番目の区間が共通部分を持つような組 (i,j)\,(1\leq i < j \leq N) の個数を求めてください。

### 制約

• 2 \leq N \leq 5 \times 10^5
• 0 \leq l_i < r_i \leq 10^9
• 入力はすべて整数

### 入力

N
l_1 r_1
l_2 r_2
\vdots
l_N r_N


### 入力例 1

3
1 5
7 8
3 7


### 出力例 1

2


### 入力例 2

3
3 4
2 5
1 6


### 出力例 2

3


### 入力例 3

2
1 2
3 4


### 出力例 3

0


Score : 400 points

### Problem Statement

You are given N intervals of real numbers. The i-th (1 \leq i \leq N) interval is [l_i, r_i]. Find the number of pairs (i, j)\,(1 \leq i < j \leq N) such that the i-th and j-th intervals intersect.

### Constraints

• 2 \leq N \leq 5 \times 10^5
• 0 \leq l_i < r_i \leq 10^9
• All input values are integers.

### Input

The input is given from Standard Input in the following format:

N
l_1 r_1
l_2 r_2
\vdots
l_N r_N


### Sample Input 1

3
1 5
7 8
3 7


### Sample Output 1

2


The given intervals are [1,5], [7,8], [3,7]. Among these, the 1-st and 3-rd intervals intersect, as well as the 2-nd and 3-rd intervals, so the answer is 2.

### Sample Input 2

3
3 4
2 5
1 6


### Sample Output 2

3


### Sample Input 3

2
1 2
3 4


### Sample Output 3

0

E - Guess the Sum

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

この問題は インタラクティブな問題（あなたの作成したプログラムとジャッジシステムが入出力を介して対話を行う形式の問題）です。

あなたの目標は A_L+A_{L+1}+\dots+A_{R}100 で割った余りを求めることです。ただし、あなたは数列 A の要素の値を直接知ることはできません。 その代わりに、ジャッジシステムに対して以下の質問を行うことができます。

• 2^i(j+1)\leq 2^N を満たすように非負整数 i,j を選ぶ。l=2^ij,r=2^i(j+1)-1 として A_l+A_{l+1}+\dots+A_{r}100 で割った余りを聞く。

どのような A であっても A_L+A_{L+1}+\dots+A_{R}100 で割った余りを特定することができる質問回数の最小値を m とします。m 回以内の質問を行って A_L+A_{L+1}+\dots+A_{R}100 で割った余りを求めてください。

### 制約

• 1\leq N\leq 18
• 0\leq L\leq R\leq 2^N-1
• 入力は全て整数

### 入出力

この問題はインタラクティブな問題（あなたの作成したプログラムとジャッジシステムが入出力を介して対話を行う形式の問題）です。

N L R


? i j


ここで、i,j は以下を満たす必要があります。

• i,j は非負整数
• 2^i(j+1)\leq 2^N

これに対する応答は、次の形式で標準入力から与えられます。

T


ここで、T は質問に対する答えで、l=2^ij,r=2^i(j+1)-1 としたとき A_l+A_{l+1}+\dots+A_{r}100 で割った余りです。

ただし、i,j が制約を満たしていないか、質問回数が m 回を超えた場合は T-1 となります。

ジャッジが -1 を返した場合、プログラムはすでに不正解とみなされています。この場合、ただちにプログラムを終了してください。

A_L+A_{L+1}+\dots+A_{R}100 で割った余りが特定出来たら、SA_L+A_{L+1}+\dots+A_{R}100 で割った余りとして以下の形式で出力してください。その後、ただちにプログラムを終了してください。

! S


### 注意点

• 出力を行うたびに、末尾に改行を入れて標準出力を flush してください。そうしなかった場合、ジャッジ結果が TLE となる可能性があります。
• 対話の途中で誤った出力形式による出力を行った、あるいはプログラムが途中で終了した場合のジャッジ結果は不定です。
• 解答を出力したらただちにプログラムを終了してください。そうしない場合、ジャッジ結果は不定です。

### 入出力例

3 1 5 まず整数 N,L,R が与えられます。
? 0 1 (i,j)=(0,1) として質問を行います。
41 l=1,r=1 であるため、質問の答えは A_1=41100 で割った余りである 41 です。ジャッジはその値を返します。
? 1 1 (i,j) = (1,1) として質問を行います。
85 l=2,r=3 であるため、質問の答えは A_2+A_3=85100 で割った余りである 85 です。ジャッジはその値を返します。
? 1 2 (i,j) = (1,2) として質問を行います。
11 l=4,r=5 であるため、質問の答えは A_4+A_5=111100 で割った余りである 11 です。ジャッジはその値を返します。
! 37 答えは 37 であるとわかったので、それを出力します。

Score : 500 points

### Problem Statement

This is an interactive problem (where your program interacts with the judge via input and output).

You are given a positive integer N and integers L and R such that 0 \leq L \leq R < 2^N. The judge has a hidden sequence A = (A_0, A_1, \dots, A_{2^N-1}) consisting of integers between 0 and 99, inclusive.

Your goal is to find the remainder when A_L + A_{L+1} + \dots + A_R is divided by 100. However, you cannot directly know the values of the elements in the sequence A. Instead, you can ask the judge the following question:

• Choose non-negative integers i and j such that 2^i(j+1) \leq 2^N. Let l = 2^i j and r = 2^i (j+1) - 1. Ask for the remainder when A_l + A_{l+1} + \dots + A_r is divided by 100.

Let m be the minimum number of questions required to determine the remainder when A_L + A_{L+1} + \dots + A_R is divided by 100 for any sequence A. You need to find this remainder within m questions.

### Constraints

• 1 \leq N \leq 18
• 0 \leq L \leq R \leq 2^N - 1
• All input values are integers.

### Input and Output

This is an interactive problem (where your program interacts with the judge via input and output).

First, read the integers N, L, and R from Standard Input:

N L R


Then, repeat asking questions until you can determine the remainder when A_L + A_{L+1} + \dots + A_R is divided by 100. Each question should be printed in the following format:

? i j


Here, i and j must satisfy the following constraints:

• i and j are non-negative integers.
• 2^i(j+1) \leq 2^N

The response to the question will be given in the following format from Standard Input:

T


Here, T is the answer to the question, which is the remainder when A_l + A_{l+1} + \dots + A_r is divided by 100, where l = 2^i j and r = 2^i (j+1) - 1.

If i and j do not satisfy the constraints, or if the number of questions exceeds m, then T will be -1.

If the judge returns -1, your program is already considered incorrect. In this case, terminate the program immediately.

Once you have determined the remainder when A_L + A_{L+1} + \dots + A_R is divided by 100, print the remainder S in the following format and terminate the program immediately:

! S


### Notes

• At the end of each output, print a newline and flush Standard Output. Otherwise, the verdict may be TLE.
• If your output is malformed or your program exits prematurely, the verdict will be indeterminate.
• After printing the answer, terminate the program immediately. Otherwise, the verdict will be indeterminate.

### Example

Here is an example for N=3, L=1, R=5, and A=(31, 41, 59, 26, 53, 58, 97, 93). In this case, m=3, so you can ask up to three questions.

Input Output Description
3 1 5 First, the integers N, L, and R are given.
? 0 1 Ask the question with (i, j) = (0, 1).
41 l=1 and r=1, so the response is the remainder when A_1=41 is divided by 100, which is 41. The judge returns this value.
? 1 1 Ask the question with (i, j) = (1, 1).
85 l=2 and r=3, so the response is the remainder when A_2 + A_3 = 85 is divided by 100, which is 85. The judge returns this value.
? 1 2 Ask the question with (i, j) = (1, 2).
11 l=4 and r=5, so the response is the remainder when A_4 + A_5 = 111 is divided by 100, which is 11. The judge returns this value.
! 37 The answer is 37, so print this value.
F - MST Query

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

Q 個のクエリが与えられるので順に処理してください。i 番目のクエリは以下で説明されます。

• 整数 u_i,v_i,w_i が与えられる。G の頂点 u_i,v_i の間に重み w_i の辺を追加する。その後、G の最小全域木に含まれる辺の重みの和を出力する。

### 制約

• 2\leq N\leq 2 \times 10^5
• 1\leq Q\leq 2 \times 10^5
• 1\leq a_i\lt b_i\leq N
• 1\leq u_i\lt v_i\leq N
• 1\leq c_i,w_i\leq 10
• クエリを処理する前のグラフは連結
• 入力はすべて整数

### 入力

N Q
a_1 b_1 c_1
\vdots
a_{N-1} b_{N-1} c_{N-1}
u_1 v_1 w_1
\vdots
u_Q v_Q w_Q


### 出力

Q 行出力せよ。i 行目には i 番目のクエリに対する答えを出力せよ。

### 入力例 1

4 4
1 2 6
2 3 5
2 4 4
1 3 3
1 2 3
1 4 10
3 4 1


### 出力例 1

12
10
10
7


### 入力例 2

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


### 出力例 2

49
46
45
38
34
33


Score : 550 points

### Problem Statement

You are given a weighted undirected connected graph G with N vertices and N-1 edges, where vertices are numbered 1 to N and edges are numbered 1 to N-1. Edge i connects vertices a_i and b_i with a weight of c_i.

You are given Q queries to process sequentially. The i-th query is described as follows:

• You are given integers u_i, v_i, w_i. Add an edge with weight w_i between vertices u_i and v_i in G. Then, print the sum of the weights of the edges in a minimum spanning tree of G.

### Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq a_i < b_i \leq N
• 1 \leq u_i < v_i \leq N
• 1 \leq c_i, w_i \leq 10
• The graph is connected before processing the queries.
• All input values are integers.

### Input

The input is given from Standard Input in the following format:

N Q
a_1 b_1 c_1
\vdots
a_{N-1} b_{N-1} c_{N-1}
u_1 v_1 w_1
\vdots
u_Q v_Q w_Q


### Output

Print Q lines. The i-th line should contain the answer to the i-th query.

### Sample Input 1

4 4
1 2 6
2 3 5
2 4 4
1 3 3
1 2 3
1 4 10
3 4 1


### Sample Output 1

12
10
10
7


Here is the graph after adding the edge for each query. The edges included in the minimum spanning tree are colored red.

### Sample Input 2

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


### Sample Output 2

49
46
45
38
34
33

G - Baseball

Time Limit: 5 sec / Memory Limit: 1024 MB

### 問題文

まず、高橋君が、 1,2,\dots,N から K 個の相異なる整数 x_1,x_2,\dots,x_K を選びます。

### 制約

• 1 \leq N \leq 5 \times 10^4
• 1 \leq K \leq N
• 0 \leq P_i \leq 10^5
• 1 \leq \sum_{y'=1}^N P_{y'} \leq 10^5
• 入力はすべて整数

### 入力

N K
P_1 P_2 \dots P_N


### 入力例 1

5 2
1 1 1 1 1


### 出力例 1

3


### 入力例 2

5 1
0 0 1 0 0


### 出力例 2

0


### 入力例 3

1 1
100


### 出力例 3

0


### 入力例 4

20 7
4262 9522 2426 3823 7364 964 2743 2423 1955 5274 3684 847 363 35 278 3220 203 2904 6304 1928


### 出力例 4

22809


Score : 650 points

### Problem Statement

You are given a sequence P=(P_1,P_2,\dots,P_N) of length N. Takahashi and Aoki will play a game using the sequence P.

First, Takahashi will choose K distinct integers x_1,x_2,\dots,x_K from 1,2,\dots,N.

Next, Aoki will choose an integer y from 1,2,\dots,N with a probability proportional to P_y. That is, the probability that integer y is chosen is \dfrac{P_y}{\sum_{y'=1}^N P_{y'}}. Then, Aoki's score will be \displaystyle \min_{i=1,2,\dots,K} |x_i-y|.

Takahashi wants to minimize the expected value of Aoki's score. Find the expected value of Aoki's score when Takahashi chooses x_1,x_2,\dots,x_K so that this value is minimized, multiplied by \sum_{y'=1}^N P_{y'}. It is guaranteed that the value to be printed is an integer.

### Constraints

• 1 \leq N \leq 5 \times 10^4
• 1 \leq K \leq N
• 0 \leq P_i \leq 10^5
• 1 \leq \sum_{y'=1}^N P_{y'} \leq 10^5
• All input values are integers.

### Input

The input is given from Standard Input in the following format:

N K
P_1 P_2 \dots P_N


### Sample Input 1

5 2
1 1 1 1 1


### Sample Output 1

3


The probabilities of Aoki choosing 1,2,\dots,N are all equal: \frac{1}{5}.

If Takahashi chooses x_1=2 and x_2=4, then the expected value of Aoki's score will be 1 \times \frac{1}{5} + 0 \times \frac{1}{5} + 1 \times \frac{1}{5} + 0 \times \frac{1}{5} + 1 \times \frac{1}{5} = \frac{3}{5}.

If Takahashi chooses x_1=2 and x_2=3, then the expected value of Aoki's score will be 1 \times \frac{1}{5} + 0 \times \frac{1}{5} + 0 \times \frac{1}{5} + 1 \times \frac{1}{5} + 2 \times \frac{1}{5} = \frac{4}{5}.

No matter how Takahashi chooses, the expected value of Aoki's score cannot be smaller than \frac{3}{5}. Therefore, the minimum value is \frac{3}{5}, so print this value multiplied by 5, which is 3.

### Sample Input 2

5 1
0 0 1 0 0


### Sample Output 2

0


### Sample Input 3

1 1
100


### Sample Output 3

0


### Sample Input 4

20 7
4262 9522 2426 3823 7364 964 2743 2423 1955 5274 3684 847 363 35 278 3220 203 2904 6304 1928


### Sample Output 4

22809