Problem Statement

In the figure shown in the image below, are the points numbered a and b directly connected by a line segment?

Constraints

• 1 \leq a \lt b \leq 10
• a and b are integers.

Sample Input 1

4 5

Sample Output 1

Yes

In the figure shown in the Problem Statement, the points numbered 4 and 5 are directly connected by a line segment.
Thus, Yes should be printed.

Sample Input 2

3 5

Sample Output 2

No

In the figure shown in the Problem Statement, the points numbered 3 and 5 are not directly connected by a line segment.
Thus, No should be printed.

Sample Input 3

1 10

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

You are given a sequence of 26 integers P=(P_1,P_2, \ldots ,P_{26}) consisting of integers from 1 through 26. It is guaranteed that all elements in P are distinct.

Print a string S of length 26 that satisfies the following condition.

• For every i (1 \leq i \leq 26), the i-th character of S is the lowercase English letter that comes P_i-th in alphabetical order.

Constraints

• 1 \leq P_i \leq 26
• P_i \neq P_j (i \neq j)
• All values in input are integers.

Sample Input 1

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

Sample Output 1

abcdefghijklmnopqrstuvwxyz

Sample Input 2

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

Sample Output 2

bacdefghijklmnopqrstuvwxyz

Sample Input 3

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

Sample Output 3

eklpyqragjdwtcbxzsnifvhmou

Problem Statement

Takahashi is playing a game called Chess960. He has decided to write a code that determines if a random initial state satisfies the conditions of Chess960.

You are given a string S of length eight. S has exactly one K and Q, and exactly two R's, B's , and N's. Determine if S satisfies all of the following conditions.

• Suppose that the x-th and y-th (x < y) characters from the left of S are B; then, x and y have different parities.

• K is between two R's. More formally, suppose that the x-th and y-th (x < y) characters from the left of S are R and the z-th is K; then x< z < y.

Constraints

• S is a string of length 8 that contains exactly one K and Q, and exactly two R's, B's , and N's.

Sample Input 1

RNBQKBNR

Sample Output 1

Yes

The 3-rd and 6-th characters are B, and 3 and 6 have different parities. Also, K is between the two R's. Thus, the conditions are fulfilled.

Sample Input 2

KRRBBNNQ

Sample Output 2

No

K is not between the two R's.

Sample Input 3

BRKRBQNN

Sample Output 3

No

Problem Statement

Given an integer N, find the number of integers X that satisfy all of the following conditions, modulo 998244353.

• X is an N-digit positive integer.
• Let X_1,X_2,\dots,X_N be the digits of X from top to bottom. They satisfy all of the following:
  • 1 \le X_i \le 9 for all integers 1 \le i \le N;
  • |X_i-X_{i+1}| \le 1 for all integers 1 \le i \le N-1.

Constraints

• N is an integer.
• 2 \le N \le 10^6

Sample Input 1

4

Sample Output 1

203

Some of the 4-digit integers satisfying the conditions are 1111,1234,7878,6545.

Sample Input 2

2

Sample Output 2

25

Sample Input 3

1000000

Sample Output 3

248860093

Be sure to find the count modulo 998244353.

Problem Statement

You are given a permutation P = (P_1, \dots, P_N) of (1, \dots, N), where (P_1, \dots, P_N) \neq (1, \dots, N).

Assume that P is the K-th lexicographically smallest among all permutations of (1 \dots, N). Find the (K-1)-th lexicographically smallest permutation.

Constraints

• 2 \leq N \leq 100
• 1 \leq P_i \leq N \, (1 \leq i \leq N)
• P_i \neq P_j \, (i \neq j)
• (P_1, \dots, P_N) \neq (1, \dots, N)
• All values in the input are integers.

Sample Input 1

3
3 1 2

Sample Output 1

2 3 1

Here are the permutations of (1, 2, 3) in ascending lexicographical order.

• (1, 2, 3)
• (1, 3, 2)
• (2, 1, 3)
• (2, 3, 1)
• (3, 1, 2)
• (3, 2, 1)

Therefore, P = (3, 1, 2) is the fifth smallest, so the sought permutation, which is the fourth smallest (5 - 1 = 4), is (2, 3, 1).

Sample Input 2

10
9 8 6 5 10 3 1 2 4 7

Sample Output 2

9 8 6 5 10 2 7 4 3 1

Problem Statement

We have a long piece of timber with a length of L meters.
For each x = 1, 2, \dots, L - 1, there is a mark called Mark x at x meters from the left end of the piece.

You are given Q queries, the i-th of which is represented as a pair of numbers (c_i, x_i).
Process the queries in ascending order of i as described below.

• If c_i = 1: cut the piece at Mark x_i into two.
• If c_i = 2: choose the piece with Mark x_i on it and print its length.

Here, for both kinds of queries c_i = 1, 2, it is guaranteed that there will have been no cut at Mark x_i when the query is to be processed.

Constraints

• 1 \leq L \leq 10^9
• 1 \leq Q \leq 2 \times 10^5
• c_i = 1, 2 (1 \leq i \leq Q)
• 1 \leq x_i \leq L - 1 (1 \leq i \leq Q)
• For every i (1 \leq i \leq Q), the following holds: there is no j such that 1 \leq j \lt i and (c_j,x_j) = (1, x_i).
• All values in input are integers.

Sample Input 1

5 3
2 2
1 3
2 2

Sample Output 1

5
3

At the time of the first query, no cut has been made, so the piece with Mark 2 has a length of 5 meters. Thus, you should print 5.
In the second query, the piece is cut into two pieces with lengths of 3 and 2 meters.
At the time of the third query, the piece with Mark 2 has a length of 3 meters, so you should print 3.

Sample Input 2

5 3
1 2
1 4
2 3

Sample Output 2

2

Sample Input 3

100 10
1 31
2 41
1 59
2 26
1 53
2 58
1 97
2 93
1 23
2 84

Sample Output 3

69
31
6
38
38

Problem Statement

Let us call a positive integer n that satisfies the following condition an arithmetic number.

• Let d_i be the i-th digit of n from the top (when n is written in base 10 without unnecessary leading zeros.) Then, (d_2-d_1)=(d_3-d_2)=\dots=(d_k-d_{k-1}) holds, where k is the number of digits in n.
  • This condition can be rephrased into the sequence (d_1,d_2,\dots,d_k) being arithmetic.
  • If n is a 1-digit integer, it is assumed to be an arithmetic number.

For example, 234,369,86420,17,95,8,11,777 are arithmetic numbers, while 751,919,2022,246810,2356 are not.

Find the smallest arithmetic number not less than X.

Constraints

• X is an integer between 1 and 10^{17} (inclusive).

Sample Input 1

152

Sample Output 1

159

The smallest arithmetic number not less than 152 is 159.

Sample Input 2

88

Sample Output 2

88

X itself may be an arithmetic number.

Sample Input 3

8989898989

Sample Output 3

9876543210

Problem Statement

Given are sequences of N integers each: A = (A_1, \dots, A_N) and B = (B_1, \dots, B_N). Find the number of non-empty subsets S of \{1,2,\ldots,N\} that satisfy the following condition:

• \max_{i \in S} A_i \geq \sum_{i \in S} B_i.

Since the count can be enormous, print it modulo 998244353.

Constraints

• 1 \leq N \leq 5000
• 1 \leq A_i,B_i \leq 5000
• All values in input are integers.

Sample Input 1

2
3 1
1 2

Sample Output 1

2

\{1,2,\ldots,N\} has three subsets: \{1\}, \{2\}, and \{1,2\}.

• For S=\{1\}, we have \max_{i \in S} A_i=3 and \sum_{i \in S} B_i=1.
• For S=\{2\}, we have \max_{i \in S} A_i=1 and \sum_{i \in S} B_i=2.
• For S=\{1,2\}, we have \max_{i \in S} A_i=3 and \sum_{i \in S} B_i=3.

Thus, the condition \max_{i \in S} A_i \geq \sum_{i \in S} B_i is satisfied by two subsets: \{1\} and \{1,2\}.

Sample Input 2

2
1 1
2 2

Sample Output 2

0

There may be no subsets that satisfy the condition.

Sample Input 3

20
1937 3980 2689 1208 3640 1979 581 2271 4229 3948 3708 1522 4161 4661 3797 96 3388 3395 2920 2247
4485 2580 174 1156 3770 3396 3558 3500 3494 479 269 3383 1230 1711 3545 3919 134 475 3796 1017

Sample Output 3

476