Problem Statement

Takahashi, a young baseball enthusiast, has been a very good boy this year, so Santa has decided to give him a bat or a glove, whichever is more expensive.

If a bat costs B yen and a glove costs G yen (B\neq G), which one will Santa give to Takahashi?

Constraints

• B and G are different integers between 1 and 1000, inclusive.

Sample Input 1

300 100

Sample Output 1

Bat

The bat is more expensive than the glove, so Santa will give Takahashi the bat.

Sample Input 2

334 343

Sample Output 2

Glove

The glove is more expensive than the bat, so Santa will give Takahashi the glove.

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

N players numbered 1 to N will play a soccer game.
When a player commits an offense, that player will receive a yellow card or a red card.
A player who satisfies one of the following conditions will be removed from the game.

• Accumulates two yellow cards.
• Receives a red card.

Once a player is removed, that player will no longer receive any cards.

You will watch this game. Initially, the players have not received any cards.
There will be Q events. Correctly answer the questions asked in the events.
There are three kinds of events, which are given in the format c x from the input, where c is 1, 2, or 3. The events are as follows.

• 1 x: Player x receives a yellow card.
• 2 x: Player x receives a red card.
• 3 x: You are asked whether player x has been removed from the game. Answer Yes or No.

Constraints

• 1 \leq N \leq 100
• 1 \leq Q \leq 100
• 1 \leq x \leq N in all events.
• There is at least one event of the third kind.
• A player who has been removed will no longer receive any cards.
• All values in the input are integers.

Sample Input 1

3 9
3 1
3 2
1 2
2 1
3 1
3 2
1 2
3 2
3 3

Sample Output 1

No
No
Yes
No
Yes
No

Here are all the events in chronological order.

In the 1-st event, you are asked whether player 1 has been removed from the game. Player 1 has not been removed, so you should print No.
In the 2-nd event, you are asked whether player 2 has been removed from the game. Player 2 has not been removed, so you should print No.
In the 3-rd event, player 2 receives a yellow card.
In the 4-th event, player 1 receives a red card and is removed from the game.
In the 5-th event, you are asked whether player 1 has been removed from the game. Player 1 has been removed, so you should print Yes.
In the 6-th event, you are asked whether player 2 has been removed from the game. Player 2 has not been removed, so you should print No.
In the 7-th event, player 2 receives a yellow card and is removed from the game.
In the 8-th event, you are asked whether player 2 has been removed from the game. Player 2 has been removed, so you should print Yes.
In the 9-th event, you are asked whether player 3 has been removed from the game. Player 3 has not been removed, so you should print No.

Problem Statement

You are given a sequence of N positive integers A = (A_1, A_2, \dots ,A_N). Takahashi repeats the following operation until A contains one or fewer positive elements:

• Sort A in descending order. Then, decrease both A_1 and A_2 by 1.

Find the number of times he performs this operation.

Constraints

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

Sample Input 1

4
1 2 3 3

Sample Output 1

4

The process goes as follows:

• After the 1st operation, A is (2, 2, 2, 1).
• After the 2nd operation, A is (1, 1, 2, 1).
• After the 3rd operation, A is (1, 0, 1, 1).
• After the 4th operation, A is (0, 0, 1, 0). A no longer contains more than one positive elements, so the process ends here.

Sample Input 2

3
1 1 100

Sample Output 2

2

Problem Statement

The AtCoder Kingdom holds a festival for N days. On M of these days, namely on the A_1-th, A_2-th, \dots, A_M-th days, fireworks will be launched. It is guaranteed that fireworks will be launched on the last day of the festival. (In other words, A_M=N is guaranteed.)

For each i=1,2,\dots,N, solve the following problem.

• How many days later from the i-th day will fireworks be launched for the first time on or after the i-th day? If fireworks are launched on the i-th day, it is considered to be 0 days later.

Constraints

• 1 \le M \le N \le 2 \times 10^5
• 1 \le A_1 < A_2 < \dots < A_M = N
• All input values are integers.

Sample Input 1

3 2
2 3

Sample Output 1

1
0
0

The kingdom holds a festival for 3 days, and fireworks are launched on the 2-nd and 3-rd days.

• From the 1-st day, the first time fireworks are launched is the 2-nd day of the festival, which is 1 day later.
• From the 2-nd day, the first time fireworks are launched is the 2-nd day of the festival, which is 0 days later.
• From the 3-rd day, the first time fireworks are launched is the 3-rd day of the festival, which is 0 days later.

Sample Input 2

8 5
1 3 4 7 8

Sample Output 2

0
1
0
0
2
1
0
0

Problem Statement

On an xy-coordinate plane, is there a lattice point whose distances from two lattice points (x_1, y_1) and (x_2, y_2) are both \sqrt{5}?

Notes

A point on an xy-coordinate plane whose x and y coordinates are both integers is called a lattice point.
The distance between two points (a, b) and (c, d) is defined to be the Euclidean distance between them, \sqrt{(a - c)^2 + (b-d)^2}.

The following figure illustrates an xy-plane with a black circle at (0, 0) and white circles at the lattice points whose distances from (0, 0) are \sqrt{5}. (The grid shows where either x or y is an integer.)

Constraints

• -10^9 \leq x_1 \leq 10^9
• -10^9 \leq y_1 \leq 10^9
• -10^9 \leq x_2 \leq 10^9
• -10^9 \leq y_2 \leq 10^9
• (x_1, y_1) \neq (x_2, y_2)
• All values in input are integers.

Sample Input 1

0 0 3 3

Sample Output 1

Yes

• The distance between points (2,1) and (x_1, y_1) is \sqrt{(0-2)^2 + (0-1)^2} = \sqrt{5};
• the distance between points (2,1) and (x_2, y_2) is \sqrt{(3-2)^2 + (3-1)^2} = \sqrt{5};
• point (2, 1) is a lattice point,

so point (2, 1) satisfies the condition. Thus, Yes should be printed.
One can also assert in the same way that (1, 2) also satisfies the condition.

Sample Input 2

0 1 2 3

Sample Output 2

No

No lattice point satisfies the condition, so No should be printed.

Sample Input 3

1000000000 1000000000 999999999 999999999

Sample Output 3

Yes

Point (10^9 + 1, 10^9 - 2) and point (10^9 - 2, 10^9 + 1) satisfy the condition.

Problem Statement

You are given positive integers N and M.
Find the smallest positive integer X that satisfies both of the conditions below, or print -1 if there is no such integer.

• X can be represented as the product of two integers a and b between 1 and N, inclusive. Here, a and b may be the same.
• X is at least M.

Constraints

• 1\leq N\leq 10^{12}
• 1\leq M\leq 10^{12}
• N and M are integers.

Sample Input 1

5 7

Sample Output 1

8

First, 7 cannot be represented as the product of two integers between 1 and 5.
Second, 8 can be represented as the product of two integers between 1 and 5, such as 8=2\times 4.

Thus, you should print 8.

Sample Input 2

2 5

Sample Output 2

-1

Since 1\times 1=1, 1\times 2=2, 2\times 1=2, and 2\times 2=4, only 1, 2, and 4 can be represented as the product of two integers between 1 and 2, so no number greater than or equal to 5 can be represented as the product of two such integers.
Thus, you should print -1.

Sample Input 3

100000 10000000000

Sample Output 3

10000000000

For a=b=100000 (=10^5), the product of a and b is 10000000000 (=10^{10}), which is the answer.
Note that the answer may not fit into a 32-bit integer type.

Problem Statement

There are N integers a_1,\ldots,a_N written on a whiteboard.
Here, a_i can be represented as a_i = p_{i,1}^{e_{i,1}} \times \ldots \times p_{i,m_i}^{e_{i,m_i}} using m_i prime numbers p_{i,1} \lt \ldots \lt p_{i,m_i} and positive integers e_{i,1},\ldots,e_{i,m_i}.
You will choose one of the N integers to replace it with 1.
Find the number of values that can be the least common multiple of the N integers after the replacement.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq m_i
• \sum{m_i} \leq 2 \times 10^5
• 2 \leq p_{i,1} \lt \ldots \lt p_{i,m_i} \leq 10^9
• p_{i,j} is prime.
• 1 \leq e_{i,j} \leq 10^9
• All values in input are integers.

Sample Input 1

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

Sample Output 1

3

The integers on the whiteboard are a_1 =7^2=49, a_2=2^2 \times 5^1 = 20, a_3 = 5^1 = 5, a_4=2^1 \times 7^1 = 14.
If you replace a_1 with 1, the integers on the whiteboard become 1,20,5,14, whose least common multiple is 140.
If you replace a_2 with 1, the integers on the whiteboard become 49,1,5,14, whose least common multiple is 490.
If you replace a_3 with 1, the integers on the whiteboard become 49,20,1,14, whose least common multiple is 980.
If you replace a_4 with 1, the integers on the whiteboard become 49,20,5,1, whose least common multiple is 980.
Therefore, the least common multiple of the N integers after the replacement can be 140, 490, or 980, so the answer is 3.

Sample Input 2

1
1
998244353 1000000000

Sample Output 2

1

There may be enormous integers on the whiteboard.

Problem Statement

Given an integer N not less than 2, find the number of integers b not less than 2 such that:

• when N is written in base b, every digit is 0 or 1.

Find the answer for T independent test cases.

It can be proved that there is a finite number of desired integers b not less than 2 under the constraints of this problem.

Constraints

• 1 \leq T \leq 1000
• 2 \leq N \leq 10^{18}
• All values in the input are integers.

Sample Input 1

3
12
2
36

Sample Output 1

4
1
5

For the first test case, four b's satisfy the condition in the problem statement: b = 2, 3, 11, 12. Indeed, when N=12 is written in base 2, 3, 11, and 12, it becomes 1100, 110, 11 and 10, respectively.