Problem Statement

Takahashi turns on the light of his room at S o'clock (on the 24-hour clock) every day and turns it off at T o'clock every day.
The date may change while the light is on.

Determine whether the light is on at 30 minutes past X o'clock.

Constraints

• 0 \leq S, T, X \leq 23
• S \neq T
• All values in input are integers.

Sample Input 1

7 20 12

Sample Output 1

Yes

The light is on between 7 o'clock and 20 o'clock. At 30 minutes past 12 o'clock, it is on, so we print Yes.

Sample Input 2

20 7 12

Sample Output 2

No

The light is on between 0 o'clock and 7 o'clock, and between 20 o'clock and 0 o'clock (on the next day). At 30 minutes past 12 o'clock, it is off, so we print No.

Sample Input 3

23 0 23

Sample Output 3

Yes

Problem Statement

There are N people. Each of them agrees or disagrees with a proposal. Here, N is an odd number.

The i-th (i = 1, 2, \dots, N) person's opinion is represented by a string S_i: the person agrees if S_i = For and disagrees if S_i = Against.

Determine whether the majority agrees with the proposal.

Constraints

• N is an odd number between 1 and 99, inclusive.
• S_i = For or S_i = Against, for all i = 1, 2, \dots, N.

Sample Input 1

3
For
Against
For

Sample Output 1

Yes

The proposal is supported by two people, which is the majority, so Yes should be printed.

Sample Input 2

5
Against
Against
For
Against
For

Sample Output 2

No

The proposal is supported by two people, which is not the majority, so No should be printed.

Sample Input 3

1
For

Sample Output 3

Yes

Problem Statement

Locate a piece on a chessboard.

We have a grid with 8 rows and 8 columns of squares. Each of the squares has a 2-character name determined as follows.

• The first character of the name of a square in the 1-st column from the left is a. Similarly, the first character of the name of a square in the 2-nd, 3-rd, \ldots, 8-th column from the left is b, c, d, e, f, g, h, respectively.
• The second character of the name of a square in the 1-st row from the bottom is 1. Similarly, the second character of the name of a square in the 2-nd, 3-rd, \ldots, 8-th row from the bottom is 2, 3, 4, 5, 6, 7, 8, respectively.

For instance, the bottom-left square is named a1, the bottom-right square is named h1, and the top-right square is named h8.

You are given 8 strings S_1,\ldots,S_8, each of length 8, representing the state of the grid.
The j-th character of S_i is * if the square at the i-th row from the top and j-th column from the left has a piece on it, and . otherwise. The character * occurs exactly once among S_1,\ldots,S_8. Find the name of the square that has a piece on it.

Constraints

• S_i is a string of length 8 consisting of . and*.
• The character * occurs exactly once among S_1,\ldots,S_8.

Sample Input 1

........
........
........
........
........
........
........
*.......

Sample Output 1

a1

As explained in the problem statement, the bottom-left square is named a1.

Sample Input 2

........
........
........
........
........
.*......
........
........

Sample Output 2

b3

Problem Statement

Takahashi is participating in a gymnastic competition.
In the competition, each of 5N judges grades Takahashi's performance, and his score is determined as follows:

• Invalidate the grades given by the N judges who gave the highest grades.
• Invalidate the grades given by the N judges who gave the lowest grades.
• Takahashi's score is defined as the average of the remaining 3N judges' grades.

More formally, Takahashi's score is obtained by performing the following procedure on the multiset of the judges' grades S (|S|=5N):

• Repeat the following operation N times: choose the maximum element (if there are multiple such elements, choose one of them) and remove it from S.
• Repeat the following operation N times: choose the minimum element (if there are multiple such elements, choose one of them) and remove it from S.
• Takahashi's score is defined as the average of the 3N elements remaining in S.

The i-th (1\leq i\leq 5N) judge's grade for Takahashi's performance was X_i points. Find Takahashi's score.

Constraints

• 1\leq N\leq 100
• 0\leq X_i\leq 100
• All values in the input are integers.

Sample Input 1

1
10 100 20 50 30

Sample Output 1

33.333333333333336

Since N=1, the grade given by one judge who gave the highest grade, and one with the lowest, are invalidated.
The 2-nd judge gave the highest grade (100 points), which is invalidated.
Additionally, the 1-st judge gave the lowest grade (10 points), which is also invalidated.
Thus, the average is \displaystyle\frac{20+50+30}{3}=33.333\cdots.

Note that the output will be considered correct if the absolute or relative error from the true value is at most 10^{-5}.

Sample Input 2

2
3 3 3 4 5 6 7 8 99 100

Sample Output 2

5.500000000000000

Since N=2, the grades given by the two judges who gave the highest grades, and two with the lowest, are invalidated.
The 10-th and 9-th judges gave the highest grades (100 and 99 points, respectively), which are invalidated.
Three judges, the 1-st, 2-nd, and 3-rd, gave the lowest grade (3 points), so two of them are invalidated.
Thus, the average is \displaystyle\frac{3+4+5+6+7+8}{6}=5.5.

Note that the choice of the two invalidated judges from the three with the lowest grades does not affect the answer.

Problem Statement

A single-player card game is popular in AtCoder Inc. Each card in the game has a lowercase English letter or the symbol @ written on it. There is plenty number of cards for each kind. The game goes as follows.

1. Arrange the same number of cards in two rows.
2. Replace each card with @ with one of the following cards: a, t, c, o, d, e, r.
3. If the two rows of cards coincide, you win. Otherwise, you lose.

To win this game, you will do the following cheat.

• Freely rearrange the cards within a row whenever you want after step 1.

You are given two strings S and T, representing the two rows you have after step 1. Determine whether it is possible to win with cheating allowed.

Constraints

• S and T consist of lowercase English letters and @.
• The lengths of S and T are equal and between 1 and 2\times 10^5, inclusive.

Sample Input 1

ch@ku@ai
choku@@i

Sample Output 1

Yes

You can replace the @s so that both rows become chokudai.

Sample Input 2

ch@kud@i
akidu@ho

Sample Output 2

Yes

You can cheat and replace the @s so that both rows become chokudai.

Sample Input 3

aoki
@ok@

Sample Output 3

No

You cannot win even with cheating.

Sample Input 4

aa
bb

Sample Output 4

No

Problem Statement

You are given a sequence A = (A_1, A_2, \ldots, A_N) of length N. For each K = 0, 1, 2, \ldots, N-1, solve the following problem.

Find the number of integers i between 1 and N (inclusive) such that:

• A contains exactly K distinct integers greater than A_i.

Constraints

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

Sample Input 1

6
2 7 1 8 2 8

Sample Output 1

2
1
2
1
0
0

For example, we will find the answer for K=2.

• Regarding A_1 = 2, A contains 2 distinct integers greater than A_1: 7 and 8.
• Regarding A_2 = 7, A contains 1 distinct integer greater than A_2: 8.
• Regarding A_3 = 1, A contains 3 distinct integers greater than A_3: 2, 7, and 8.
• Regarding A_4 = 8, A contains 0 distinct integers greater than A_4 (there is no such integer).
• Regarding A_5 = 2, A contains 2 distinct integers greater than A_5: 7 and 8.
• Regarding A_6 = 8, A contains 0 distinct integers greater than A_6 (there is no such integer).

Thus, there are two i's, i = 1 and i = 5, such that A contains exactly K = 2 distinct integers greater than A_i. Therefore, the answer for K = 2 is 2.

Sample Input 2

1
1

Sample Output 2

1

Sample Input 3

10
979861204 57882493 979861204 447672230 644706927 710511029 763027379 710511029 447672230 136397527

Sample Output 3

2
1
2
1
2
1
1
0
0
0

Problem Statement

You are given a string S of length N consisting of uppercase and lowercase English letters.

Let us perform Q operations on the string S. The i-th operation (1\leq i\leq Q) is represented by a tuple (t _ i,x _ i,c _ i) of two integers and one character, as follows.

• If t _ i=1, change the x _ i-th character of S to c _ i.
• If t _ i=2, convert all uppercase letters in S to lowercase (do not use x _ i,c _ i for this operation).
• If t _ i=3, convert all lowercase letters in S to uppercase (do not use x _ i,c _ i for this operation).

Print the S after the Q operations.

Constraints

• 1\leq N\leq5\times10^5
• S is a string of length N consisting of uppercase and lowercase English letters.
• 1\leq Q\leq5\times10^5
• 1\leq t _ i\leq3\ (1\leq i\leq Q)
• If t _ i=1, then 1\leq x _ i\leq N\ (1\leq i\leq Q).
• c _ i is an uppercase or lowercase English letter.
• If t _ i\neq 1, then x _ i=0 and c _ i= 'a'.
• N,Q,t _ i,x _ i are all integers.

Sample Input 1

7
AtCoder
5
1 4 i
3 0 a
1 5 b
2 0 a
1 4 Y

Sample Output 1

atcYber

Initially, the string S is AtCoder.

• The first operation changes the 4-th character to i, changing S to AtCider.
• The second operation converts all lowercase letters to uppercase, changing S to ATCIDER.
• The third operation changes the 5-th character to b, changing S to ATCIbER.
• The fourth operation converts all uppercase letters to lowercase, changing S to atciber.
• The fifth operation changes the 4-th character to Y, changing S to atcYber.

After the operations, the string S is atcYber, so print atcYber.

Sample Input 2

35
TheQuickBrownFoxJumpsOverTheLazyDog
10
2 0 a
1 19 G
1 13 m
1 2 E
1 21 F
2 0 a
1 27 b
3 0 a
3 0 a
1 15 i

Sample Output 2

TEEQUICKBROWMFiXJUGPFOVERTBELAZYDOG

Problem Statement

You are given a string S of length N consisting of 0 and 1. It describes a length-N sequence A=(A _ 1,A _ 2,\ldots,A _ N). If the i-th character of S (1\leq i\leq N) is 0, then A _ i=0; if it is 1, then A _ i=1.

Find the following:

\[\sum _ {1\leq i\leq j\leq N}(\cdots((A _ i\barwedge A _ {i+1})\barwedge A _ {i+2})\barwedge\cdots\barwedge A _ j)\]

More formally, find \displaystyle\sum _ {i=1} ^ {N}\sum _ {j=i} ^ Nf(i,j) for f(i,j)\ (1\leq i\leq j\leq N) defined as follows:

\[f(i,j)=\left\{\begin{matrix} A _ i&(i=j)\\ f(i,j-1)\barwedge A _ j\quad&(i\lt j) \end{matrix}\right.\]

Here, \barwedge, NAND, is a binary operator satisfying the following:

\[0\barwedge0=1,0\barwedge1=1,1\barwedge0=1,1\barwedge1=0.\]

Constraints

• 1\leq N\leq10^6
• S is a string of length N consisting of 0 and 1.
• All input values are integers.

Sample Input 1

5
00110

Sample Output 1

9

Here are the values of f(i,j) for the pairs (i,j) such that 1\leq i\leq j\leq N:

• f(1,1)=0=0
• f(1,2)=0\barwedge0=1
• f(1,3)=(0\barwedge0)\barwedge1=0
• f(1,4)=((0\barwedge0)\barwedge1)\barwedge1=1
• f(1,5)=(((0\barwedge0)\barwedge1)\barwedge1)\barwedge0=1
• f(2,2)=0=0
• f(2,3)=0\barwedge1=1
• f(2,4)=(0\barwedge1)\barwedge1=0
• f(2,5)=((0\barwedge1)\barwedge1)\barwedge0=1
• f(3,3)=1=1
• f(3,4)=1\barwedge1=0
• f(3,5)=(1\barwedge1)\barwedge0=1
• f(4,4)=1=1
• f(4,5)=1\barwedge0=1
• f(5,5)=0=0

Their sum is 0+1+0+1+1+0+1+0+1+1+0+1+1+1+0=9, so print 9.

Note that \barwedge does not satisfy the associative property. For instance, (1\barwedge1)\barwedge0=0\barwedge0=1\neq0=1\barwedge1=1\barwedge(1\barwedge0).

Sample Input 2

30
101010000100101011010011000010

Sample Output 2

326

Problem Statement

Given are N distinct points in a two-dimensional plane. Point i (1 \leq i \leq N) has the coordinates (x_i,y_i).

Let us define the distance between two points i and j be \mathrm{min} (|x_i-x_j|,|y_i-y_j|): the smaller of the difference in the x-coordinates and the difference in the y-coordinates.

Find the maximum distance between two different points.

Constraints

• 2 \leq N \leq 200000
• 0 \leq x_i,y_i \leq 10^9
• (x_i,y_i) \neq (x_j,y_j) (i \neq j)
• All values in input are integers.

Sample Input 1

3
0 3
3 1
4 10

Sample Output 1

4

The distances between Points 1 and 2, between Points 1 and 3, and between Points 2 and 3 are 2, 4, and 1, respectively, so your output should be 4.

Sample Input 2

4
0 1
0 4
0 10
0 6

Sample Output 2

0

Sample Input 3

8
897 729
802 969
765 184
992 887
1 104
521 641
220 909
380 378

Sample Output 3

801