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

You are given N strings W_1,W_2,\dots,W_N consisting of lowercase English letters.
If one or more of these strings equal and, not, that, the, or you, then print Yes; otherwise, print No.

Constraints

• N is an integer between 1 and 100, inclusive.
• 1 \le |W_i| \le 50 (|W_i| is the length of W_i.)
• W_i consists of lowercase English letters.

Sample Input 1

10
in that case you should print yes and not no

Sample Output 1

Yes

We have, for instance, W_4= you, so you should print Yes.

Sample Input 2

10
in diesem fall sollten sie no und nicht yes ausgeben

Sample Output 2

No

None of the strings W_i equals any of and, not, that, the, and you.

Problem Statement

We have seven cards. The i-th card (i=1,\ldots,7) has an integer A_i written on it.
Determine whether it is possible to choose five of them so that the chosen cards form a full house.

A set of five cards is called a full house if and only if the following conditions are satisfied:

• For different integers x and y, there are three cards with x and two cards with y.

Constraints

• A_i is an integer between 1 and 13, inclusive.

Sample Input 1

1 4 1 4 2 1 3

Sample Output 1

Yes

For example, by choosing the cards (1,1,1,4,4), we can form a full house.

Sample Input 2

11 12 13 10 13 12 11

Sample Output 2

No

No five cards chosen from the seven cards form a full house.

Sample Input 3

7 7 7 7 7 7 7

Sample Output 3

No

Note that five identical cards do not form a full house.

Sample Input 4

13 13 1 1 7 4 13

Sample Output 4

Yes

Problem Statement

There is a grid with H horizontal rows and W vertical columns, in which two distinct squares have a piece.

The state of the squares is represented by H strings S_1, \dots, S_H of length W. S_{i, j} = o means that there is a piece in the square at the i-th row from the top and j-th column from the left; S_{i, j} = - means that the square does not have a piece. Here, S_{i, j} denotes the j-th character of the string S_i.

Consider repeatedly moving one of the pieces to one of the four adjacent squares. It is not allowed to move the piece outside the grid. How many moves are required at minimum for the piece to reach the square with the other piece?

Constraints

• 2 \leq H, W \leq 100
• H and W are integers.
• S_i \, (1 \leq i \leq H) is a string of length W consisting of o and -.
• There exist exactly two pairs of integers 1 \leq i \leq H, 1 \leq j \leq W such that S_{i, j} = o.

Sample Input 1

2 3
--o
o--

Sample Output 1

3

The piece at the 1-st row from the top and 3-rd column from the left can reach the square with the other piece in 3 moves: down, left, left. Since it is impossible to do so in two or less moves, 3 should be printed.

Sample Input 2

5 4
-o--
----
----
----
-o--

Sample Output 2

4

Problem Statement

You are given positive integers N and K. Define a sequence A = (A_0, A_1, \ldots, A_N) of length N+1 as follows:

• A_i = 1 for 0 \le i < K;
• A_i=A_{i-K}+A_{i-K+1}+\ldots+A_{i-1} for K \le i.

Find A_N modulo 10^9.

Constraints

• 1 \le N, K \le 10^{6}
• All input values are integers.

Sample Input 1

4 2

Sample Output 1

5

We have A_0 = A_1 = 1, and A_2=A_0+A_1=2,A_3=A_1+A_2=3,A_4=A_2+A_3=5.

Sample Input 2

10 20

Sample Output 2

1

Sample Input 3

1000000 500000

Sample Output 3

420890625

Remember to print A_N modulo 10^9.

Problem Statement

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

Find the number of pairs of integers (l,r) satisfying 1\leq l\leq r\leq N such that the subsequence (A_l,A_{l+1},\dots,A_r) forms an arithmetic progression.

A sequence (x_1,x_2,\dots,x_{|x|}) is an arithmetic progression if and only if there exists a d such that x_{i+1}-x_i=d\ (1\leq i < |x|). In particular, a sequence of length 1 is always an arithmetic progression.

Constraints

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

Sample Input 1

4
3 6 9 3

Sample Output 1

8

There are eight pairs of integers (l,r) satisfying the condition: (1,1),(2,2),(3,3),(4,4),(1,2),(2,3),(3,4),(1,3).

Indeed, when (l,r)=(1,3), (A_l,\dots,A_r)=(3,6,9) is an arithmetic progression, so it satisfies the condition. However, when (l,r)=(2,4), (A_l,\dots,A_r)=(6,9,3) is not an arithmetic progression, so it does not satisfy the condition.

Sample Input 2

5
1 1 1 1 1

Sample Output 2

15

All pairs of integers (l,r)\ (1\leq l\leq r\leq 5) satisfy the condition.

Sample Input 3

8
87 42 64 86 72 58 44 30

Sample Output 3

22

Problem Statement

You are given an integer N and strings R and C of length N consisting of A, B, and C. Solve the following problem.

There is a N \times N grid. All cells are initially empty.
You can write at most one character from A, B, and C in each cell. (You can also leave the cell empty.)

Determine if it is possible to satisfy all of the following conditions, and if it is possible, print one way to do so.

• Each row and each column contain exactly one A, one B, and one C.
• The leftmost character written in the i-th row matches the i-th character of R.
• The topmost character written in the i-th column matches the i-th character of C.

Constraints

• N is an integer between 3 and 5, inclusive.
• R and C are strings of length N consisting of A, B, and C.

Sample Input 1

5
ABCBC
ACAAB

Sample Output 1

Yes
AC..B
.BA.C
C.BA.
BA.C.
..CBA

The grid in the output example satisfies all the following conditions, so it will be treated as correct.

• Each row contains exactly one A, one B, and one C.
• Each column contains exactly one A, one B, and one C.
• The leftmost characters written in the rows are A, B, C, B, C from top to bottom.
• The topmost characters written in the columns are A, C, A, A, B from left to right.

Sample Input 2

3
AAA
BBB

Sample Output 2

No

For this input, there is no way to fill the grid to satisfy the conditions.

Problem Statement

We have a sequence A=(A_1,A_2,\dots,A_N) of length N. Initially, all the terms are 0.
Using an integer K given in the input, we define a function f(A) as follows:

• Let B be the sequence obtained by sorting A in descending order (so that it becomes monotonically non-increasing).
• Then, let f(A)=B_1 + B_2 + \dots + B_K.

We consider applying Q updates on this sequence.
Apply the following operation on the sequence A for i=1,2,\dots,Q in this order, and print the value f(A) at that point after each update.

• Change A_{X_i} to Y_i.

Constraints

• All input values are integers.
• 1 \le K \le N \le 5 \times 10^5
• 1 \le Q \le 5 \times 10^5
• 1 \le X_i \le N
• 0 \le Y_i \le 10^9

Sample Input 1

4 2 10
1 5
2 1
3 3
4 2
2 10
1 0
4 0
3 1
2 0
3 0

Sample Output 1

5
6
8
8
15
13
13
11
1
0

In this input, N=4 and K=2. Q=10 updates are applied.

• The 1-st update makes A=(5, 0,0,0). Now, f(A)=5.
• The 2-nd update makes A=(5, 1,0,0). Now, f(A)=6.
• The 3-rd update makes A=(5, 1,3,0). Now, f(A)=8.
• The 4-th update makes A=(5, 1,3,2). Now, f(A)=8.
• The 5-th update makes A=(5,10,3,2). Now, f(A)=15.
• The 6-th update makes A=(0,10,3,2). Now, f(A)=13.
• The 7-th update makes A=(0,10,3,0). Now, f(A)=13.
• The 8-th update makes A=(0,10,1,0). Now, f(A)=11.
• The 9-th update makes A=(0, 0,1,0). Now, f(A)=1.
• The 10-th update makes A=(0, 0,0,0). Now, f(A)=0.

Problem Statement

You are given sequences of positive integers of length N: A=(A_1,A_2,\ldots,A_N) and B=(B_1,B_2,\ldots,B_N).

You are given Q queries to process in order. The i-th query is explained below.

• You are given positive integers l_i,r_i,L_i,R_i. Print Yes if it is possible to rearrange the subsequence (A_{l_i},A_{l_i+1},\ldots,A_{r_i}) to match the subsequence (B_{L_i},B_{L_i+1},\ldots,B_{R_i}), and No otherwise.

Constraints

• 1\leq N,Q\leq 2\times 10^5
• 1\leq A_i,B_i\leq N
• 1\leq l_i \leq r_i\leq N
• 1\leq L_i \leq R_i\leq N
• All input values are integers.

Sample Input 1

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

Sample Output 1

Yes
No
No
Yes

• For the 1st query, it is possible to rearrange (1,2,3) to match (2,3,1). Hence, we print Yes.
• For the 2nd query, it is impossible to rearrange (1,2) in any way to match (1,4,2). Hence, we print No.
• For the 3rd query, it is impossible to rearrange (1,2,3,2) in any way to match (3,1,4,2). Hence, we print No.
• For the 4th query, it is possible to rearrange (1,2,3,2,4) to match (2,3,1,4,2). Hence, we print Yes.

Sample Input 2

4 4
4 4 4 4
4 4 4 4
1 2 2 3
3 3 1 1
1 3 1 4
1 4 2 3

Sample Output 2

Yes
Yes
No
No