Problem Statement

You are given an integer sequence A=(A_1,A_2,\dots,A_N) of length N and an integer X.
Determine whether X is contained in A.

Constraints

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

Sample Input 1

5
3 1 4 1 5
4

Sample Output 1

Yes

We have A=(3,1,4,1,5) and X=4; X is contained in A.

Sample Input 2

4
100 100 100 100
100

Sample Output 2

Yes

X may be contained in A multiple times.

Sample Input 3

6
2 3 5 7 11 13
1

Sample Output 3

No

Problem Statement

A mayoral election is being held in AtCoder City. The candidates are Takahashi and Aoki.

There are N valid votes cast for either of the two candidates, and the counting is currently underway. Here, N is an odd number.

The current vote count is T votes for Takahashi and A votes for Aoki.

Determine if the outcome of the election is already decided at this point.

Constraints

• 1 \leq N \leq 99
• N is an odd number.
• 0 \leq T, A \leq N
• T + A \leq N
• All input values are integers.

Sample Input 1

7 4 2

Sample Output 1

Yes

Even if the remaining one vote goes to Aoki, Takahashi will still win. That is, his victory is decided, so print Yes.

Sample Input 2

99 12 48

Sample Output 2

No

Although Aoki currently has more votes, Takahashi would win if he receives the remaining 39 votes. Therefore, print No.

Sample Input 3

1 0 0

Sample Output 3

No

Problem Statement

You are given three strings S_1, S_2, S_3 consisting of lowercase English letters, and a string T consisting of 1, 2, 3.

Concatenate the three strings according to the characters in T and print the resulting string. Formally, conform to the following instructions.

• For each integer i such that 1 \leq i \leq |T|, let the string s_i be defined as follows:
  • S_1, if the i-th character of T is 1;
  • S_2, if the i-th character of T is 2;
  • S_3, if the i-th character of T is 3.
• Concatenate the strings s_1, s_2, \dots, s_{|T|} in this order and print the resulting string.

Constraints

• 1 \leq |S_1|, |S_2|, |S_3| \leq 10
• 1 \leq |T| \leq 1000
• S_1, S_2, and S_3 consist of lowercase English letters.
• T consists of 1, 2, and 3.

Sample Input 1

mari
to
zzo
1321

Sample Output 1

marizzotomari

We have s_1 = mari, s_2 = zzo, s_3 = to, s_4 = mari. Concatenate these and print the resulting string: marizzotomari.

Sample Input 2

abra
cad
abra
123

Sample Output 2

abracadabra

Sample Input 3

a
b
c
1

Sample Output 3

a

Problem Statement

There is a stack of 100 cards, each labeled with the integer 0.

Process Q queries. Each query is of one of the following:

• Type 1: Place a card labeled with an integer x on top of the stack.
• Type 2: Remove the top card of the stack and output the integer written on that removed card. Under the constraints of this problem, the stack always has at least one card.

Constraints

• 1 \le Q \le 100
• 1 \le x \le 100
• There is at least one query of type 2.
• All input values are integers.

Sample Input 1

6
2
1 4
1 3
2
2
2

Sample Output 1

0
3
4
0

After processing each query, the stack is as follows:

• Remove the top card of the stack. The integer on the removed card is 0, so output 0.
  • The stack then has 99 cards labeled with 0.
• Add a card labeled 4 on top.
  • The stack then has 1 card labeled 4, and 99 cards labeled 0, from top to bottom.
• Add a card labeled 3 on top.
  • The stack then has 1 card labeled 3, 1 card labeled 4, and 99 cards labeled 0, from top to bottom.
• Remove the top card. The integer on that card is 3, so output 3.
  • The stack then has 1 card labeled 4, and 99 cards labeled 0, from top to bottom.
• Remove the top card. The integer on that card is 4, so output 4.
  • The stack then has 99 cards labeled 0.
• Remove the top card. The integer on that card is 0, so output 0.
  • The stack then has 98 cards labeled 0.

Sample Input 2

5
2
2
2
2
2

Sample Output 2

0
0
0
0
0

Problem Statement

You are given two strings S and T. Determine whether it is possible to make S equal T by performing the following operation some number of times (possibly zero).

Between two consecutive equal characters in S, insert a character equal to these characters. That is, take the following three steps.

1. Let N be the current length of S, and S = S_1S_2\ldots S_N.
2. Choose an integer i between 1 and N-1 (inclusive) such that S_i = S_{i+1}. (If there is no such i, do nothing and terminate the operation now, skipping step 3.)
3. Insert a single copy of the character S_i(= S_{i+1}) between the i-th and (i+1)-th characters of S. Now, S is a string of length N+1: S_1S_2\ldots S_i S_i S_{i+1} \ldots S_N.

Constraints

• Each of S and T is a string of length between 2 and 2 \times 10^5 (inclusive) consisting of lowercase English letters.

Sample Input 1

abbaac
abbbbaaac

Sample Output 1

Yes

You can make S = abbaac equal T = abbbbaaac by the following three operations.

• First, insert b between the 2-nd and 3-rd characters of S. Now, S = abbbaac.
• Next, insert b again between the 2-nd and 3-rd characters of S. Now, S = abbbbaac.
• Lastly, insert a between the 6-th and 7-th characters of S. Now, S = abbbbaaac.

Thus, Yes should be printed.

Sample Input 2

xyzz
xyyzz

Sample Output 2

No

No sequence of operations makes S = xyzz equal T = xyyzz. Thus, No should be printed.

Problem Statement

We have HW cards arranged in a matrix with H rows and W columns.
For each i=1, \ldots, N, the card at the A_i-th row from the top and B_i-th column from the left has a number i written on it. The other HW-N cards have nothing written on them.

We will repeat the following two kinds of operations on these cards as long as we can.

• If there is a row without a numbered card, remove all the cards in that row and fill the gap by shifting the remaining cards upward.
• If there is a column without a numbered card, remove all the cards in that column and fill the gap by shifting the remaining cards to the left.

Find the position of each numbered card after the end of the process above. It can be proved that these positions are uniquely determined without depending on the order in which the operations are done.

Constraints

• 1 \leq H,W \leq 10^9
• 1 \leq N \leq \min(10^5,HW)
• 1 \leq A_i \leq H
• 1 \leq B_i \leq W
• All pairs (A_i,B_i) are distinct.
• All values in input are integers.

Sample Input 1

4 5 2
3 2
2 5

Sample Output 1

2 1
1 2

Let * represent a card with nothing written on it. The initial arrangement of cards is:

*****
****2
*1***
*****

After the end of the process, they will be arranged as follows:

*2
1*

Here, the card with 1 is at the 2-nd row from the top and 1-st column from the left, and the card with 2 is at the 1-st row from the top and 2-nd column from the left.

Sample Input 2

1000000000 1000000000 10
1 1
10 10
100 100
1000 1000
10000 10000
100000 100000
1000000 1000000
10000000 10000000
100000000 100000000
1000000000 1000000000

Sample Output 2

1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10

Problem Statement

Given are a permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N) and a positive integer K.

For each i=K,K+1,\ldots,N, find the following.

• The K-th greatest value among the first i terms of P.

Constraints

• 1 \leq K \leq N \leq 5 \times 10^5
• (P_1,P_2,\ldots,P_N) is a permutation of (1,2,\ldots,N).
• All values in input are integers.

Sample Input 1

3 2
1 2 3

Sample Output 1

1
2

• The (K=) 2-nd greatest value among the first 2 terms of P, (P_1,P_2)=(1,2), is 1.
• The (K=) 2-nd greatest value among the first 3 terms of P, (P_1,P_2,P_3)=(1,2,3), is 2.

Sample Input 2

11 5
3 7 2 5 11 6 1 9 8 10 4

Sample Output 2

2
3
3
5
6
7
7

Problem Statement

You are given strings A and B of equal length consisting of 0 and 1.

You can perform the following operation on A zero or more times.

• Move the first character of A to the end.

Find the minimum number of operations required to make A=B.
If it is impossible to make A=B no matter how you operate, print -1 instead.

You are given T test cases; find the answer for each of them.

Constraints

• 1 \le T \le 10000
• A and B are strings consisting of 0 and 1.
• 2 \le |A|=|B| \le 10^6
• For a single input, the sum of |A| does not exceed 10^6.

Sample Input 1

5
1010001
1000110
000
111
01010
01010
0101
0011
100001101110000001010110110001
101100011000011011100000010101

Sample Output 1

2
-1
0
-1
22

This input contains five test cases.

• For the first test case, A= 1010001 and B= 1000110.
  • By performing the operation on A twice, A becomes 1010001 \rightarrow 0100011 \rightarrow 1000110, which makes A=B.
• For the second test case, no matter how you perform the operation, you cannot change 000 to 111.
• For the third test case, A=B from the beginning.

Problem Statement

You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N and a positive integer D.

Find the number, modulo 998244353, of integer sequences B=(B_1, B_2, \ldots, B_N) that can be obtained by rearranging A and satisfy the following condition:

• B_{i+1}\geq B_i-D holds for all i\ (1\leq i\leq N-1).

Constraints

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

Sample Input 1

4 1
5 2 1 2

Sample Output 1

3

The integer sequences satisfying the condition are (1,2,2,5),(2,1,2,5),(2,2,1,5), which are three sequences.

Sample Input 2

5 10
20 40 60 80 100

Sample Output 2

1

Sample Input 3

15 12345
18270 31252 27543 31406 22271 13402 12279 25697 18349 27615 39360 22790 32581 23990 36154

Sample Output 3

858152905