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 cells numbered from 1 to N in a row. Initially, M cells contain stones, and cell X_i contains A_i stones (1 \leq i \leq M).

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

• If cell i (1 \leq i \leq N-1) contains a stone, move one stone from cell i to cell i+1.

Find the minimum number of operations required to reach a state where each of the N cells contains exactly one stone. If it is impossible, print -1.

Constraints

• 2 \leq N \leq 2 \times 10^{9}
• 1 \leq M \leq 2 \times 10^{5}
• M \leq N
• 1 \leq X_i \leq N (1 \leq i \leq M)
• X_i \neq X_j (1 \leq i < j \leq M)
• 1 \leq A_i \leq 2 \times 10^{9} (1 \leq i \leq M)
• All input values are integers.

Sample Input 1

5 2
1 4
3 2

Sample Output 1

4

You can reach a state where each of the five cells contains exactly one stone with four operations as follows:

• Move one stone from cell 1 to cell 2.
• Move one stone from cell 2 to cell 3.
• Move one stone from cell 4 to cell 5.
• Move one stone from cell 1 to cell 2.

It is impossible to achieve the goal in three or fewer operations. Therefore, print 4.

Sample Input 2

10 3
1 4 8
4 2 4

Sample Output 2

-1

No matter how you perform the operations, you cannot reach a state where all ten cells contain exactly one stone. Therefore, print -1.

Problem Statement

For positive integers x and y, define f(x, y) as follows:

• Interpret the decimal representations of x and y as strings and concatenate them in this order to obtain a string z. The value of f(x, y) is the value of z when interpreted as a decimal integer.

For example, f(3, 14) = 314 and f(100, 1) = 1001.

You are given a sequence of positive integers A = (A_1, \ldots, A_N) of length N. Find the value of the following expression modulo 998244353:

Constraints

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

Sample Input 1

3
3 14 15

Sample Output 1

2044

• f(A_1, A_2) = 314
• f(A_1, A_3) = 315
• f(A_2, A_3) = 1415

Thus, the answer is f(A_1, A_2) + f(A_1, A_3) + f(A_2, A_3) = 2044.

Sample Input 2

5
1001 5 1000000 1000000000 100000

Sample Output 2

625549048

Be sure to calculate the value modulo 998244353.

Problem Statement

There are N cities in a certain country.
You will travel from your office in city 1 to a destination in city N, via zero or more cities.
Two types of transportation are available: company car and train. The time required to travel from city i to city j is as follows:

• D_{i,j} \times A minutes by company car, and
• D_{i,j} \times B + C minutes by train.

You can switch from company car to train, but not vice versa.
You can do so without spending time, but only in a city.

What is the minimum time in minutes to travel from city 1 to city N?

Constraints

• 2 \leq N \leq 1000
• 1 \leq A, B, C \leq 10^6
• D_{i,j} \leq 10^6
• D_{i,i} = 0
• D_{i,j} = D_{j,i} > 0 (i \neq j)
• All input values are integers.

Sample Input 1

4 8 5 13
0 6 2 15
6 0 3 5
2 3 0 13
15 5 13 0

Sample Output 1

78

You can travel from city 1 to city 4 in a total of 78 minutes by moving as follows.

• Travel by company car from city 1 to city 3. This takes 2 \times 8 = 16 minutes.
• Travel by company car from city 3 to city 2. This takes 3 \times 8 = 24 minutes.
• Travel by train from city 2 to city 4. This takes 5 \times 5 + 13 = 38 minutes.

It is impossible to travel from city 1 to city 4 in less than 78 minutes.

Sample Input 2

3 1 1000000 1000000
0 10 1
10 0 10
1 10 0

Sample Output 2

1

Sample Input 3

5 954257 954213 814214
0 84251 214529 10017 373342
84251 0 91926 32336 164457
214529 91926 0 108914 57762
10017 32336 108914 0 234705
373342 164457 57762 234705 0

Sample Output 3

168604826785

Problem Statement

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

There are N horizontal bars numbered from 1 to N placed on the grid. Bar i consists of L_i blocks of size 1 \times 1 connected horizontally, and its leftmost block is initially at cell (R_i, C_i). That is, initially, bar i occupies the cells (R_i, C_i), (R_i, C_i + 1), \dots, (R_i, C_i + L_i - 1). It is guaranteed that there is no cell occupied by two different bars.

The current time is t = 0. At every time t = 0.5 + n for some non-negative integer n, the following occurs in order of i = 1, 2, \dots, N:

• If bar i is not on the bottom row (the H-th row), and none of the cells directly below the cells occupied by bar i is occupied by any bar, then bar i moves down by one cell. That is, if at that time bar i occupies the cells (r,C_i),(r,C_i+1),\dots,(r,C_i+L_i-1)\ (r < H), and the cell (r + 1, C_i + j) is not occupied by any bar for all j (0 \leq j \leq L_i - 1), then bar i now occupies (r + 1, C_i), (r + 1, C_i + 1), \dots, (r + 1, C_i + L_i - 1).
• Otherwise, nothing happens.

Let (R'_i, C_i), (R'_i, C_i + 1), \dots, (R'_i, C_i + L_i - 1) be the cells occupied by bar i at time t = 10^{100}. Find R'_1, R'_2, \dots, R'_N.

Constraints

• 1 \leq H, W \leq 2 \times 10^5
• 1 \leq N \leq 2 \times 10^5
• 1 \leq R_i \leq H
• 1 \leq C_i \leq W
• 1 \leq L_i \leq W - C_i + 1
• In the initial state, there is no cell occupied by two different bars.
• All input values are integers.

Sample Input 1

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

Sample Output 1

2
4
3
4

The following three diagrams represent the grid at times t = 0, 1, and 2 from left to right. Colored rectangles represent the bars, and the number inside each rectangle indicates its bar number.

The changes in the grid state are explained as follows:

• At t = 0.5:
  • i = 1: The cells directly below bar 1 are (2,2),(2,3),(2,4). Among these, (2,2) is occupied by bar 3 and (2,4) is occupied by bar 4, so nothing happens.
  • i = 2: The cells directly below bar 2 are (4,2),(4,3), which are not occupied by any other bar, so bar 2 moves down by one cell.
  • i = 3: The cells directly below bar 3 are (3,1),(3,2), which are not occupied by any other bar, so bar 3 moves down by one cell.
  • i = 4: The cell directly below bar 4 is (3,4), which is not occupied by any other bar, so bar 4 moves down by one cell.
• At t = 1.5:
  • i = 1: The cells directly below bar 1 are (2,2),(2,3),(2,4), which are not occupied by any other bar, so bar 1 moves down by one cell.
  • i = 2: Bar 2 is on the bottom row, so nothing happens.
  • i = 3: The cells directly below bar 3 are (4,1),(4,2). Among these, (4,2) is occupied by bar 2, so nothing happens.
  • i = 4: The cell directly below bar 4 is (4,4), which is not occupied by any other bar, so bar 4 moves down by one cell.

At times t = 2.5, 3.5, \dots, there is no bar such that the cells directly below it are all unoccupied, so nothing happens. Thus, the grid at time t = 10^{100} is the same as at t = 2 (the rightmost diagram above).

Therefore, R'_1 = 2, R'_2 = 4, R'_3 = 3, R'_4 = 4.

Sample Input 2

382 382 3
3 3 3
8 8 8
2 2 2

Sample Output 2

382
382
381

Sample Input 3

5 10 8
2 2 1
4 3 1
4 8 2
1 2 2
2 5 3
5 4 3
4 5 2
1 5 2

Sample Output 3

5
5
5
4
3
5
4
2