Problem Statement

You are given a string S of length N consisting of lowercase English letters.
If there are any adjacent occurrences of a and b in S, print Yes; otherwise, print No. (The order of a and b does not matter.)

Constraints

• 2 \leq N \leq 100
• S is a string of length N consisting of lowercase English letters.

Sample Input 1

3
abc

Sample Output 1

Yes

The string abc has a as the first character and b as the second character, which are adjacent. Thus, print Yes.

Sample Input 2

2
ba

Sample Output 2

Yes

The string ba has a as the second character and b as the first character, which are adjacent. (Note that the order of a and b does not matter.)

Sample Input 3

7
atcoder

Sample Output 3

No

Problem Statement

There was an exam consisting of three problems worth 1, 2, and 4 points.

Takahashi, Aoki, and Snuke took this exam. Takahashi scored A points, and Aoki scored B points.

Snuke solved all of the problems solved by at least one of Takahashi and Aoki, and failed to solve any of the problems solved by neither of them.

Find Snuke's score.

It can be proved that Snuke's score is uniquely determined under the Constraints of this problem.

Constraints

• 0\leq A,B \leq 7
• A and B are integers.

Sample Input 1

1 2

Sample Output 1

3

Since Takahashi scored 1 point, we see that he solved only the 1-point problem and failed to solve the other two.
Similarly, since Aoki scored 2 points, we see that he solved only the 2-point problem and failed to solve the other two.

Therefore, Snuke must have solved the 1- and 2-point problems, but not the 4-point one, which Takahashi and Aoki both failed to solve, for a score of 3 points. Thus, 3 should be printed.

Sample Input 2

5 3

Sample Output 2

7

Since Takahashi scored 5 points, we see that he solved the 1- and 4-point problems but not the 2-point one.
Similarly, since Aoki scored 3 points, we see that he solved the 1- and 2-point problems but not the 4-point one.

Therefore, each of the three problems is solved by at least one of Takahashi and Aoki, so we see that Snuke solved all of the problems, for a score of 7 points. Thus, 7 should be printed.

Sample Input 3

0 0

Sample Output 3

0

Both Takahashi and Aoki solved none of the problems. Therefore, so did Snuke. Thus, 0 should be printed.

Problem Statement

You are given an odd number N that is at least 3.

There is a grid with N rows and N columns, where all cells are initially empty. Now, you will write integers in each cell of this grid according to the following procedure. Let (i,j) denote the cell at the (i+1)-th row from the top and (j+1)-th column from the left (0\leq i<N, 0\leq j<N).

1. Write 1 in cell (0,\frac{N-1}{2}).
2. Repeat the following operation N^2-1 times:
   • Let (r,c) be the cell where an integer was written last time, and k be the integer written. If cell ((r-1) \bmod N, (c+1) \bmod N) is empty, write k+1 in that cell; otherwise, write k+1 in cell ((r+1) \bmod N,c). Here, x \bmod N denotes the remainder when x is divided by N.

Find the integer that will be written in each cell in this procedure. It can be proved that each cell will have an integer written in it exactly once.

Constraints

• 3\leq N \leq 99
• N is an odd number.

Sample Input 1

3

Sample Output 1

8 1 6
3 5 7
4 9 2

Integers are written in each cell as follows:

1. Write 1 in cell (0,\frac{3-1}{2})=(0,1).
2. Cell ((0-1) \bmod 3, (1+1) \bmod 3)=(2,2) is empty, so write 2 there.
3. Cell ((2-1) \bmod 3, (2+1) \bmod 3)=(1,0) is empty, so write 3 there.
4. Cell ((1-1) \bmod 3, (0+1) \bmod 3)=(0,1) is not empty, so write 4 in cell ((1+1) \bmod 3,0)=(2,0).
5. \vdots

Sample Input 2

5

Sample Output 2

17 24 1 8 15
23 5 7 14 16
4 6 13 20 22
10 12 19 21 3
11 18 25 2 9

Problem Statement

You are given a string S of length N consisting of lowercase English letters. The x-th (1 \le x \le N) character of S is S_x.

For each i=1,2,\dots,N-1, find the maximum non-negative integer l that satisfies all of the following conditions:

• l+i \le N, and
• for all integers k such that 1 \le k \le l, it holds that S_{k} \neq S_{k+i}.

Note that l=0 always satisfies the conditions.

Constraints

• N is an integer such that 2 \le N \le 5000.
• S is a string of length N consisting of lowercase English letters.

Sample Input 1

6
abcbac

Sample Output 1

5
1
2
0
1

In this input, S= abcbac.

• When i=1, we have S_1 \neq S_2, S_2 \neq S_3, \dots, and S_5 \neq S_6, so the maximum value is l=5.
• When i=2, we have S_1 \neq S_3 but S_2 = S_4, so the maximum value is l=1.
• When i=3, we have S_1 \neq S_4 and S_2 \neq S_5 but S_3 = S_6, so the maximum value is l=2.
• When i=4, we have S_1 = S_5, so the maximum value is l=0.
• When i=5, we have S_1 \neq S_6, so the maximum value is l=1.

Problem Statement

Among the positive integers that consist of 0's and 2's when written in base 10, find the K-th smallest integer.

Constraints

• K is an integer between 1 and 10^{18} (inclusive).

Sample Input 1

3

Sample Output 1

22

The positive integers that consist of 0's and 2's when written in base 10 are 2,20,22,\dots in ascending order.
The (K=) 3-rd of them, which is 22, should be printed.

Sample Input 2

11

Sample Output 2

2022

Sample Input 3

923423423420220108

Sample Output 3

220022020000202020002022022000002020002222002200002022002200

Note that the exact value of the answer must be printed as an integer, even if it is big.

Problem Statement

You are given a length-N sequence of non-negative integers.
When B is a sequence obtained by choosing K elements from A and concatenating them without changing the order, find the maximum possible value of MEX(B).

Here, for a sequence X, we define MEX(X) as the unique non-negative integer m that satisfies the following conditions:

• Every integer i such that 0 \le i < m is contained in X.
• m is not contained in X.

Constraints

• All values in the input are integers.
• 1 \le K \le N \le 3 \times 10^5
• 0 \le A_i \le 10^9

Sample Input 1

7 3
2 0 2 3 2 1 9

Sample Output 1

3

In this input, A=(2,0,2,3,2,1,9), and you obtain the sequence B by picking K=3 elements. For example,

• If the 1-st, 2-nd, and 3-rd elements are chosen, MEX(B)=MEX(2,0,2)=1.
• If the 3-rd, 4-th, and 6-th elements are chosen, MEX(B)=MEX(2,3,1)=0.
• If the 2-nd, 6-th, and 7-th elements are chosen, MEX(B)=MEX(0,1,9)=2.
• If the 2-nd, 3-rd, and 6-th elements are chosen, MEX(B)=MEX(0,2,1)=3.

The maximum possible MEX is 3.

Problem Statement

Takahashi has N kinds of coins; specifically, for 1\leq i\leq N, he has B_i coins worth A_i yen (the currency in Japan) each.

Determine if Takahashi can pay exactly X yen (without change) with the coins he currently has.

Constraints

• 1\leq N\leq 50
• 1\leq X\leq 10^4
• 1\leq A_i\leq 100
• 1\leq B_i\leq 50
• A_i are pairwise distinct.
• All values in the input are integers.

Sample Input 1

2 19
2 3
5 6

Sample Output 1

Yes

Takahashi has three 2-yen coins and six 5-yen coins. He can use two 2-yen coins and three 5-yen coins to pay exactly 2\times 2+5\times 3=19 yen. Thus, Yes should be printed.

Sample Input 2

2 18
2 3
5 6

Sample Output 2

No

There is no combination of the coins that he can use to pay exactly 18 yen. Thus, No should be printed.

Sample Input 3

3 1001
1 1
2 1
100 10

Sample Output 3

Yes

He need not use all kinds of coins.

Problem Statement

There are N mochi (rice cakes), arranged in ascending order of size. The size of the i-th mochi (1\leq i\leq N) is A_i.

Given two mochi A and B, with sizes a and b respectively, you can make one kagamimochi (a stacked rice cake) by placing mochi A on top of mochi B if and only if a is at most half of b.

Find how many kagamimochi can be made simultaneously.

More precisely, find the maximum non-negative integer K for which the following is possible:

• From the N mochi, choose 2K of them to form K pairs. For each pair, place one mochi on top of the other, to make K kagamimochi.

Constraints

• 2 \leq N \leq 5 \times 10^5
• 1 \leq A_i \leq 10^9 \ (1 \leq i \leq N)
• A_i \leq A_{i+1} \ (1 \leq i < N)
• All input values are integers.

Sample Input 1

6
2 3 4 4 7 10

Sample Output 1

3

The sizes of the given mochi are as follows:

In this case, you can make the following three kagamimochi simultaneously:

It is not possible to make four or more kagamimochi from six mochi, so print 3.

Sample Input 2

3
387 388 389

Sample Output 2

0

It is possible that you cannot make any kagamimochi.

Sample Input 3

24
307 321 330 339 349 392 422 430 477 481 488 537 541 571 575 602 614 660 669 678 712 723 785 792

Sample Output 3

6

Problem Statement

There are N intervals on a number line, numbered from 1 to N.

The left endpoint of interval i is at coordinate 0, and the right endpoint is at coordinate W_i. Here, W_1 < W_2 < \dots < W_N.

You are given Q queries; process them in the order they are given. Each query is one of the following three types:

• Type 1 (1 v): Let l be the coordinate of the current left endpoint of interval v. Translate each of the intervals numbered v or less so that its left endpoint is at coordinate l.
• Type 2 (2 v): Let r be the coordinate of the current right endpoint of interval v. Translate each of the intervals numbered v or less so that its right endpoint is at coordinate r.
• Type 3 (3 x): Output the current number of intervals that contain coordinate x+\frac{1}{2}.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq W_i \leq 10^9 (1 \leq i \leq N)
• W_1 < W_2 < \dots < W_N
• For v given in queries of types 1 and 2, 1 \leq v \leq N.
• For x given in queries of type 3, 0 \leq x \leq 10^9.
• At least one query of type 3 is given.
• All input values are integers.

Sample Input 1

4
2 4 6 10
5
2 3
1 2
3 2
2 4
3 1

Sample Output 1

4
1

Initially, the intervals in order of their numbers are [0, 2], [0, 4], [0, 6], [0, 10].

• For the 1st query, the coordinate of the right endpoint of interval 3 before the operation is 6, so the intervals after the operation are [4, 6], [2, 6], [0, 6], [0, 10] in order of their numbers.
• For the 2nd query, the coordinate of the left endpoint of interval 2 before the operation is 2, so the intervals after the operation are [2, 4], [2, 6], [0, 6], [0, 10] in order of their numbers.
• For the 3rd query, the intervals that contain coordinate 2 + \frac{1}{2} are intervals 1,2,3,4, which is four intervals, so output 4.
• For the 4th query, the coordinate of the right endpoint of interval 4 before the operation is 10, so the intervals after the operation are [8, 10], [6, 10], [4, 10], [0, 10] in order of their numbers.
• For the 5th query, the intervals that contain coordinate 1 + \frac{1}{2} is only interval 4, which is one interval, so output 1.