Problem Statement

The Eastern Army and the Western Army are at war in a certain capital.

Takahashi recorded information about the fighting forces as a string S.
S contains only the characters E and W, and the number of Es in S equals the number of soldiers in the Eastern Army, and the number of Ws equals the number of soldiers in the Western Army.

Given the string S that Takahashi recorded, output East if the Eastern Army has more soldiers than the Western Army, or West if the Western Army has more soldiers than the Eastern Army.

The length of S is guaranteed to be odd. Thus, it can be proved that exactly one of the two armies strictly outnumbers the other (that is, the two armies cannot have the same number of soldiers).

Constraints

• S is a string of length between 1 and 99, inclusive, consisting of E and W.
• The length of S is odd.

Sample Input 1

EEWEW

Sample Output 1

East

S contains three Es and two Ws, so the Eastern Army has three soldiers and the Western Army has two soldiers.
Since the Eastern Army has more soldiers than the Western Army, output East.

Sample Input 2

WWWWWWW

Sample Output 2

West

S contains zero Es and seven Ws, so the Eastern Army has zero soldiers and the Western Army has seven soldiers.
Since the Western Army has more soldiers than the Eastern Army, output West.

Problem Statement

You are given a positive integer N and two strings S and T, each of length N and consisting of lowercase English letters.

Find the Hamming distance between S and T. That is, find the number of integers i such that 1 \leq i \leq N and the i-th character of S is different from the i-th character of T.

Constraints

• 1\leq N \leq 100
• N is an integer.
• Each of S and T is a string of length N consisting of lowercase English letters.

Sample Input 1

6
abcarc
agcahc

Sample Output 1

2

S and T differ in the 2nd and 5th characters, but not in other characters. Thus, the answer is 2.

Sample Input 2

7
atcoder
contest

Sample Output 2

7

Sample Input 3

8
chokudai
chokudai

Sample Output 3

0

Sample Input 4

10
vexknuampx
vzxikuamlx

Sample Output 4

4

Problem Statement

You are given integers L, R, and a string S consisting of lowercase English letters.
Print this string after reversing (the order of) the L-th through R-th characters.

Constraints

• S consists of lowercase English letters.
• 1 \le |S| \le 10^5 (|S| is the length of S.)
• L and R are integers.
• 1 \le L \le R \le |S|

Sample Input 1

3 7
abcdefgh

Sample Output 1

abgfedch

After reversing the 3-rd through 7-th characters of abcdefgh, we have abgfedch.

Sample Input 2

1 7
reviver

Sample Output 2

reviver

The operation may result in the same string as the original.

Sample Input 3

4 13
merrychristmas

Sample Output 3

meramtsirhcyrs

Problem Statement

You are given an integer N and a sequence A=(A _ 1,A _ 2,\ldots,A _ N) of length N.

Given Q queries, process them in the given order. Each query is of one of the following two kinds:

• 1 k x : set the value A _ k to x.
• 2 k : print the value A _ k.

Constraints

• 1 \leq N \leq 10 ^ 5
• 1 \leq Q \leq 10 ^ 5
• 0 \leq A _ i \leq 10 ^ 9\ (1\leq i\leq N)
• 1\leq k\leq N for all queries.
• 0\leq x\leq 10 ^ 9 for all queries of the first kind.
• There is at least one query of the second kind.
• All values in the input are integers.

Sample Input 1

3
1 3 5
7
2 2
2 3
1 3 0
2 3
1 2 8
2 2
2 1

Sample Output 1

3
5
0
8
1

Initially, A=(1,3,5).

• For the 1-st query, A=(1,3,5), where A _ 2=3, so 3 should be printed.
• For the 2-nd query, A=(1,3,5), where A _ 3=5, so 5 should be printed.
• The 3-rd query sets the value A _ 3 to 0, making A=(1,3,0).
• For the 4-th query, A=(1,3,0), where A _ 3=0, so 0 should be printed.
• The 5-th query sets the value A _ 2 to 8, making A=(1,8,0).
• For the 6-th query, A=(1,8,0), where A _ 2=8, so 8 should be printed.
• For the 7-th query, A=(1,8,0), where A _ 1=1, so 1 should be printed.

Sample Input 2

5
22 2 16 7 30
10
1 4 0
1 5 0
2 2
2 3
2 4
2 5
1 4 100
1 5 100
2 3
2 4

Sample Output 2

2
16
0
0
16
100

Sample Input 3

7
478 369 466 343 541 42 165
20
2 1
1 7 729
1 6 61
1 6 838
1 3 319
1 4 317
2 4
1 1 673
1 3 176
1 5 250
1 1 468
2 6
1 7 478
1 5 595
2 6
1 6 599
1 6 505
2 3
2 5
2 1

Sample Output 3

478
317
838
838
176
595
468

Problem Statement

There are N people participating in an event, and the transportation cost for the i-th person is A_i yen.

Takahashi, the organizer of the event, decided to set a maximum limit x for the transportation subsidy. The subsidy for person i will be \min(x, A_i) yen. Here, x must be a non-negative integer.

Given that Takahashi's budget is M yen, and he wants the total transportation subsidy for all N people to be at most M yen, what is the maximum possible value of the subsidy limit x?

If the subsidy limit can be made infinitely large, report that instead.

Constraints

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

Sample Input 1

4 8
1 3 2 4

Sample Output 1

2

If the subsidy limit is set to 2 yen, the total transportation subsidy for all N people is \min(2,1) + \min(2,3) + \min(2,2) + \min(2,4) = 7 yen, which is within the budget of 8 yen.

If the subsidy limit is set to 3 yen, the total transportation subsidy for all N people is \min(3,1) + \min(3,3) + \min(3,2) + \min(3,4) = 9 yen, which exceeds the budget of 8 yen.

Therefore, the maximum possible value of the subsidy limit is 2 yen.

Sample Input 2

3 20
5 3 2

Sample Output 2

infinite

The subsidy limit can be made infinitely large.

Sample Input 3

10 23
2 5 6 5 2 1 7 9 7 2

Sample Output 3

2

Problem Statement

Planning to place many PCs in his room, Takahashi has decided to write a code that finds how many PCs he can place in his room.

You are given H strings S_1,S_2,\ldots,S_H, each of length W, consisting of . and T.

Takahashi may perform the following operation any number of times (possibly zero):

• Choose integers satisfying 1\leq i \leq H and 1 \leq j \leq W-1 such that the j-th and (j+1)-th characters of S_i are both T. Replace the j-th character of S_i with P, and (j+1)-th with C.

He tries to maximize the number of times he performs the operation. Find possible resulting S_1,S_2,\ldots,S_H.

Constraints

• 1\leq H \leq 100
• 2\leq W \leq 100
• H and W are integers.
• S_i is a string of length W consisting of . and T.

Sample Input 1

2 3
TTT
T.T

Sample Output 1

PCT
T.T

He can perform the operation at most once.

For example, an operation with (i,j)=(1,1) makes S_1 PCT.

Sample Input 2

3 5
TTT..
.TTT.
TTTTT

Sample Output 2

PCT..
.PCT.
PCTPC

Problem Statement

There is a directed graph (not necessarily simple) with N vertices and M edges, where the vertices are numbered as vertices 1, 2, \ldots, N.
The i-th (1\leq i\leq M) edge goes from vertex U_i to vertex V_i with cost C_i. Additionally, the out-degree of each vertex is at most 4.

Find all vertices v (1\leq v\leq N) that satisfy the following condition:

There exists a path from vertex 1 to vertex v that satisfies both of the following conditions:

• It traverses exactly L edges. If the same edge is traversed multiple times, each traversal is counted.
• The sum of the costs of the traversed edges is at least S and at most T. (If the same edge is traversed multiple times, the cost is added to the sum each time.)

Constraints

• 1\leq N\leq 2\times 10^5
• 1\leq M\leq 2\times 10^5
• 1\leq L \leq 10
• 1\leq S\leq T \leq 10^9
• 1\leq U_i,V_i\leq N
• 1\leq C_i\leq 10^8
• The out-degree of each vertex is at most 4.
• All input values are integers.

Sample Input 1

5 8 3 80 100
1 2 20
1 3 70
2 1 30
2 5 10
3 2 10
3 4 30
3 5 20
5 1 70

Sample Output 1

1 5

The given graph is as shown in the left figure below. The cost of each edge is shown near the starting vertex of that edge.

Here, the following holds:

• For the path from vertex 1 to vertex 1, consider vertex 1 \to vertex 2 \to vertex 5 \to vertex 1 (center of the figure above). This traverses exactly three edges, and the sum of the costs of the traversed edges is 20+10+70=100, so it satisfies the condition.
• There is no path from vertex 1 to vertex 2 that satisfies the condition. One path that traverses exactly three edges is vertex 1 \to vertex 2 \to vertex 1 \to vertex 2, but the sum of the costs of the edges traversed in this path is 20+30+20=70, which is less than 80, so it does not satisfy the condition.
• There is no path from vertex 1 to vertex 3 that satisfies the condition. One path that traverses exactly three edges is vertex 1 \to vertex 2 \to vertex 1 \to vertex 3, but the sum of the costs of the edges traversed in this path is 20+30+70=120, which is greater than 100, so it does not satisfy the condition.
• There is no path from vertex 1 to vertex 4 that satisfies the condition.
• For the path from vertex 1 to vertex 5, consider vertex 1 \to vertex 3 \to vertex 2 \to vertex 5 (right of the figure above). This traverses exactly three edges, and the sum of the costs of the traversed edges is 70+10+10=90, so it satisfies the condition.

Therefore, print 1, 5 in this order. Note that you need to print those vertices that satisfy the condition in ascending order.

Sample Input 2

10 1 1 1 100
2 3 1

Sample Output 2

If there are no vertices that satisfy the condition, print an empty line.

Sample Input 3

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

Sample Output 3

1 2

The graph may contain self-loops and multiple edges.
In this test case, the out-degrees from vertices 1 and 2 are 4 and 1, respectively.

Problem Statement

You are given a sequence of N-1 integers S = (S_1, S_2, \ldots, S_{N-1}), and M distinct integers X_1, X_2, \ldots, X_M, which are called lucky numbers.

A sequence of N integers A = (A_1, A_2, \ldots, A_N) satisfying the following condition is called a good sequence.

A_i + A_{i+1} = S_i holds for every i = 1, 2, \ldots, N-1.

Find the maximum possible number of terms that are lucky numbers in a good sequence A, that is, the maximum possible number of integers i between 1 and N such that A_i \in \lbrace X_1, X_2, \ldots, X_M \rbrace.

Constraints

• 2 \leq N \leq 10^5
• 1 \leq M \leq 10
• -10^9 \leq S_i \leq 10^9
• -10^9 \leq X_i \leq 10^9
• X_1 \lt X_2 \lt \cdots \lt X_M
• All values in input are integers.

Sample Input 1

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

Sample Output 1

4

A good sequence A = (3, -1, 4, -1, 5, -9, 2, -6, 5) contains four terms that are lucky numbers: A_2, A_4, A_5, A_9, which is the maximum possible count.

Sample Input 2

20 10
-183260318 206417795 409343217 238245886 138964265 -415224774 -499400499 -313180261 283784093 498751662 668946791 965735441 382033304 177367159 31017484 27914238 757966050 878978971 73210901
-470019195 -379631053 -287722161 -231146414 -84796739 328710269 355719851 416979387 431167199 498905398

Sample Output 2

8

Problem Statement

There is a grid with H rows and W columns. Let (i,j) denote the cell at the i-th row from the top and j-th column from the left.

There are N coins on this grid, and the i-th coin can be picked up by passing through the cell (R_i,C_i).

Your goal is to start from cell (1,1), repeatedly move either down or right by one cell, and reach cell (H,W) while picking up as many coins as possible.

Find the maximum number of coins you can pick up and one of the paths that achieves this maximum.

Constraints

• 2\leq H,W \leq 2\times 10^5
• 1\leq N \leq \min(HW-2, 2\times 10^5)
• 1\leq R_i \leq H
• 1\leq C_i \leq W
• (R_i,C_i)\neq (1,1)
• (R_i,C_i)\neq (H,W)
• (R_i,C_i) are pairwise distinct.
• All input values are integers.

Sample Input 1

3 4 4
3 3
2 1
2 3
1 4

Sample Output 1

3
DRRDR

As shown in the figure above, by moving (1,1)\rightarrow (2,1)\rightarrow (2,2)\rightarrow (2,3)\rightarrow (3,3)\rightarrow (3,4), you can pick up three coins at (2,1),(2,3),(3,3).

Sample Input 2

2 2 2
2 1
1 2

Sample Output 2

1
DR

The path RD is also acceptable.

Sample Input 3

10 15 8
2 7
2 9
7 9
10 3
7 11
8 12
9 6
8 1

Sample Output 3

5
DRRRRRRRRDDDDDRRDRDDRRR