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

Takahashi likes full moons.

Let today be day 1. The first day on or after today on which he can see a full moon is day M. After that, he can see a full moon every P days, that is, on day M+P, day M+2P, and so on.

Find the number of days between day 1 and day N, inclusive, on which he can see a full moon.

Constraints

• 1\leq N\leq 2\times 10^5
• 1\leq M \leq P \leq 2\times 10^5
• All input values are integers.

Sample Input 1

13 3 5

Sample Output 1

3

He can see a full moon on day 3, 8, 13, 18, and so on.

From day 1 to 13, he can see a full moon on three days: day 3, 8, and 13.

Sample Input 2

5 6 6

Sample Output 2

0

There may be no days he can see a full moon.

Sample Input 3

200000 314 318

Sample Output 3

628

Problem Statement

You are given a string S consisting of lowercase and uppercase English letters. The length of S is odd.
If the number of uppercase letters in S is greater than the number of lowercase letters, convert all lowercase letters in S to uppercase.
Otherwise, convert all uppercase letters in S to lowercase.

Constraints

• S is a string consisting of lowercase and uppercase English letters.
• The length of S is an odd number between 1 and 99, inclusive.

Sample Input 1

AtCoder

Sample Output 1

atcoder

The string AtCoder contains five lowercase letters and two uppercase letters. Thus, convert all uppercase letters in AtCoder to lowercase, which results in atcoder.

Sample Input 2

SunTORY

Sample Output 2

SUNTORY

The string SunTORY contains two lowercase letters and five uppercase letters. Thus, convert all lowercase letters in SunTORY to uppercase, which results in SUNTORY.

Sample Input 3

a

Sample Output 3

a

Problem Statement

There are N sequences of integers.
The i-th (1 \leq i \leq N) sequence has L_i terms; the j-th (1 \leq j \leq L_i) term of the i-th sequence is a_{i, j}.

You are given Q queries. For the k-th (1 \leq k \leq Q) query, given integers s_k and t_k, find the t_k-th term of the s_k-th sequence.

Constraints

• 1 \leq N, Q \leq 2 \times 10^5
• L_i \geq 1 \, (1 \leq i \leq N)
• \sum_{i=1}^N L_i \leq 2 \times 10^5
• 1 \leq a_{i, j} \leq 10^9 \, (1 \leq i \leq N, 1 \leq j \leq L_i)
• 1 \leq s_k \leq N, 1 \leq t_k \leq L_{s_k} \, (1 \leq k \leq Q)
• All values in the input are integers.

Sample Input 1

2 2
3 1 4 7
2 5 9
1 3
2 1

Sample Output 1

7
5

The 1-st sequence is (1, 4, 7) and the 2-nd is (5, 9).
The answer to each query is as follows:

• The 3-rd term of the 1-st sequence is 7.
• The 1-st term of the 2-nd sequence is 5.

Sample Input 2

3 4
4 128 741 239 901
2 1 1
3 314 159 26535
1 1
2 2
3 3
1 4

Sample Output 2

128
1
26535
901

Problem Statement

There is a tree T with N vertices. The i-th edge (1\leq i\leq N-1) connects vertex U_i and vertex V_i.

You are given two different vertices X and Y in T. List all vertices along the simple path from vertex X to vertex Y in order, including endpoints.

It can be proved that, for any two different vertices a and b in a tree, there is a unique simple path from a to b.

Constraints

• 1\leq N\leq 2\times 10^5
• 1\leq X,Y\leq N
• X\neq Y
• 1\leq U_i,V_i\leq N
• All values in the input are integers.
• The given graph is a tree.

Sample Input 1

5 2 5
1 2
1 3
3 4
3 5

Sample Output 1

2 1 3 5

The tree T is shown below. The simple path from vertex 2 to vertex 5 is 2 \to 1 \to 3 \to 5.
Thus, 2,1,3,5 should be printed in this order, with spaces in between.

Sample Input 2

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

Sample Output 2

1 2

The tree T is shown below.

Problem Statement

Person 0, Person 1, \ldots, and Person (N-1) are sitting around a turntable in their counterclockwise order, evenly spaced. Dish p_i is in front of Person i on the table.
You may perform the following operation 0 or more times:

• Rotate the turntable by one N-th of a counterclockwise turn. As a result, the dish that was in front of Person i right before the rotation is now in front of Person (i+1) \bmod N.

When you are finished, Person i is happy if Dish i is in front of Person (i-1) \bmod N, Person i, or Person (i+1) \bmod N.
Find the maximum possible number of happy people.

Constraints

• 3 \leq N \leq 2 \times 10^5
• 0 \leq p_i \leq N-1
• p_i \neq p_j if i \neq j.
• All values in input are integers.

Sample Input 1

4
1 2 0 3

Sample Output 1

4

The figure below shows the table after one operation.

Here, there are four happy people:

• Person 0 is happy because Dish 0 is in front of Person 3\ (=(0-1) \bmod 4);
• Person 1 is happy because Dish 1 is in front of Person 1\ (=1);
• Person 2 is happy because Dish 2 is in front of Person 2\ (=2);
• Person 3 is happy because Dish 3 is in front of Person 0\ (=(3+1) \bmod 4).

There cannot be five or more happy people, so the answer is 4.

Sample Input 2

3
0 1 2

Sample Output 2

3

Sample Input 3

10
3 9 6 1 7 2 8 0 5 4

Sample Output 3

5

Problem Statement

A shop sells N kinds of lunchboxes, one for each kind.
For each i = 1, 2, \ldots, N, the i-th kind of lunchbox contains A_i takoyaki (octopus balls) and B_i taiyaki (fish-shaped cakes).

Takahashi wants to eat X or more takoyaki and Y or more taiyaki.
Determine whether it is possible to buy some number of lunchboxes to get at least X takoyaki and at least Y taiyaki. If it is possible, find the minimum number of lunchboxes that Takahashi must buy to get them.

Note that just one lunchbox is in stock for each kind; you cannot buy two or more lunchboxes of the same kind.

Constraints

• 1 \leq N \leq 300
• 1 \leq X, Y \leq 300
• 1 \leq A_i, B_i \leq 300
• All values in input are integers.

Sample Input 1

3
5 6
2 1
3 4
2 3

Sample Output 1

2

He wants to eat 5 or more takoyaki and 6 or more taiyaki.
Buying the second and third lunchboxes will get him 3 + 2 = 5 taiyaki and 4 + 3 = 7 taiyaki.

Sample Input 2

3
8 8
3 4
2 3
2 1

Sample Output 2

-1

Even if he is to buy every lunchbox, it is impossible to get at least 8 takoyaki and at least 8 taiyaki.
Thus, print -1.

Problem Statement

Given integers A, X, and M, find \displaystyle \sum_{i = 0}^{X-1} A^i, modulo M.

Constraints

• 1 \leq A, M \leq 10^9
• 1 \leq X \leq 10^{12}
• All values in the input are integers.

Sample Input 1

3 4 7

Sample Output 1

5

3^0 + 3^1 + 3^2 + 3^3 = 40, which equals 5 modulo 7, so 5 should be printed.

Sample Input 2

8 10 9

Sample Output 2

0

Sample Input 3

1000000000 1000000000000 998244353

Sample Output 3

919667211

Problem Statement

You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N.

For each integer pair (L,R) with 1 \le L \le R \le N, define f(L,R) as follows:

• Start with an empty blackboard. Write the R-L+1 integers A_L, A_{L+1}, \ldots, A_R on the blackboard in order.
• Repeat the following operation until all integers on the blackboard are erased:
  • Choose integers l, r with l \le r such that every integer from l through r appears at least once on the blackboard. Then, erase all integers from l through r that are on the blackboard.
• Let f(L,R) be the minimum number of such operations needed to erase all the integers from the blackboard.

Find \displaystyle \sum_{L=1}^N \sum_{R=L}^N f(L,R).

Constraints

• 1 \le N \le 3 \times 10^5
• 1 \le A_i \le N
• All input values are integers.

Sample Input 1

4
1 3 1 4

Sample Output 1

16

For example, in the case of (L,R)=(1,4):

• The blackboard has 1,3,1,4.
• Choose (l,r)=(1,1) and erase all occurrences of 1. The blackboard now has 3,4.
• Choose (l,r)=(3,4) and erase all occurrences of 3 and 4. The blackboard becomes empty.
• It cannot be done in fewer than two operations, so f(1,4) = 2.

Similarly, you can find f(2,4)=2, f(1,1)=1, etc.

\displaystyle \sum_{L=1}^N \sum_{R=L}^N f(L,R) = 16, so print 16.

Sample Input 2

5
3 1 4 2 4

Sample Output 2

23

Sample Input 3

10
5 1 10 9 2 5 6 9 1 6

Sample Output 3

129