Problem Statement

You are given an integer N between 1 and 9, inclusive, as input.

Concatenate N copies of the digit N and print the resulting string.

Constraints

• N is an integer between 1 and 9, inclusive.

Sample Input 1

3

Sample Output 1

333

Concatenate three copies of the digit 3 to yield the string 333.

Sample Input 2

9

Sample Output 2

999999999

Problem Statement

Takahashi turned on a computer at time 0 and clicked the mouse N times. The i-th (1 \le i \le N) click was at time T_i.

If he consecutively clicked the mouse at time x_1 and time x_2 (where x_1 < x_2), a double click is said to be fired at time x_2 if and only if x_2 - x_1 \le D.

What time was a double click fired for the first time? If no double click was fired, print -1 instead.

Constraints

• 1 \le N \le 100
• 1 \le D \le 10^9
• 1 \le T_i \le 10^9(1 \le i \le N)
• T_i < T_{i+1}(1 \le i \le N-1)
• All values in the input are integers.

Sample Input 1

4 500
300 900 1300 1700

Sample Output 1

1300

Takahashi clicked the mouse at time 900 and 1300. Since 1300 - 900 \le 500, a double click was fired at time 1300.

A double click had not been fired before time 1300, so 1300 should be printed.

Sample Input 2

5 99
100 200 300 400 500

Sample Output 2

-1

No double click was fired, so print -1.

Sample Input 3

4 500
100 600 1100 1600

Sample Output 3

600

If multiple double clicks were fired, be sure to print only the first such event.

Problem Statement

You are given a positive integer N.

We have a grid with N rows and N columns, where the square at the i-th row from the top and j-th column from the left has a digit A_{i,j} written on it.

Assume that the upper and lower edges of this grid are connected, as well as the left and right edges. In other words, all of the following holds.

• (N,i) is just above (1,i), and (1,i) is just below (N,i). (1\le i\le N).
• (i,N) is just to the left of (i,1), and (i,1) is just to the right of (i,N). (1\le i\le N).

Takahashi will first choose one of the following eight directions: up, down, left, right, and the four diagonal directions. Then, he will start on a square of his choice and repeat moving one square in the chosen direction N-1 times.

In this process, Takahashi visits N squares. Find the greatest possible value of the integer that is obtained by arranging the digits written on the squares visited by Takahashi from left to right in the order visited by him.

Constraints

• 1 \le N \le 10
• 1 \le A_{i,j} \le 9
• All values in input are integers.

Sample Input 1

4
1161
1119
7111
1811

Sample Output 1

9786

If Takahashi starts on the square at the 2-nd row from the top and 4-th column from the left and goes down and to the right, the integer obtained by arranging the digits written on the visited squares will be 9786. It is impossible to make a value greater than 9786, so the answer is 9786.

Sample Input 2

10
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111

Sample Output 2

1111111111

Note that the answer may not fit into a 32-bit integer.

Problem Statement

Takahashi invented Tak Code, a two-dimensional code. A TaK Code satisfies all of the following conditions:

• It is a region consisting of nine horizontal rows and nine vertical columns.
• All the 18 cells in the top-left and bottom-right three-by-three regions are black.
• All the 14 cells that are adjacent (horizontally, vertically, or diagonally) to the top-left or bottom-right three-by-three region are white.

It is not allowed to rotate a TaK Code.

You are given a grid with N horizontal rows and M vertical columns. The state of the grid is described by N strings, S_1,\ldots, and S_N, each of length M. The cell at the i-th row from the top and j-th column from the left is black if the j-th character of S_i is #, and white if it is ..

Find all the nine-by-nine regions, completely contained in the grid, that satisfy the conditions of a TaK Code.

Constraints

• 9 \leq N,M \leq 100
• N and M are integers.
• S_i is a string of length M consisting of . and #.

Sample Input 1

19 18
###......###......
###......###......
###..#...###..#...
..............#...
..................
..................
......###......###
......###......###
......###......###
.###..............
.###......##......
.###..............
............###...
...##.......###...
...##.......###...
.......###........
.......###........
.......###........
........#.........

Sample Output 1

1 1
1 10
7 7
10 2

A TaK Code looks like the following, where # is a black cell, . is a white cell, and ? can be either black or white.

###.?????
###.?????
###.?????
....?????
?????????
?????....
?????.###
?????.###
?????.###

In the grid given by the input, the nine-by-nine region, whose top-left cell is at the 10-th row from the top and 2-nd column from the left, satisfies the conditions of a TaK Code, as shown below.

###......
###......
###......
.........
..##.....
..##.....
......###
......###
......###

Sample Input 2

9 21
###.#...........#.###
###.#...........#.###
###.#...........#.###
....#...........#....
#########...#########
....#...........#....
....#.###...###.#....
....#.###...###.#....
....#.###...###.#....

Sample Output 2

1 1

Sample Input 3

18 18
######............
######............
######............
######............
######............
######............
..................
..................
..................
..................
..................
..................
............######
............######
............######
............######
............######
............######

Sample Output 3

There may be no region that satisfies the conditions of TaK Code.

Problem Statement

On an xy-coordinate plane, is there a lattice point whose distances from two lattice points (x_1, y_1) and (x_2, y_2) are both \sqrt{5}?

Notes

A point on an xy-coordinate plane whose x and y coordinates are both integers is called a lattice point.
The distance between two points (a, b) and (c, d) is defined to be the Euclidean distance between them, \sqrt{(a - c)^2 + (b-d)^2}.

The following figure illustrates an xy-plane with a black circle at (0, 0) and white circles at the lattice points whose distances from (0, 0) are \sqrt{5}. (The grid shows where either x or y is an integer.)

Constraints

• -10^9 \leq x_1 \leq 10^9
• -10^9 \leq y_1 \leq 10^9
• -10^9 \leq x_2 \leq 10^9
• -10^9 \leq y_2 \leq 10^9
• (x_1, y_1) \neq (x_2, y_2)
• All values in input are integers.

Sample Input 1

0 0 3 3

Sample Output 1

Yes

• The distance between points (2,1) and (x_1, y_1) is \sqrt{(0-2)^2 + (0-1)^2} = \sqrt{5};
• the distance between points (2,1) and (x_2, y_2) is \sqrt{(3-2)^2 + (3-1)^2} = \sqrt{5};
• point (2, 1) is a lattice point,

so point (2, 1) satisfies the condition. Thus, Yes should be printed.
One can also assert in the same way that (1, 2) also satisfies the condition.

Sample Input 2

0 1 2 3

Sample Output 2

No

No lattice point satisfies the condition, so No should be printed.

Sample Input 3

1000000000 1000000000 999999999 999999999

Sample Output 3

Yes

Point (10^9 + 1, 10^9 - 2) and point (10^9 - 2, 10^9 + 1) satisfy the condition.

Problem Statement

There is a grid with H rows and W columns.

Each cell of the grid is land or sea, which is represented by H strings S_1, S_2, \ldots, S_H of length W. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left, and (i, j) is land if the j-th character of S_i is ., and (i, j) is sea if the character is #.

The constraints guarantee that all cells on the perimeter of the grid (that is, the cells (i, j) that satisfy at least one of i = 1, i = H, j = 1, j = W) are sea.

Takahashi's spaceship has crash-landed on a cell in the grid. Afterward, he moved N times on the grid following the instructions represented by a string T of length N consisting of L, R, U, and D. For i = 1, 2, \ldots, N, the i-th character of T describes the i-th move as follows:

• L indicates a move of one cell to the left. That is, if he is at (i, j) before the move, he will be at (i, j-1) after the move.
• R indicates a move of one cell to the right. That is, if he is at (i, j) before the move, he will be at (i, j+1) after the move.
• U indicates a move of one cell up. That is, if he is at (i, j) before the move, he will be at (i-1, j) after the move.
• D indicates a move of one cell down. That is, if he is at (i, j) before the move, he will be at (i+1, j) after the move.

It is known that all cells along his path (including the cell where he crash-landed and the cell he is currently on) are not sea. Print the number of cells that could be his current position.

Constraints

• H, W, and N are integers.
• 3 \leq H, W \leq 500
• 1 \leq N \leq 500
• T is a string of length N consisting of L, R, U, and D.
• S_i is a string of length W consisting of . and #.
• There is at least one cell that could be Takahashi's current position.
• All cells on the perimeter of the grid are sea.

Sample Input 1

6 7 5
LULDR
#######
#...#.#
##...##
#.#...#
#...#.#
#######

Sample Output 1

2

The following two cases are possible, so there are two cells that could be Takahashi's current position: (3, 4) and (4, 5).

• He crash-landed on cell (3, 5) and moved (3, 5) \rightarrow (3, 4) \rightarrow (2, 4) \rightarrow (2, 3) \rightarrow (3, 3) \rightarrow (3, 4).
• He crash-landed on cell (4, 6) and moved (4, 6) \rightarrow (4, 5) \rightarrow (3, 5) \rightarrow (3, 4) \rightarrow (4, 4) \rightarrow (4, 5).

Sample Input 2

13 16 9
ULURDLURD
################
##..##.#..####.#
###.#..#.....#.#
#..##..#####.###
#...#..#......##
###.##.#..#....#
##.#####....##.#
###.###.#.#.#..#
######.....##..#
#...#.#.######.#
##..###..#..#.##
#...#.#.#...#..#
################

Sample Output 2

6

Problem Statement

There are N ants on a number line, labeled 1 to N. Ant i (1 \leq i \leq N) starts at coordinate X_i and faces either a positive or negative direction. Initially, all ants are at distinct coordinates. The direction each ant is facing is represented by a binary string S of length N, where ant i is facing the negative direction if S_i is 0 and the positive direction if S_i is 1.

Let the current time be 0, and the ants move in their respective directions at a speed of 1 unit per unit time for (T+0.1) units of time until time (T+0.1). If multiple ants reach the same coordinate, they pass through each other without changing direction or speed. After (T+0.1) units of time, all ants stop.

Find the number of pairs (i, j) such that 1 \leq i < j \leq N and ants i and j pass each other from now before time (T+0.1).

Constraints

• 2 \leq N \leq 2 \times 10^{5}
• 1 \leq T \leq 10^{9}
• S is a string of length N consisting of 0 and 1.
• -10^{9} \leq X_i \leq 10^{9} (1 \leq i \leq N)
• X_i \neq X_j (1 \leq i < j \leq N)
• N, T, and X_i (1 \leq i \leq N) are integers.

Sample Input 1

6 3
101010
-5 -1 0 1 2 4

Sample Output 1

5

The following five pairs of ants pass each other:

• Ant 3 and ant 4 pass each other at time 0.5.
• Ant 5 and ant 6 pass each other at time 1.
• Ant 1 and ant 2 pass each other at time 2.
• Ant 3 and ant 6 pass each other at time 2.
• Ant 1 and ant 4 pass each other at time 3.

No other pairs of ants pass each other, so print 5.

Sample Input 2

13 656320850
0100110011101
-900549713 -713494784 -713078652 -687818593 -517374932 -498415009 -472742091 -390030458 -379340552 -237481538 -44636942 352721061 695864366

Sample Output 2

14

Problem Statement

The Republic of AtCoder has N cities, called City 1, City 2, \ldots, City N. Initially, there was a bidirectional road between every pair of different cities, but M of these roads have become unusable due to deterioration over time. More specifically, for each 1\leq i \leq M, the road connecting City U_i and City V_i has become unusable.

Takahashi will go for a K-day trip that starts and ends in City 1. Formally speaking, a K-day trip that starts and ends in City 1 is a sequence of K+1 cities (A_0, A_1, \ldots, A_K) such that A_0=A_K=1 holds and for each 0\leq i\leq K-1, A_i and A_{i+1} are different and there is still a usable road connecting City A_i and City A_{i+1}.

Print the number of different K-day trips that start and end in City 1, modulo 998244353. Here, two K-day trips (A_0, A_1, \ldots, A_K) and (B_0, B_1, \ldots, B_K) are said to be different when there exists an i such that A_i\neq B_i.

Constraints

• 2 \leq N \leq 5000
• 0 \leq M \leq \min\left( \frac{N(N-1)}{2},5000 \right)
• 2 \leq K \leq 5000
• 1 \leq U_i<V_i \leq N
• All pairs (U_i, V_i) are pairwise distinct.
• All values in input are integers.

Sample Input 1

3 1 4
2 3

Sample Output 1

4

There are four different trips as follows.

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

No other trip is valid, so we should print 4.

Sample Input 2

3 3 3
1 2
1 3
2 3

Sample Output 2

0

No road remains usable, so there is no valid trip.

Sample Input 3

5 3 100
1 2
4 5
2 3

Sample Output 3

428417047

Problem Statement

There is a simple graph with N vertices numbered 1 to N and M edges numbered 1 to M. Edge i connects vertices u_i and v_i.
Each vertex has one lamp on it. Initially, all the lamps are off.

Determine whether it is possible to turn exactly K lamps on by performing the following operation between 0 and M times, inclusive.

• Choose one edge. Let u and v be the endpoints of the edge. Toggle the states of the lamps on u and v. That is, if the lamp is on, turn it off, and vice versa.

If it is possible to turn exactly K lamps on, print a sequence of operations that achieves this state.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq \min\left( 2 \times 10^5, \frac{N(N-1)}{2} \right)
• 0 \leq K \leq N
• 1 \leq u_i < v_i \leq N
• The given graph is simple.
• All input values are integers.

Sample Input 1

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

Sample Output 1

Yes
3
3 4 5

If we operate according to the sample output, it will go as follows:

• Choose edge 3. Turn on the lamps on vertex 2 and vertex 4.
• Choose edge 4. Turn on the lamps on vertex 3 and vertex 5.
• Choose edge 5. Turn on the lamp on vertex 1 and turn off the lamp on vertex 5.

After completing all operations, the lamps on vertices 1, 2, 3, and 4 are on. Therefore, this sequence of operations satisfies the conditions.

Other possible sequences of operations that satisfy the conditions include X = 4, (e_1,e_2,e_3,e_4) = (3,4,3,1). (It is allowed to choose the same edge more than once.)

Sample Input 2

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

Sample Output 2

No

Sample Input 3

10 10 6
2 5
2 6
3 5
3 8
4 6
4 8
5 9
6 7
6 10
7 9

Sample Output 3

Yes
3
10 9 6