Problem Statement

You are given a 3-character string S, which is a concatenation of integers a and b between 1 and 9 (inclusive) and the character x in this order: axb.

Find the product of a and b.

Constraints

• The length of S is 3.
• The 1-st and 3-rd characters are digits between 1 and 9 (inclusive).
• The 2-nd character is x.

Sample Input 1

3x7

Sample Output 1

21

We have 3 \times 7 = 21, which should be printed.

Sample Input 2

9x9

Sample Output 2

81

Sample Input 3

1x1

Sample Output 3

1

Problem Statement

Takahashi has a string S consisting of lowercase English letters.

On this string, he will do the operation below just once.

• First, choose a non-negative integer K.
• Then, shift each character of S to the right by K (see below).

Here,

• a shifted to the right by 1 is b;
• b shifted to the right by 1 is c;
• c shifted to the right by 1 is d;
• \cdots
• y shifted to the right by 1 is z;
• z shifted to the right by 1 is a.

For example, b shifted to the right by 4 is f, and y shifted to the right by 3 is b.

You are given a string T. Determine whether Takahashi can make S equal T by the operation above.

Constraints

• Each of S and T is a string of length between 1 and 10^5 (inclusive) consisting of lowercase English letters.
• The lengths of S and T are equal.

Sample Input 1

abc
ijk

Sample Output 1

Yes

When Takahashi chooses K=8,

• a is shifted to the right by 8 and becomes i,
• b is shifted to the right by 8 and becomes j,
• c is shifted to the right by 8 and becomes k,

and now S and T are equal.
Therefore, he can make S equal T, so Yes should be printed.

Sample Input 2

z
a

Sample Output 2

Yes

Choosing K=1 makes S and T equal.
Note that the letter on the right of z is a.

Sample Input 3

ppq
qqp

Sample Output 3

No

There is no non-negative integer K that he can choose to make S equal T, so No should be printed.

Sample Input 4

atcoder
atcoder

Sample Output 4

Yes

Choosing K=0 makes S and T equal.

Problem Statement

Takahashi and Aoki each have a toy made by attaching M cords to N balls.

In Takahashi's toy, the balls are numbered 1, \dots, N, and the i-th cord ties Ball A_i and B_i.

Similarly, in Aoki's toy, the balls are numbered 1, \dots, N, and the i-th cord ties Ball C_i and D_i.

In each toy, no cord ties a ball to itself, and no two balls are tied by two or more different cords.

Snuke is wondering whether the two toys have the same shape.
Here, they are said to have the same shape when there is a sequence P that satisfies the conditions below.

• P is a permutation of (1, \dots, N).
• For every pair of integers i, j between 1 and N (inclusive), the following holds.
  • Balls i and j in Takahashi's toy are tied by a cord if and only if Balls P_i and P_j in Aoki's toy are tied by a cord.

If the two toys have the same shape, print Yes; otherwise, print No.

Constraints

• 1 \leq N \leq 8
• 0 \leq M \leq \frac{N(N - 1)}{2}
• 1 \leq A_i \lt B_i \leq N \, (1 \leq i \leq M)
• (A_i, B_i) \neq (A_j, B_j) \, (i \neq j)
• 1 \leq C_i \lt D_i \leq N \, (1 \leq i \leq M)
• (C_i, D_i) \neq (C_j, D_j) \, (i \neq j)
• All values in input are integers.

Sample Input 1

4 4
1 2
1 3
1 4
3 4
1 3
1 4
2 3
3 4

Sample Output 1

Yes

Takahashi's toy is illustrated on the left in the figure below, and Aoki's is illustrated on the right.

The following figure shows that the two toys have the same shape. The condition in the statement is satisfied when P = (3, 2, 1, 4), for example.

Sample Input 2

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

Sample Output 2

No

The two toys do not have the same shape.

Sample Input 3

8 0

Sample Output 3

Yes

Problem Statement

There is a H \times W-square grid with H horizontal rows and W vertical columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.
Each square is described by a character C_{i, j}, where C_{i, j} = . means (i, j) is an empty square, and C_{i, j} = # means (i, j) is a wall.

Takahashi is about to start walking in this grid. When he is on (i, j), he can go to (i, j + 1) or (i + 1, j). However, he cannot exit the grid or enter a wall square. He will stop when there is no more square to go to.

When starting on (1, 1), at most how many squares can Takahashi visit before he stops?

Constraints

• 1 \leq H, W \leq 100
• H and W are integers.
• C_{i, j} = . or C_{i, j} = #. (1 \leq i \leq H, 1 \leq j \leq W)
• C_{1, 1} = .

Sample Input 1

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

Sample Output 1

4

For example, by going (1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2), he can visit 4 squares.

He cannot visit 5 or more squares, so we should print 4.

Sample Input 2

1 1
.

Sample Output 2

1

Sample Input 3

5 5
.....
.....
.....
.....
.....

Sample Output 3

9

Problem Statement

There is a H \times W-square grid with H horizontal rows and W vertical columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.

The grid has a rook, initially on (x_1, y_1). Takahashi will do the following operation K times.

• Move the rook to a square that shares the row or column with the square currently occupied by the rook. Here, it must move to a square different from the current one.

How many ways are there to do the K operations so that the rook will be on (x_2, y_2) in the end? Since the answer can be enormous, find it modulo 998244353.

Constraints

• 2 \leq H, W \leq 10^9
• 1 \leq K \leq 10^6
• 1 \leq x_1, x_2 \leq H
• 1 \leq y_1, y_2 \leq W

Sample Input 1

2 2 2
1 2 2 1

Sample Output 1

2

We have the following two ways.

• First, move the rook from (1, 2) to (1, 1). Second, move it from (1, 1) to (2, 1).
• First, move the rook from (1, 2) to (2, 2). Second, move it from (2, 2) to (2, 1).

Sample Input 2

1000000000 1000000000 1000000
1000000000 1000000000 1000000000 1000000000

Sample Output 2

24922282

Be sure to find the count modulo 998244353.

Sample Input 3

3 3 3
1 3 3 3

Sample Output 3

9

Problem Statement

Given are two sequences of N integers each: A = (A_1, A_2, \ldots, A_N) and B = (B_1, B_2 \ldots, B_N).

On the sequence A, you can do the two operations below any number of times (possibly zero) in any order.

• Choose an integer i satisfying 1 \leq i \leq N, and increase or decrease A_i by 1, for the cost of X yen (Japanese currency).
• Choose an integer i satisfying 1 \leq i \leq N-1, and swap the values of A_i and A_{i+1}, for the cost of Y yen.

Print the minimum total cost needed to make the sequence A equal the sequence B by repeating the above.

Constraints

• 2 \leq N \leq 18
• 1 \leq X \leq 10^8
• 1 \leq Y \leq 10^{16}
• 1 \leq A_i, B_i \leq 10^8
• All values in input are integers.

Sample Input 1

4 3 5
4 2 5 2
6 4 2 1

Sample Output 1

16

Initialy, we have A = (4, 2, 5, 2).
The following sequence of operations makes A equal B.

• Pay X = 3 yen to increase the value of A_3 by 1, making A = (4, 2, 6, 2).
• Pay Y = 5 yen to swap the values of A_2 and A_3, making A = (4, 6, 2, 2).
• Pay Y = 5 yen to swap the values of A_1 and A_2, making A = (6, 4, 2, 2).
• Pay X = 3 yen to decrease the value of A_4 by 1, making A = (6, 4, 2, 1).

The total cost of these operations is 3+5+5+3 = 16 yen, which is the minimum possible.

Sample Input 2

5 12345 6789
1 2 3 4 5
1 2 3 4 5

Sample Output 2

0

A and B are equal from the beginning, so no operation is needed.

Sample Input 3

18 20719114 5117250357733867
10511029 36397527 63027379 44706927 47672230 79861204 57882493 42931589 51053644 52300688 43971370 26515475 62139996 41282303 34022578 12523039 6696497 64922712
14720753 4621362 25269832 91410838 86751784 32741849 6602693 60719353 28911226 88280613 18745325 80675202 34289776 37849132 99280042 73760634 43897718 40659077

Sample Output 3

13104119429316474

Note that values in input or output may not fit into 32-bit integer types.

Problem Statement

We have a directed graph with N vertices, called Vertex 1, Vertex 2, \ldots, Vertex N.

For each pair of integers such that 1 \leq i, j \leq N and i \neq j, there is a directed edge from Vertex i to Vertex j of weight (A_i + B_j) \bmod M. (Here, x \bmod y denotes the remainder when x is divided by y.)

There is no edge other than the above.

Print the shortest distance from Vertex 1 to Vertex N, that is, the minimum possible total weight of the edges in a path from Vertex 1 to Vertex N.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 2 \leq M \leq 10^9
• 0 \leq A_i, B_j < M
• All values in input are integers.

Sample Input 1

4 12
10 11 6 0
8 7 4 1

Sample Output 1

3

Below, i \rightarrow j denotes the directed edge from Vertex i to Vertex j.
Let us consider the path 1 \rightarrow 3 \rightarrow 2 \rightarrow 4.

• Edge 1\rightarrow 3 weighs (A_1 + B_3) \bmod M = (10 + 4) \bmod 12 = 2,
• Edge 3 \rightarrow 2 weighs (A_3 + B_2) \bmod M = (6 + 7) \bmod 12 = 1,
• Edge 2\rightarrow 4 weighs (A_2 + B_4) \bmod M = (11 + 1) \bmod 12 = 0.

Thus, the total weight of the edges in this path is 2 + 1 + 0 = 3.
This is the minimum possible sum for a path from Vertex 1 to Vertex N.

Sample Input 2

10 1000
785 934 671 520 794 168 586 667 411 332
363 763 40 425 524 311 139 875 548 198

Sample Output 2

462

Problem Statement

We have an H \times W chessboard with H rows and W columns, and a king.
Let (i, j) denote the square at the i-th row from the top (1 \leq i \leq H) and j-th column from the left (1 \leq j \leq W).
The king can move one square in any direction. Formally, the king on (i,j) can move to (k,l) if and only if \max(|i-k|,|j-l|) = 1.

A tour is the process of moving the king on the H \times W chessboard as follows.

• Start by putting the king on (1, 1). Then, move the king to put it on each square exactly once.

For example, when H = 2, W = 3, going (1,1) \to (1,2) \to (1, 3) \to (2, 3) \to (2, 2) \to (2, 1) is a valid tour.

You are given a square (a, b) other than (1, 1). Construct a tour ending on (a,b) and print it. It can be proved that a solution always exists under the Constraints of this problem.

Constraints

• 2 \leq H \leq 100
• 2 \leq W \leq 100
• 1 \leq a \leq H
• 1 \leq b \leq W
• (a, b) \neq (1, 1)
• All values in input are integers.

Sample Input 1

3 2 3 2

Sample Output 1

1 1
1 2
2 1
2 2
3 1
3 2

The king goes (1, 1) \to (1, 2) \to (2, 1) \to (2, 2)\to (3, 1) \to (3, 2), which is indeed a tour ending on (3, 2).
There are some other valid tours, three of which are listed below.

• (1, 1) \to (1, 2) \to (2, 2) \to (2, 1) \to (3, 1) \to (3, 2)
• (1, 1) \to (2, 1) \to (1, 2) \to (2, 2) \to (3, 1) \to (3, 2)
• (1, 1) \to (2, 2) \to (1, 2) \to (2, 1) \to (3, 1) \to (3, 2)