Problem Statement

Takahashi has N items and one bag.

The size of the i-th (1\le i\le N) item is A_i, and the size of the bag is M.

If and only if the total size of the items he is trying to put in the bag is at most M, he can put all those items in the bag simultaneously.

If he can put all N items in the bag simultaneously, print Yes; otherwise, print No.

Constraints

• 1\le N\le100
• 1\le M\le10000
• 1\le A_i\le100\ (1\le i\le N)
• All input values are integers.

Sample Input 1

5 15
3 1 4 1 5

Sample Output 1

Yes

The total size of the 5 items is 3+1+4+1+5=14. Since this is not greater than the bag size 15, Takahashi can put all items in the bag simultaneously. Thus, print Yes.

Sample Input 2

5 5
3 1 4 1 5

Sample Output 2

No

The total size of the 5 items is 14, which is greater than the bag size 5, so he cannot put all items in the bag simultaneously. Thus, print No.

Sample Input 3

1 10000
100

Sample Output 3

Yes

Problem Statement

Determine if there is a segment that directly connects the points numbered a and b in the figure below.

Constraints

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

Sample Input 1

1 2

Sample Output 1

Yes

In the figure in the Problem Statement, there is a segment that directly connects the points numbered 1 and 2, so Yes should be printed.

Sample Input 2

2 8

Sample Output 2

No

In the figure in the Problem Statement, there is no segment that directly connects the points numbered 2 and 8, so No should be printed.

Sample Input 3

14 15

Sample Output 3

No

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

Keyence has N bases worldwide, numbered 1 to N. Base i has W_i employees, and at 0 o'clock in Coordinated Universal Time (UTC), it is X_i o'clock at base i.

You want to hold a one-hour meeting across the entire company. Each employee can only participate in the meeting if the meeting time is completely within the 9:00-18:00 time slot at their base. Find the maximum number of employees who can participate when deciding the meeting time to allow as many employees as possible to participate.

Constraints

• 1\leq N \leq 1000
• 1\leq W_i \leq 10^6
• 0\leq X_i < 24
• All input values are integers.

Sample Input 1

3
5 0
3 3
2 18

Sample Output 1

8

Consider holding the meeting from 14:00 to 15:00 in UTC.

• The meeting is held from 14:00 to 15:00 at base 1, so the 5 employees at base 1 can participate in the meeting.
• The meeting is held from 17:00 to 18:00 at base 2, so the 3 employees at base 2 can participate in the meeting.
• The meeting is held from 8:00 to 9:00 at base 3, so the 2 employees at base 3 cannot participate in the meeting.

Thus, a total of 5+3=8 employees can participate in the meeting. No meeting time allows more employees to participate.

Sample Input 2

2
1 10
1000000 20

Sample Output 2

1000000

Sample Input 3

6
31 3
20 8
11 5
4 3
47 14
1 18

Sample Output 3

67

Problem Statement

You are given strictly increasing sequences of length N and M: A=(A _ 1,A _ 2,\ldots,A _ N) and B=(B _ 1,B _ 2,\ldots,B _ M). Here, A _ i\neq B _ j for every i and j (1\leq i\leq N,1\leq j\leq M).

Let C=(C _ 1,C _ 2,\ldots,C _ {N+M}) be a strictly increasing sequence of length N+M that results from the following procedure.

• Let C be the concatenation of A and B. Formally, let C _ i=A _ i for i=1,2,\ldots,N, and C _ i=B _ {i-N} for i=N+1,N+2,\ldots,N+M.
• Sort C in ascending order.

For each of A _ 1,A _ 2,\ldots,A _ N, B _ 1,B _ 2,\ldots,B _ M, find its position in C. More formally, for each i=1,2,\ldots,N, find k such that C _ k=A _ i, and for each j=1,2,\ldots,M, find k such that C _ k=B _ j.

Constraints

• 1\leq N,M\leq 10^5
• 1\leq A _ 1\lt A _ 2\lt\cdots\lt A _ N\leq 10^9
• 1\leq B _ 1\lt B _ 2\lt\cdots\lt B _ M\leq 10^9
• A _ i\neq B _ j for every i and j (1\leq i\leq N,1\leq j\leq M).
• All values in the input are integers.

Sample Input 1

4 3
3 14 15 92
6 53 58

Sample Output 1

1 3 4 7
2 5 6

C will be (3,6,14,15,53,58,92). Here, the 1-st, 3-rd, 4-th, 7-th elements are from A=(3,14,15,92), and the 2-nd, 5-th, 6-th elements are from B=(6,53,58).

Sample Input 2

4 4
1 2 3 4
100 200 300 400

Sample Output 2

1 2 3 4
5 6 7 8

Sample Input 3

8 12
3 4 10 15 17 18 22 30
5 7 11 13 14 16 19 21 23 24 27 28

Sample Output 3

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

Problem Statement

There is an integer sequence A of length N, initially A_i = i. Process a total of Q queries of the following types:

• Type 1: Change A_p to x.
• Type 2: Output A_p.
• Type 3: Repeat the operation "move the first element of A to the end" k times.
  • Formally, replace A with (A_2,A_3,\dots,A_N,A_1) k times.

Constraints

• All input values are integers.
• 1 \le N \le 10^6
• 1 \le Q \le 3 \times 10^5
• All queries satisfy the following constraints:
  • 1 \le p \le N
  • 1 \le x \le 10^6
  • 1 \le k \le 10^9

Sample Input 1

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

Sample Output 1

3
1
1000000

This input contains 5 queries.

• Initially, A=(1,2,3,4,5).
• The 1st query is Type 2: output A_3=3.
• The 2nd query is Type 1: replace A_2 with 1000000.
  • After the query, A=(1,1000000,3,4,5).
• The 3rd query is Type 3: repeat the operation "move the first element of A to the end" 4 times.
  • After the query, A=(5,1,1000000,3,4).
• The 4th query is Type 2: output A_2=1.
• The 5th query is Type 2: output A_3=1000000.

Sample Input 2

1000000 2
1 1000000 999999
3 1000000000

Sample Output 2

The output may be empty.

Problem Statement

There is a simple undirected graph G with N vertices and M edges. The vertices are numbered 1, 2, \ldots, N, and the i-th edge is an undirected edge connecting vertices A_i and B_i.

You can repeat the following two operations in any order and any number of times:

• Add one undirected edge to G
• Remove one undirected edge from G

Find the minimum number of operations to make G a simple undirected graph where all vertices have degree 2.

Constraints

• 3 \leq N \leq 8
• 0 \leq M \leq \frac{N(N-1)}{2}
• The graph G given in the input is a simple undirected graph.
• All input values are integers.

Sample Input 1

5 4
1 2
1 5
2 4
4 5

Sample Output 1

3

For example, the following three operations make G a simple undirected graph where all vertices have degree 2.

• Add an edge connecting vertices 2 and 3.
• Remove the edge connecting vertices 2 and 4.
• Add an edge connecting vertices 3 and 4.

Sample Input 2

3 0

Sample Output 2

3

Sample Input 3

6 8
1 4
1 5
2 3
2 6
3 4
3 6
4 5
4 6

Sample Output 3

2

Sample Input 4

8 21
1 4
5 7
8 4
3 4
2 5
8 1
5 1
2 8
2 1
2 4
3 1
6 7
5 8
2 7
6 8
5 4
3 8
7 3
7 8
5 3
7 4

Sample Output 4

13

Problem Statement

This problem has a similar setting to Problem G. Differences in the problem statement are indicated in red.

There is a grid with H rows and W columns, where each cell is painted red or green.

Let (i,j) denote the cell in the i-th row from the top and the j-th column from the left.

The color of cell (i,j) is represented by the character S_{i,j}, where S_{i,j} = . means cell (i,j) is red, and S_{i,j} = # means cell (i,j) is green.

The number of green connected components in the grid is the number of connected components in the graph with the vertex set being the green cells and the edge set being the edges connecting two adjacent green cells. Here, two cells (x,y) and (x',y') are considered adjacent when |x-x'| + |y-y'| = 1.

Consider choosing one red cell uniformly at random and repainting it green. Print the expected value of the number of green connected components in the grid after repainting, modulo 998244353.

Constraints

• 1 \leq H,W \leq 1000
• S_{i,j} = . or S_{i,j} = #.
• There is at least one (i,j) such that S_{i,j} = ..

Sample Input 1

3 3
##.
#.#
#..

Sample Output 1

499122178

If cell (1,3) is repainted green, the number of green connected components becomes 1.

If cell (2,2) is repainted green, the number of green connected components becomes 1.

If cell (3,2) is repainted green, the number of green connected components becomes 2.

If cell (3,3) is repainted green, the number of green connected components becomes 2.

Therefore, the expected value of the number of green connected components after choosing one red cell uniformly at random and repainting it green is (1+1+2+2)/4 = 3/2.

Sample Input 2

4 5
..#..
.###.
#####
..#..

Sample Output 2

598946613

Sample Input 3

3 4
#...
.#.#
..##

Sample Output 3

285212675

Problem Statement

You are given a string S consisting of lowercase English letters. Print the number of non-empty strings T that satisfy the following condition, modulo 998244353.

The concatenation TT of two copies of T is a subsequence of S (not necessarily contiguous).

Constraints

• S is a string consisting of lowercase English letters whose length is between 1 and 100, inclusive.

Sample Input 1

ababbaba

Sample Output 1

8

The eight strings satisfying the condition are a, aa, ab, aba, b, ba, bab, and bb.

Sample Input 2

zzz

Sample Output 2

1

The only string satisfying the condition is z. Note that this string contributes to the answer just once, although there are three ways to extract the subsequence zz from S = S_1S_2S_3 = zzz: S_1S_2 = zz, S_1S_3 = zz, and S_2S_3 = zz.

Sample Input 3

ppppqqppqqqpqpqppqpqqqqpppqppq

Sample Output 3

580