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