Problem Statement

There are N people labeled 1 to N, who have played several one-on-one games without draws. Initially, each person started with 0 points. In each game, the winner's score increased by 1 and the loser's score decreased by 1 (scores can become negative). Determine the final score of person N if the final score of person i\ (1\leq i\leq N-1) is A_i. It can be shown that the final score of person N is uniquely determined regardless of the sequence of games.

Constraints

• 2 \leq N \leq 100
• -100 \leq A_i \leq 100
• All input values are integers.

Sample Input 1

4
1 -2 -1

Sample Output 1

2

Here is one possible sequence of games where the final scores of persons 1, 2, 3 are 1, -2, -1, respectively.

• Initially, persons 1, 2, 3, 4 have 0, 0, 0, 0 points, respectively.
• Persons 1 and 2 play, and person 1 wins. The players now have 1, -1, 0, 0 point(s).
• Persons 1 and 4 play, and person 4 wins. The players now have 0, -1, 0, 1 point(s).
• Persons 1 and 2 play, and person 1 wins. The players now have 1, -2, 0, 1 point(s).
• Persons 2 and 3 play, and person 2 wins. The players now have 1, -1, -1, 1 point(s).
• Persons 2 and 4 play, and person 4 wins. The players now have 1, -2, -1, 2 point(s).

In this case, the final score of person 4 is 2. Other possible sequences of games exist, but the score of person 4 will always be 2 regardless of the progression.

Sample Input 2

3
0 0

Sample Output 2

0

Sample Input 3

6
10 20 30 40 50

Sample Output 3

-150

Problem Statement

In the figure shown in the image below, are the points numbered a and b directly connected by a line segment?

Constraints

• 1 \leq a \lt b \leq 10
• a and b are integers.

Sample Input 1

4 5

Sample Output 1

Yes

In the figure shown in the Problem Statement, the points numbered 4 and 5 are directly connected by a line segment.
Thus, Yes should be printed.

Sample Input 2

3 5

Sample Output 2

No

In the figure shown in the Problem Statement, the points numbered 3 and 5 are not directly connected by a line segment.
Thus, No should be printed.

Sample Input 3

1 10

Sample Output 3

Yes

Problem Statement

There are N people numbered 1 to N.

Person i guessed the building area of KEYENCE headquarters building to be S_i square meters.

The shape of KEYENCE headquarters building is shown below, where a and b are some positive integers.
That is, the building area of the building can be represented as 4ab+3a+3b.

Based on just this information, how many of the N people are guaranteed to be wrong in their guesses?

Constraints

• 1 \leq N \leq 20
• 1 \leq S_i \leq 1000
• All values in input are integers.

Sample Input 1

3
10 20 39

Sample Output 1

1

The area would be 10 square meters if a=1,b=1, and 39 square meters if a=2,b=3.

However, no pair of positive integers a and b would make the area 20 square meters.

Thus, we can only be sure that Person 2 guessed wrong.

Sample Input 2

5
666 777 888 777 666

Sample Output 2

3

Problem Statement

There are N people numbered 1, 2, \dots, N in the xy-plane. Person i is at the coordinates (X_i, Y_i).
K of these people, Persons A_1, A_2, \dots, A_K, will receive lights of the same strength.
When a person at coordinates (x, y) has a light of strength R, it lights up the interior of a circle of radius R centered at (x, y) (including the boundary).
Find the minimum strength of the lights needed for every person to be lit by at least one light.

Constraints

• All values in input are integers.
• 1 \le K < N \le 1000
• 1 \le A_1 < A_2 < \dots < A_K \le N
• |X_i|,|Y_i| \le 10^5
• (X_i,Y_i) \neq (X_j,Y_j), if i \neq j.

Sample Input 1

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

Sample Output 1

2.23606797749978969

This input contains four people. Among them, Persons 2 and 3 will have lights.
Every person will be lit by at least one light if R \ge \sqrt{5} \approx 2.236068.

Sample Input 2

2 1
2
-100000 -100000
100000 100000

Sample Output 2

282842.712474619009

Sample Input 3

8 3
2 6 8
-17683 17993
93038 47074
58079 -57520
-41515 -89802
-72739 68805
24324 -73073
71049 72103
47863 19268

Sample Output 3

130379.280458974768

Problem Statement

We have a sequence of N numbers: A = (a_1, a_2, \dots, a_N).
Process the Q queries explained below.

• Query i: You are given a pair of integers (x_i, k_i). Let us look at the elements of A one by one from the beginning: a_1, a_2, \dots Which element will be the k_i-th occurrence of the number x_i?
  Print the index of that element, or -1 if there is no such element.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 0 \leq a_i \leq 10^9 (1 \leq i \leq N)
• 0 \leq x_i \leq 10^9 (1 \leq i \leq Q)
• 1 \leq k_i \leq N (1 \leq i \leq Q)
• All values in input are integers.

Sample Input 1

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

Sample Output 1

1
2
5
-1
3
6
-1
-1

1 occurs in A at a_1, a_2, a_5. Thus, the answers to Query 1 through 4 are 1, 2, 5, -1 in this order.

Sample Input 2

3 2
0 1000000000 999999999
1000000000 1
123456789 1

Sample Output 2

2
-1

Problem Statement

There are N types of beans, one bean of each type. The i-th type of bean has a deliciousness of A_i and a color of C_i. The beans are mixed and can only be distinguished by color.

You will choose one color of beans and eat one bean of that color. By selecting the optimal color, maximize the minimum possible deliciousness of the bean you eat.

Constraints

• 1 \leq N \leq 2 \times 10^{5}
• 1 \leq A_i \leq 10^{9}
• 1 \leq C_i \leq 10^{9}
• All input values are integers.

Sample Input 1

4
100 1
20 5
30 5
40 1

Sample Output 1

40

Note that beans of the same color cannot be distinguished from each other.

You can choose color 1 or color 5.

• There are two types of beans of color 1, with deliciousness of 100 and 40. Thus, the minimum deliciousness when choosing color 1 is 40.
• There are two types of beans of color 5, with deliciousness of 20 and 30. Thus, the minimum deliciousness when choosing color 5 is 20.

To maximize the minimum deliciousness, you should choose color 1, so print the minimum deliciousness in that case: 40.

Sample Input 2

10
68 3
17 2
99 2
92 4
82 4
10 3
100 2
78 1
3 1
35 4

Sample Output 2

35

Problem Statement

Solve the following problem for T test cases.

Given are non-negative integers a and s. Is there a pair of non-negative integers (x,y) that satisfies both of the conditions below?

• x\ \text{AND}\ y=a
• x+y=s

Constraints

• 1 \leq T \leq 10^5
• 0 \leq a,s \lt 2^{60}
• All values in input are integers.

Sample Input 1

2
1 8
4 2

Sample Output 1

Yes
No

In the first test case, some pairs such as (x,y)=(3,5) satisfy the conditions.

In the second test case, no pair of non-negative integers satisfies the conditions.

Sample Input 2

4
201408139683277485 381410962404666524
360288799186493714 788806911317182736
18999951915747344 451273909320288229
962424162689761932 1097438793187620758

Sample Output 2

No
Yes
Yes
No

Problem Statement

A "Snowflake Tree" is defined as a tree that can be generated by the following procedure:

1. Choose positive integers x,y.
2. Prepare one vertex.
3. Prepare x more vertices, and connect each of them to the vertex prepared in step 2.
4. For each of the x vertices prepared in step 3, attach y leaves to it.

The figure below shows a Snowflake Tree with x=4,y=2. The vertices prepared in steps 2, 3, 4 are shown in red, blue, and green, respectively.

You are given a tree T with N vertices. The vertices are numbered 1 to N, and the i-th edge (i=1,2,\dots,N-1) connects vertices u_i and v_i.

Consider deleting zero or more vertices of T and the edges adjacent to them so that the remaining graph becomes a single Snowflake Tree. Find the minimum number of vertices that must be deleted. Under the constraints of this problem, it is always possible to transform T into a Snowflake Tree.

Constraints

• 3 \leq N \leq 3 \times 10^5
• 1 \leq u_i < v_i \leq N
• The given graph is a tree.
• All input values are integers.

Sample Input 1

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

Sample Output 1

1

By deleting vertex 8, the given tree can be transformed into a Snowflake Tree with x=2,y=2.

Sample Input 2

3
1 2
2 3

Sample Output 2

0

The given tree is already a Snowflake Tree with x=1,y=1.

Sample Input 3

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

Sample Output 3

3

Problem Statement

A monster with health H has appeared in front of you, and a turn-based battle has started.

In each turn 1,2,…, you cast one of N spells, spells 1,…,N.

If you cast spell i in turn j, the monster's health reduces by d_i in each turn j,j+1,…,j+t_i －1.

Find the earliest turn that you can make the monster's health 0 or less.

Constraints

• 1 \leq N \leq 3 \times 10^5
• 1 \leq H \leq 10^{18}
• 1 \leq t_i,d_i \leq 10^9
• All values in the input are integers.

Sample Input 1

2 20
2 2
5 1

Sample Output 1

6

The following procedure makes the monster's health 0 or less in turn 6, which is the earliest.

• Cast spell 1 in turn 1. Due to the spell cast in turn 1, the monster's health reduces by 2 and becomes 18.
• Cast spell 2 in turn 2. Due to the spells cast in turns 1 and 2, the monster's health reduces by 2+1=3 and becomes 15.
• Cast spell 1 in turn 3. Due to the spells cast in turns 2 and 3, the monster's health reduces by 1+2=3 and becomes 12.
• Cast spell 2 in turn 4. Due to the spells cast in turns 2,3 and 4, the monster's health reduces by 1+2+1=4 and becomes 8.
• Cast spell 1 in turn 5. Due to the spells cast in turns 2,4 and 5, the monster's health reduces by 1+1+2=4 and becomes 4.
• Cast spell 2 in turn 6. Due to the spells cast in turns 2,4,5 and 6, the monster's health reduces by 1+1+2+1=5 and becomes -1.

Sample Input 2

10 200
1 21
1 1
1 1
8 4
30 1
3 1
10 2
8 1
9 1
4 4

Sample Output 2

9