Problem Statement

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

Extract all elements of A that are multiples of K, divide them by K, and print the quotients.

Constraints

• 1\leq N,K\leq 100
• 1\leq A_1 < A_2 < \ldots < A_N \leq 100
• A has at least one multiple of K.
• All given numbers are integers.

Sample Input 1

5 2
2 5 6 7 10

Sample Output 1

1 3 5

The multiples of 2 among the elements in A are 2, 6, and 10. Divide them by 2 to get 1, 3, and 5, and print them in ascending order with spaces in between.

Sample Input 2

3 1
3 4 7

Sample Output 2

3 4 7

Sample Input 3

5 10
50 51 54 60 65

Sample Output 3

5 6

Problem Statement

There is a grid with H horizontal rows and W vertical columns. Let (i,j) denote the square at the i-th row from the top and the j-th column from the left.
Find the number of squares that share a side with Square (R, C).

Here, two squares (a,b) and (c,d) are said to share a side if and only if |a-c|+|b-d|=1 (where |x| denotes the absolute value of x).

Constraints

• All values in input are integers.
• 1 \le R \le H \le 10
• 1 \le C \le W \le 10

Sample Input 1

3 4
2 2

Sample Output 1

4

We will describe Sample Inputs/Outputs 1,2, and 3 at once below Sample Output 3.

Sample Input 2

3 4
1 3

Sample Output 2

3

Sample Input 3

3 4
3 4

Sample Output 3

2

When H=3 and W=4, the grid looks as follows.

• For Sample Input 1, there are 4 squares adjacent to Square (2,2).
• For Sample Input 2, there are 3 squares adjacent to Square (1,3).
• For Sample Input 3, there are 2 squares adjacent to Square (3,4).

Sample Input 4

1 10
1 5

Sample Output 4

2

Sample Input 5

8 1
8 1

Sample Output 5

1

Sample Input 6

1 1
1 1

Sample Output 6

0

Problem Statement

You are given a string S. Find the lexicographically smallest string S' obtained by permuting the characters of S.

Here, for different two strings s = s_1 s_2 \ldots s_n and t = t_1 t_2 \ldots t_m, s \lt t holds lexicographically when one of the conditions below is satisfied.

• There is an integer i\ (1 \leq i \leq \min(n,m)) such that s_i \lt t_i and s_j=t_j for all integers j\ (1 \leq j \lt i).
• s_i = t_i for all integers i\ (1 \leq i \leq \min(n,m)), and n \lt m.

Constraints

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

Sample Input 1

aba

Sample Output 1

aab

Three strings can be obtained by permuting aba:

• aba
• aab
• baa

The lexicographically smallest among them is aab.

Sample Input 2

zzzz

Sample Output 2

zzzz

Problem Statement

There is a rectangular chocolate consisting of H rows and W columns of blocks.

You are given Q queries; process them in order and find the answer to each query. Each query is in one of the following formats:

• Type 1: An integer R is given. Find the number of chocolate blocks in the bottom R rows, then eat them.

• Type 2: An integer C is given. Find the number of chocolate blocks in the rightmost C columns, then eat them.

When the queries are processed in order, the chocolate remains rectangular after each query is processed, and it has at least R + 1 rows immediately before processing a type 1 query and has at least C + 1 columns immediately before processing a type 2 query.

Constraints

• 2 \leq H, W \leq 100
• 1 \leq Q \leq 100
• For type 1 queries, 1 \leq R.
• When the queries are processed in order, the chocolate has at least R + 1 rows immediately before processing a type 1 query.
• For type 2 queries, 1 \leq C.
• When the queries are processed in order, the chocolate has at least C + 1 columns immediately before processing a type 2 query.
• All input values are integers.

Sample Input 1

7 9 5
2 4
1 3
2 1
2 1
1 3

Sample Output 1

28
15
4
4
9

Initially, the chocolate is a rectangle with 7 rows and 9 columns.

For the first query, the number of chocolate blocks in the rightmost 4 columns is 28, so output 28. The chocolate becomes 7 rows and 5 columns.

For the second query, the number of chocolate blocks in the bottom 3 rows is 15, so output 15. The chocolate becomes 4 rows and 5 columns.

For the third query, the number of chocolate blocks in the rightmost 1 column is 4, so output 4. The chocolate becomes 4 rows and 4 columns.

For the fourth query, the number of chocolate blocks in the rightmost 1 column is 4, so output 4. The chocolate becomes 4 rows and 3 columns.

For the fifth query, the number of chocolate blocks in the bottom 3 rows is 9, so output 9. The chocolate becomes 1 row and 3 columns.

Problem Statement

Takahashi has N pairs of socks, and the i-th pair consists of two socks of color i. One day, after organizing his chest of drawers, Takahashi realized that he had lost one sock each of colors A_1, A_2, \dots, A_K, so he decided to use the remaining 2N-K socks to make \lfloor\frac{2N-K}{2}\rfloor new pairs of socks, each pair consisting of two socks. The weirdness of a pair of a sock of color i and a sock of color j is defined as |i-j|, and Takahashi wants to minimize the total weirdness.

Find the minimum possible total weirdness when making \lfloor\frac{2N-K}{2}\rfloor pairs from the remaining socks. Note that if 2N-K is odd, there will be one sock that is not included in any pair.

Constraints

• 1\leq K\leq N \leq 2\times 10^5
• 1\leq A_1 < A_2 < \dots < A_K \leq N
• All input values are integers.

Sample Input 1

4 2
1 3

Sample Output 1

2

Below, let (i,j) denote a pair of a sock of color i and a sock of color j.

There are 1, 2, 1, 2 socks of colors 1, 2, 3, 4, respectively. Creating the pairs (1,2),(2,3),(4,4) results in a total weirdness of |1-2|+|2-3|+|4-4|=2, which is the minimum.

Sample Input 2

5 1
2

Sample Output 2

0

The optimal solution is to make the pairs (1,1),(3,3),(4,4),(5,5) and leave one sock of color 2 as a surplus (not included in any pair).

Sample Input 3

8 5
1 2 4 7 8

Sample Output 3

2

Problem Statement

We have two figures S and T on a two-dimensional grid with square cells.

S lies within a grid with N rows and N columns, and consists of the cells where S_{i,j} is #.
T lies within the same grid with N rows and N columns, and consists of the cells where T_{i,j} is #.

Determine whether it is possible to exactly match S and T by 90-degree rotations and translations.

Constraints

• 1 \leq N \leq 200
• Each of S and T consists of # and ..
• Each of S and T contains at least one #.

Sample Input 1

5
.....
..#..
.###.
.....
.....
.....
.....
....#
...##
....#

Sample Output 1

Yes

We can match S to T by rotating it 90-degrees counter-clockwise and translating it.

Sample Input 2

5
#####
##..#
#..##
#####
.....
#####
#..##
##..#
#####
.....

Sample Output 2

No

It is impossible to match them by 90-degree rotations and translations.

Sample Input 3

4
#...
..#.
..#.
....
#...
#...
..#.
....

Sample Output 3

Yes

Each of S and T may not be connected.

Sample Input 4

4
#...
.##.
..#.
....
##..
#...
..#.
....

Sample Output 4

No

Note that it is not allowed to rotate or translate just a part of a figure; it is only allowed to rotate or translate a whole figure.

Problem Statement

There are N+2 cells arranged in a row. Let cell i denote the i-th cell from the left.

There is one stone placed in each of the cells from cell 1 to cell N.
For each 1 \leq i \leq N, the stone in cell i is white if S_i is W, and black if S_i is B.
Cells N+1 and N+2 are empty.

You can perform the following operation any number of times (possibly zero):

• Choose a pair of adjacent cells that both contain stones, and move these two stones to the empty two cells while preserving their order.
  More precisely, choose an integer x such that 1 \leq x \leq N+1 and both cells x and x+1 contain stones. Let k and k+1 be the empty two cells. Move the stones from cells x and x+1 to cells k and k+1, respectively.

Determine if it is possible to achieve the following state, and if so, find the minimum number of operations required:

• Each of the cells from cell 1 to cell N contains one stone, and for each 1 \leq i \leq N, the stone in cell i is white if T_i is W, and black if T_i is B.

Constraints

• 2 \leq N \leq 14
• N is an integer.
• Each of S and T is a string of length N consisting of B and W.

Sample Input 1

6
BWBWBW
WWWBBB

Sample Output 1

4

Using . to represent an empty cell, the desired state can be achieved in four operations as follows, which is the minimum:

• BWBWBW..
• BW..BWBW
• BWWBB..W
• ..WBBBWW
• WWWBBB..

Sample Input 2

6
BBBBBB
WWWWWW

Sample Output 2

-1

Sample Input 3

14
BBBWBWWWBBWWBW
WBWWBBWWWBWBBB

Sample Output 3

7

Problem Statement

There are N cells arranged in a row from left to right.
The i-th cell from the left (1\leq i\leq N) is called cell i.
Initially, all cells are painted white.

Process Q queries in order.
The i-th query (1\leq i\leq Q) is as follows:

Two integers (L_i,R_i) (1\leq L_i\leq R_i\leq N) are given.
Paint all cells L_i, L_i+1, \ldots, R_i black.
Here, cells that were painted white are now painted black, and cells that were painted black remain as is.
After that, find the number of cells (among the N cells) that are painted white.

Constraints

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

Sample Input 1

10 5
3 5
8 9
5 8
2 9
6 6

Sample Output 1

7
5
3
2
2

Initially, 10 cells are arranged in a row from left to right.

• The first query paints cells 3,4,5 black. After the operation, the cells painted white are cells 1,2,6,7,8,9,10, which is 7 cells.
• The second query paints cells 8,9 black. After the operation, the cells painted white are 1,2,6,7,10, which is 5 cells.
• The third query paints cells 5,6,7,8 black. After the operation, the cells painted white are 1,2,10, which is 3 cells.
• The fourth query paints cells 2,3,\ldots,9 black. After the operation, the cells painted white are 1,10, which is 2 cells.
• The fifth query paints cell 6 black. After the operation, the cells painted white are cells 1,10, which is 2 cells.

Thus, output 7,5,3,2,2 in this order on each line.

Sample Input 2

1000000000 1
1 500000000

Sample Output 2

500000000

Problem Statement

There are N cards numbered 1,\ldots,N. Card i has P_i written on the front and Q_i written on the back.
Here, P=(P_1,\ldots,P_N) and Q=(Q_1,\ldots,Q_N) are permutations of (1, 2, \dots, N).

How many ways are there to choose some of the N cards such that the following condition is satisfied? Find the count modulo 998244353.

Condition: every number 1,2,\ldots,N is written on at least one of the chosen cards.

Constraints

• 1 \leq N \leq 2\times 10^5
• 1 \leq P_i,Q_i \leq N
• P and Q are permutations of (1, 2, \dots, N).
• All values in input are integers.

Sample Input 1

3
1 2 3
2 1 3

Sample Output 1

3

For example, if you choose Cards 1 and 3, then 1 is written on the front of Card 1, 2 on the back of Card 1, and 3 on the front of Card 3, so this combination satisfies the condition.

There are 3 ways to choose cards satisfying the condition: \{1,3\},\{2,3\},\{1,2,3\}.

Sample Input 2

5
2 3 5 4 1
4 2 1 3 5

Sample Output 2

12

Sample Input 3

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

Sample Output 3

1