Problem Statement

KEYENCE has a culture of addressing everyone with the suffix "-san," regardless of roles, age, or positions.

You are given a string S consisting of lowercase English letters.
If S ends with san, print Yes; otherwise, print No.

Constraints

• S is a string of length between 4 and 30, inclusive, consisting of lowercase English letters.

Sample Input 1

takahashisan

Sample Output 1

Yes

The string S= takahashisan ends with san, so print Yes.

Sample Input 2

aokikun

Sample Output 2

No

The string S= aokikun does not end with san, so print No.

Problem Statement

You are given a sequence of positive integers of length N: A=(A_1,A_2,\dots,A_N).

Find the sum of the odd-indexed elements of A. That is, find A_1 + A_3 + A_5 + \dots + A_m, where m is the largest odd number not exceeding N.

Constraints

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

Sample Input 1

7
3 1 4 1 5 9 2

Sample Output 1

14

The sum of the odd-indexed elements of A is A_1+A_3+A_5+A_7=3+4+5+2=14.

Sample Input 2

1
100

Sample Output 2

100

Sample Input 3

14
100 10 1 10 100 10 1 10 100 10 1 10 100 10

Sample Output 3

403

Problem Statement

Takahashi is exploring a cave in a video game.

The cave consists of N rooms arranged in a row. The rooms are numbered Room 1,2,\ldots,N from the entrance.

Takahashi is initially in Room 1, and the time limit is T.
For each 1 \leq i \leq N-1, he may consume a time of A_i to move from Room i to Room (i+1). There is no other way to move between rooms. He cannot make a move that makes the time limit 0 or less.

There are M bonus rooms in the cave. The i-th bonus room is Room X_i; when he arrives at the room, the time limit increases by Y_i.

Can Takahashi reach Room N?

Constraints

• 2 \leq N \leq 10^5
• 0 \leq M \leq N-2
• 1 \leq T \leq 10^9
• 1 \leq A_i \leq 10^9
• 1 < X_1 < \ldots < X_M < N
• 1 \leq Y_i \leq 10^9
• All values in input are integers.

Sample Input 1

4 1 10
5 7 5
2 10

Sample Output 1

Yes

• Takahashi is initially in Room 1, and the time limit is 10.
• He consumes a time of 5 to move to Room 2. Now the time limit is 5. Then, the time limit increases by 10; it is now 15.
• He consumes a time of 7 to move to Room 3. Now the time limit is 8.
• He consumes a time of 5 to move to Room 4. Now the time limit is 3.

Sample Input 2

4 1 10
10 7 5
2 10

Sample Output 2

No

He cannot move from Room 1 to Room 2.

Problem Statement

You are given N sequences numbered 1 to N.
Sequence i has a length of L_i and its j-th element (1 \leq j \leq L_i) is a_{i,j}.

Sequence i and Sequence j are considered the same when L_i = L_j and a_{i,k} = a_{j,k} for every k (1 \leq k \leq L_i).
How many different sequences are there among Sequence 1 through Sequence N?

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq L_i \leq 2 \times 10^5 (1 \leq i \leq N)
• 0 \leq a_{i,j} \leq 10^{9} (1 \leq i \leq N, 1 \leq j \leq L_i)
• The total number of elements in the sequences, \sum_{i=1}^N L_i, does not exceed 2 \times 10^5.
• All values in input are integers.

Sample Input 1

4
2 1 2
2 1 1
2 2 1
2 1 2

Sample Output 1

3

Sample Input 1 contains four sequences:

• Sequence 1 : (1, 2)
• Sequence 2 : (1, 1)
• Sequence 3 : (2, 1)
• Sequence 4 : (1, 2)

Except that Sequence 1 and Sequence 4 are the same, these sequences are pairwise different, so we have three different sequences.

Sample Input 2

5
1 1
1 1
1 2
2 1 1
3 1 1 1

Sample Output 2

4

Sample Input 2 contains five sequences:

• Sequence 1 : (1)
• Sequence 2 : (1)
• Sequence 3 : (2)
• Sequence 4 : (1, 1)
• Sequence 5 : (1, 1, 1)

Sample Input 3

1
1 1

Sample Output 3

1

Problem Statement

We have a playlist with N songs numbered 1, \dots, N.
Song i lasts A_i seconds.

When the playlist is played, song 1, song 2, \ldots, and song N play in this order. When song N ends, the playlist repeats itself, starting from song 1 again. While a song is playing, the next song does not play; when a song ends, the next song starts immediately.

At exactly T seconds after the playlist starts playing, which song is playing? Also, how many seconds have passed since the start of that song?
There is no input where the playlist changes songs at exactly T seconds after it starts playing.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq T \leq 10^{18}
• 1 \leq A_i \leq 10^9
• The playlist does not change songs at exactly T seconds after it starts playing.
• All values in the input are integers.

Sample Input 1

3 600
180 240 120

Sample Output 1

1 60

When the playlist is played, the following happens. (Assume that it starts playing at time 0.)

• From time 0 to time 180, song 1 plays.
• From time 180 to time 420, song 2 plays.
• From time 420 to time 540, song 3 plays.
• From time 540 to time 720, song 1 plays.
• From time 720 to time 960, song 2 plays.
• \qquad\vdots

At time 600, song 1 is playing, and 60 seconds have passed since the start of that song.

Sample Input 2

3 281
94 94 94

Sample Output 2

3 93

Sample Input 3

10 5678912340
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

6 678912340

Problem Statement

You are given a string S = S_1S_2\ldots S_N of length N consisting of lowercase English letters.

Additionally, you are given Q queries about the string S. For i = 1, 2, \ldots, Q, the i-th query is represented by two integers l_i, r_i and asks the following.

In the substring S_{l_i}S_{l_i+1}\ldots S_{r_i} of S, which ranges from the l_i-th to the r_i-th character, how many places are there where the same lowercase English letter occurs twice in a row? In other words, how many integers p satisfy l_i \leq p \leq r_i-1 and S_p = S_{p+1}?

Print the answer for each of the Q queries.

Constraints

• N and Q are integers.
• 1 \leq N, Q \leq 3 \times 10^5
• S is a string of length N consisting of lowercase English letters.
• l_i and r_i are integers.
• 1 \leq l_i \leq r_i \leq N

Sample Input 1

11 4
mississippi
3 9
4 10
4 6
7 7

Sample Output 1

2
2
0
0

The answers to the four queries are as follows.

• For the first query, S_3S_4\ldots S_9 = ssissip has two places where the same lowercase English letter occurs twice in a row: S_3S_4 = ss and S_6S_7 = ss.
• For the second query, S_4S_5\ldots S_{10} = sissipp has two places where the same lowercase English letter occurs twice in a row: S_6S_7 = ss and S_9S_{10} = pp.
• For the third query, S_4S_5S_6 = sis has zero places where the same lowercase English letter occurs twice in a row.
• For the fourth query, S_7 = s has zero places where the same lowercase English letter occurs twice in a row.

Sample Input 2

5 1
aaaaa
1 5

Sample Output 2

4

S_1S_2\ldots S_5 = aaaaa has four places where the same lowercase English letter occurs twice in a row: S_1S_2 = aa, S_2S_3 = aa, S_3S_4 = aa, and S_4S_5 = aa.

Problem Statement

There is an infinitely large grid. One cell of the grid is named cell (0,0).

The cell located r cells down and c cells right from cell (0,0) is called cell (r,c).
Here, "r cells down" means "|r| cells up" when r is negative, and "c cells right" means "|c| cells left" when c is negative.

Specifically, the cells around cell (0,0) are as follows:

Initially, Takahashi is at cell (R_t,C_t) and Aoki is at cell (R_a,C_a). They will each make N moves according to strings S and T of length N consisting of U, D, L, R.
For each i, Takahashi's and Aoki's i-th moves occur simultaneously: Takahashi moves one cell up if the i-th character of S is U, down if D, left if L, and right if R; Aoki moves similarly according to the i-th character of T.

Find the number of times Takahashi and Aoki are at the same cell immediately after a move during the N moves.

Since N is very large, S and T are given in the form ((S'_1, A_1),\ldots,(S'_M,A_M)) and ((T'_1,B_1),\ldots,(T'_L,B_L)), where S is the string obtained by concatenating "A_1 copies of character S'_1, \dots, A_M copies of character S'_M" in this order, and T is given similarly.

Constraints

• -10^9 \leq R_t,C_t,R_a,C_a \leq 10^9
• 1\leq N \leq 10^{14}
• 1\leq M,L \leq 10^5
• Each of S'_i and T'_i is one of U, D, L, R.
• 1 \leq A_i,B_i \leq 10^9
• A_1+\dots+A_M=B_1+\dots+B_L=N
• All given values are integers.

Sample Input 1

0 0 4 2
3 2 1
R 2
D 1
U 3

Sample Output 1

1

In this case, S= RRD and T= UUU, and the movements proceed as follows:

• Initially, Takahashi is at cell (0,0) and Aoki is at cell (4,2).
• After the 1st move, Takahashi is at cell (0,1) and Aoki is at cell (3,2).
• After the 2nd move, Takahashi is at cell (0,2) and Aoki is at cell (2,2).
• After the 3rd move, Takahashi is at cell (1,2) and Aoki is at cell (1,2).

Thus, the number of times Takahashi and Aoki are at the same cell immediately after a move is 1.

Sample Input 2

1000000000 1000000000 -1000000000 -1000000000
3000000000 3 3
L 1000000000
U 1000000000
U 1000000000
D 1000000000
R 1000000000
U 1000000000

Sample Output 2

1000000001

From the 2000000000-th move to the 3000000000-th move, Takahashi and Aoki are at the same cell immediately after a move for 1000000001 times.

Sample Input 3

3 3 3 2
1 1 1
L 1
R 1

Sample Output 3

0

Sample Input 4

0 0 0 0
1 1 1
L 1
R 1

Sample Output 4

0

Problem Statement

AtCoder Ski Area has N open spaces called Space 1, Space 2, \ldots, Space N. The altitude of Space i is H_i. There are M slopes that connect two spaces bidirectionally. The i-th slope (1 \leq i \leq M) connects Space U_i and Space V_i. It is possible to travel between any two spaces using some slopes.

Takahashi can only travel between spaces by using slopes. Each time he goes through a slope, his happiness changes. Specifically, when he goes from Space X to Space Y by using the slope that directly connects them, his happiness changes as follows.

• If the altitude of Space X is strictly higher than that of Space Y, the happiness increases by their difference: H_X-H_Y.
• If the altitude of Space X is strictly lower than that of Space Y, the happiness decreases by their difference multiplied by 2: 2(H_Y-H_X).
• If the altitude of Space X is equal to that of Space Y, the happiness does not change.

The happiness may be a negative value.

Initially, Takahashi is in Space 1, and his happiness is 0. Find his maximum possible happiness after going through any number of slopes (possibly zero), ending in any space.

Constraints

• 2 \leq N \leq 2\times 10^5
• N-1 \leq M \leq \min( 2\times 10^5,\frac{N(N-1)}{2})
• 0 \leq H_i\leq 10^8 (1 \leq i \leq N)
• 1 \leq U_i < V_i \leq N (1 \leq i \leq M)
• (U_i,V_i) \neq (U_j, V_j) if i \neq j.
• All values in input are integers.
• It is possible to travel between any two spaces using some slopes.

Sample Input 1

4 4
10 8 12 5
1 2
1 3
2 3
3 4

Sample Output 1

3

If Takahashi takes the route Space 1 \to Space 3 \to Space 4, his happiness changes as follows.

• When going from Space 1 (altitude 10) to Space 3 (altitude 12), it decreases by 2\times (12-10)=4 and becomes 0-4=-4.
• When going from Space 3 (altitude 12) to Space 4 (altitude 5), it increases by 12-5=7 and becomes -4+7=3.

If he ends the travel here, the final happiness will be 3, which is the maximum possible value.

Sample Input 2

2 1
0 10
1 2

Sample Output 2

0

His happiness is maximized by not moving at all.

Problem Statement

There is an octopus-shaped robot and N treasures on a number line. The i-th treasure (1\leq i\leq N) is located at coordinate X_i.
The robot has one head and N legs, and the i-th leg (1\leq i\leq N) has a length of L_i.

Find the number of integers k such that the robot can grab all N treasures as follows.

• Place the head at coordinate k.
• Repeat the following for i=1,2,\ldots,N in this order: if there is a treasure that has not been grabbed yet within a distance of L_i from the head, that is, at a coordinate x satisfying k-L_i\leq x\leq k+L_i, choose one such treasure and grab it.

Constraints

• 1 \leq N\leq 200
• -10^{18} \leq X_1<X_2<\cdots<X_N\leq 10^{18}
• 1\leq L_1\leq L_2\leq\cdots\leq L_N\leq 10^{18}
• All input values are integers.

Sample Input 1

3
-6 0 7
3 5 10

Sample Output 1

6

k=-3,-2,-1,2,3,4 satisfy the condition. For example, when k=-3, the robot can grab all three treasures as follows.

• The first leg can grab treasures at coordinates x satisfying -6\leq x\leq 0. Among them, grab the first treasure at coordinate -6.
• The second leg can grab treasures at coordinates x satisfying -8\leq x\leq 2. Among them, grab the second treasure at coordinate 0.
• The third leg can grab treasures at coordinates x satisfying -13\leq x\leq 7. Among them, grab the third treasure at coordinate 7.

Sample Input 2

1
0
1000000000000000000

Sample Output 2

2000000000000000001

All integers k from -10^{18} to 10^{18} satisfy the condition.

Sample Input 3

2
-100 100
1 1

Sample Output 3

0

No k satisfies the conditions.