Problem Statement

Three people live in Takahashi's house: Takahashi, his father, and his mother. All of them wash their hair in the bathroom each night.
His father, his mother, and Takahashi take a bath in this order and use A, B, and C milliliters of shampoo, respectively.

This morning, the bottle contained V milliliters of shampoo. Without refilling, who will be the first to run short of shampoo to wash their hair?

Constraints

• 1 \leq V,A,B,C \leq 10^5
• All values in input are integers.

Sample Input 1

25 10 11 12

Sample Output 1

T

Now, they have 25 milliliters of shampoo.

• First, Takahashi's father uses 10 milliliters, leaving 15.
• Next, Takahashi's mother uses 11 milliliters, leaving 4.
• Finally, Takahashi tries to use 12 milliliters and runs short of shampoo since only 4 is remaining.

Sample Input 2

30 10 10 10

Sample Output 2

F

Now, they have 30 milliliters of shampoo.

• First, Takahashi's father uses 10 milliliters, leaving 20.
• Next, Takahashi's mother uses 10 milliliters, leaving 10.
• Then, Takahashi uses 10 milliliters, leaving 0.
• Next day, Takahashi's father tries to use 10 milliliters and runs short of shampoo since only 0 is remaining.

Sample Input 3

100000 1 1 1

Sample Output 3

M

Problem Statement

Find the X-th character from the beginning of the string that is obtained by concatenating these characters: N copies of A's, N copies of B's, …, and N copies of Z's, in this order.

Constraints

• 1 \leq N \leq 100
• 1 \leq X \leq N\times 26
• All values in input are integers.

Sample Input 1

1 3

Sample Output 1

C

We obtain the string ABCDEFGHIJKLMNOPQRSTUVWXYZ, whose 3-rd character from the beginning is C.

Sample Input 2

2 12

Sample Output 2

F

We obtain the string AABBCCDDEEFFGGHHIIJJKKLLMMNNOOPPQQRRSSTTUUVVWWXXYYZZ, whose 12-th character from the beginning is F.

Problem Statement

A string S is said to be a substring of a string T when there is a pair of integers i and j (1 \leq i \leq j \leq |T|) that satisfy the following condition.

• The extraction of the i-th through j-th characters of T without changing the order equals S.

Let T be the concatenation of 10^5 copies of oxx.
Given a string S, print Yes if S is a substring of T, and No otherwise.

Constraints

• S is a string consisting of o and x.
• The length of S is between 1 and 10 (inclusive).

Sample Input 1

xoxxoxxo

Sample Output 1

Yes

T begins like this: oxxoxxoxxoxx... Since the extraction of 3-rd through 10-th characters of T equals S, S is a substring of T, so Yes should be printed.

Sample Input 2

xxoxxoxo

Sample Output 2

No

Since there is no way to extract from T a string that equals S, S is not a substring of T, so No should be printed.

Sample Input 3

ox

Sample Output 3

Yes

Problem Statement

You are given a string S consisting of uppercase English letters and digits. Determine whether S satisfies the following condition.

• S is a concatenation of the following characters and string in the order listed.
  • An uppercase English letter
  • A string of length 6 that is a decimal representation of an integer between 100000 and 999999, inclusive
  • An uppercase English letter

Constraints

• S consists of uppercase English letters and digits.
• The length of S is between 1 and 10, inclusive.

Sample Input 1

Q142857Z

Sample Output 1

Yes

S is a concatenation of Q, 142857, and Z in this order.
Q and Z are uppercase English letters, and 142857 is a string of length 6 that is a decimal representation of an integer between 100000 and 999999, so S satisfies the condition.

Sample Input 2

AB912278C

Sample Output 2

No

AB is not an uppercase English letter, so S does not satisfy the condition.

Sample Input 3

X900000

Sample Output 3

No

The last character of S is not an uppercase English letter, so S does not satisfy the condition.

Sample Input 4

K012345K

Sample Output 4

No

012345 is not a string of length 6 that is a decimal representation of an integer between 100000 and 999999, so S does not satisfy the condition.

Problem Statement

You are given a sequence a = (a_1, \dots, a_N) of length N consisting of integers between 1 and N.

Find the number of pairs of integers i, j that satisfy all of the following conditions:

• 1 \leq i \lt j \leq N
• \min(a_i, a_j) = i
• \max(a_i, a_j) = j

Constraints

• 2 \leq N \leq 5 \times 10^5
• 1 \leq a_i \leq N \, (1 \leq i \leq N)
• All values in input are integers.

Sample Input 1

4
1 3 2 4

Sample Output 1

2

(i, j) = (1, 4), (2, 3) satisfy the conditions.

Sample Input 2

10
5 8 2 2 1 6 7 2 9 10

Sample Output 2

8

Problem Statement

We have a sequence of N positive integers: A=(A_1,\dots,A_N).
Let B be the concatenation of 10^{100} copies of A.

Consider summing up the terms of B from left to right. When does the sum exceed X for the first time?
In other words, find the minimum integer k such that:

\displaystyle{\sum_{i=1}^{k} B_i \gt X}.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq A_i \leq 10^9
• 1 \leq X \leq 10^{18}
• All values in input are integers.

Sample Input 1

3
3 5 2
26

Sample Output 1

8

We have B=(3,5,2,3,5,2,3,5,2,\dots).
\displaystyle{\sum_{i=1}^{8} B_i = 28 \gt 26} holds, but the condition is not satisfied when k is 7 or less, so the answer is 8.

Sample Input 2

4
12 34 56 78
1000

Sample Output 2

23

Problem Statement

Takahashi is hosting a contest with N players numbered 1 to N. The players will compete for points. Currently, all players have zero points.

Takahashi's foreseeing ability lets him know how the players' scores will change. Specifically, for i=1,2,\dots,T, the score of player A_i will increase by B_i points at i seconds from now. There will be no other change in the scores.

Takahashi, who prefers diversity in scores, wants to know how many different score values will appear among the players' scores at each moment. For each i=1,2,\dots,T, find the number of different score values among the players' scores at i+0.5 seconds from now.

For example, if the players have 10, 20, 30, and 20 points at some moment, there are three different score values among the players' scores at that moment.

Constraints

• 1\leq N, T\leq 2\times 10^5
• 1\leq A_i \leq N
• 1\leq B_i \leq 10^9
• All input values are integers.

Sample Input 1

3 4
1 10
3 20
2 10
2 10

Sample Output 1

2
3
2
2

Let S be the sequence of scores of players 1, 2, 3 in this order. Currently, S=\lbrace 0,0,0\rbrace.

• After one second, the score of player 1 increases by 10 points, making S=\lbrace 10,0,0\rbrace. Thus, there are two different score values among the players' scores at 1.5 seconds from now.
• After two seconds, the score of player 3 increases by 20 points, making S=\lbrace 10,0,20\rbrace. Thus, there are three different score values among the players' scores at 2.5 seconds from now.
• After three seconds, the score of player 2 increases by 10 points, making S=\lbrace 10,10,20\rbrace. Therefore, there are two different score values among the players' scores at 3.5 seconds from now.
• After four seconds, the score of player 2 increases by 10 points, making S=\lbrace 10,20,20\rbrace. Therefore, there are two different score values among the players' scores at 4.5 seconds from now.

Sample Input 2

1 3
1 3
1 4
1 3

Sample Output 2

1
1
1

Sample Input 3

10 10
7 2620
9 2620
8 3375
1 3375
6 1395
5 1395
6 2923
10 3375
9 5929
5 1225

Sample Output 3

2
2
3
3
4
4
5
5
6
5

Problem Statement

We have a number sequence A = (A_1, A_2, \dots, A_N) of length N and integers X and Y. Find the number of pairs of integers (L, R) satisfying all the conditions below.

• 1 \leq L \leq R \leq N
• The maximum value of A_L, A_{L+1}, \dots, A_R is X, and the minimum is Y.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 2 \times 10^5
• 1 \leq Y \leq X \leq 2 \times 10^5
• All values in input are integers.

Sample Input 1

4 3 1
1 2 3 1

Sample Output 1

4

4 pairs satisfy the conditions: (L,R)=(1,3),(1,4),(2,4),(3,4).

Sample Input 2

5 2 1
1 3 2 4 1

Sample Output 2

0

No pair (L,R) satisfies the condition.

Sample Input 3

5 1 1
1 1 1 1 1

Sample Output 3

15

It may hold that X=Y.

Sample Input 4

10 8 1
2 7 1 8 2 8 1 8 2 8

Sample Output 4

36

Problem Statement

There is a grid with N rows and N columns. We denote by (i, j) the square at the i-th (1 \leq i \leq N) row from the top and j-th (1 \leq j \leq N) column from the left.
Square (i, j) has a non-negative integer a_{i, j} written on it.

When you are at square (i, j), you can move to either square (i+1, j) or (i, j+1). Here, you are not allowed to go outside the grid.

Find the number of ways to travel from square (1, 1) to square (N, N) such that the exclusive logical sum of the integers written on the squares visited (including (1, 1) and (N, N)) is 0.

Constraints

• 2 \leq N \leq 20
• 0 \leq a_{i, j} \lt 2^{30} \, (1 \leq i, j \leq N)
• All values in the input are integers.

Sample Input 1

3
1 5 2
7 0 5
4 2 3

Sample Output 1

2

The following two ways satisfy the condition:

• (1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3);
• (1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3).

Sample Input 2

2
1 2
2 1

Sample Output 2

0

Sample Input 3

10
1 0 1 0 0 1 0 0 0 1
0 0 0 1 0 1 0 1 1 0
1 0 0 0 1 0 1 0 0 0
0 1 0 0 0 1 1 0 0 1
0 0 1 1 0 1 1 0 1 0
1 0 0 0 1 0 0 1 1 0
1 1 1 0 0 0 1 1 0 0
0 1 1 0 0 1 1 0 1 0
1 0 1 1 0 0 0 0 0 0
1 0 1 1 0 0 1 1 1 0

Sample Output 3

24307