Problem Statement

We have a grid with H rows and W columns, where all the squares are initially white.

You will perform some number of painting operations on the grid. In one operation, you can do one of the following two actions:

• Choose one row, then paint all the squares in that row black.
• Choose one column, then paint all the squares in that column black.

At least how many operations do you need in order to have N or more black squares in the grid? It is guaranteed that, under the conditions in Constraints, having N or more black squares is always possible by performing some number of operations.

Constraints

• 1 \leq H \leq 100
• 1 \leq W \leq 100
• 1 \leq N \leq H \times W
• All values in input are integers.

Sample Input 1

3
7
10

Sample Output 1

2

You can have 14 black squares in the grid by performing the "row" operation twice, on different rows.

Sample Input 2

14
12
112

Sample Output 2

8

Sample Input 3

2
100
200

Sample Output 3

2

Problem Statement

In a factory, there are N robots placed on a number line. Robot i is placed at coordinate X_i and can extend its arms of length L_i in both directions, positive and negative.

We want to remove zero or more robots so that the movable ranges of arms of no two remaining robots intersect. Here, for each i (1 \leq i \leq N), the movable range of arms of Robot i is the part of the number line between the coordinates X_i - L_i and X_i + L_i, excluding the endpoints.

Find the maximum number of robots that we can keep.

Constraints

• 1 \leq N \leq 100,000
• 0 \leq X_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq L_i \leq 10^9 (1 \leq i \leq N)
• If i \neq j, X_i \neq X_j.
• All values in input are integers.

Sample Input 1

4
2 4
4 3
9 3
100 5

Sample Output 1

3

By removing Robot 2, we can keep the other three robots.

Sample Input 2

2
8 20
1 10

Sample Output 2

1

Sample Input 3

5
10 1
2 1
4 1
6 1
8 1

Sample Output 3

5

Problem Statement

Given are three integers N, K, and S.

Find a sequence A_1, A_2, ..., A_N of N integers between 1 and 10^9 (inclusive) that satisfies the condition below. We can prove that, under the conditions in Constraints, such a sequence always exists.

• There are exactly K pairs (l, r) of integers such that 1 \leq l \leq r \leq N and A_l + A_{l + 1} + \cdots + A_r = S.

Constraints

• 1 \leq N \leq 10^5
• 0 \leq K \leq N
• 1 \leq S \leq 10^9
• All values in input are integers.

Sample Input 1

4 2 3

Sample Output 1

1 2 3 4

Two pairs (l, r) = (1, 2) and (3, 3) satisfy the condition in the statement.

Sample Input 2

5 3 100

Sample Output 2

50 50 50 30 70

Problem Statement

We have N cards numbered 1, 2, ..., N. Card i (1 \leq i \leq N) has an integer A_i written in red ink on one side and an integer B_i written in blue ink on the other side. Initially, these cards are arranged from left to right in the order from Card 1 to Card N, with the red numbers facing up.

Determine whether it is possible to have a non-decreasing sequence facing up from left to right (that is, for each i (1 \leq i \leq N - 1), the integer facing up on the (i+1)-th card from the left is not less than the integer facing up on the i-th card from the left) by repeating the operation below. If the answer is yes, find the minimum number of operations required to achieve it.

• Choose an integer i (1 \leq i \leq N - 1). Swap the i-th and (i+1)-th cards from the left, then flip these two cards.

Constraints

• 1 \leq N \leq 18
• 1 \leq A_i, B_i \leq 50 (1 \leq i \leq N)
• All values in input are integers.

Sample Input 1

3
3 4 3
3 2 3

Sample Output 1

1

By doing the operation once with i = 1, we have a sequence [2, 3, 3] facing up, which is non-decreasing.

Sample Input 2

2
2 1
1 2

Sample Output 2

-1

After any number of operations, we have the sequence [2, 1] facing up, which is not non-decreasing.

Sample Input 3

4
1 2 3 4
5 6 7 8

Sample Output 3

0

No operation may be required.

Sample Input 4

5
28 15 22 43 31
20 22 43 33 32

Sample Output 4

-1

Sample Input 5

5
4 46 6 38 43
33 15 18 27 37

Sample Output 5

3

Problem Statement

We have a connected undirected graph with N vertices and M edges. Edge i in this graph (1 \leq i \leq M) connects Vertex U_i and Vertex V_i bidirectionally. We are additionally given N integers D_1, D_2, ..., D_N.

Determine whether the conditions below can be satisfied by assigning a color - white or black - to each vertex and an integer weight between 1 and 10^9 (inclusive) to each edge in this graph. If the answer is yes, find one such assignment of colors and integers, too.

• There is at least one vertex assigned white and at least one vertex assigned black.
• For each vertex v (1 \leq v \leq N), the following holds.
  • The minimum cost to travel from Vertex v to a vertex whose color assigned is different from that of Vertex v by traversing the edges is equal to D_v.

Here, the cost of traversing the edges is the sum of the weights of the edges traversed.

Constraints

• 2 \leq N \leq 100,000
• 1 \leq M \leq 200,000
• 1 \leq D_i \leq 10^9
• 1 \leq U_i, V_i \leq N
• The given graph is connected and has no self-loops or multiple edges.
• All values in input are integers.

Sample Input 1

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

Sample Output 1

BWWBB
4
3
1
5
2

Assume that we assign the colors and integers as the sample output, and let us consider Vertex 5, for example. To travel from Vertex 5, which is assigned black, to a vertex that is assigned white with the minimum cost, we should make these moves: Vertex 5 \to Vertex 4 \to Vertex 2. The total cost of these moves is 7, which satisfies the condition. We can also verify that the condition is satisfied for other vertices.

Sample Input 2

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

Sample Output 2

-1

Sample Input 3

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

Sample Output 3

BBBW
1
1
1
2
1
1

Problem Statement

We have an H \times W grid, where each square is painted white or black in the initial state. Given are strings A_1, A_2, ..., A_H representing the colors of the squares in the initial state. For each pair (i, j) (1 \leq i \leq H, 1 \leq j \leq W), if the j-th character of A_i is ., the square at the i-th row and j-th column is painted white; if that character is #, that square is painted black.

Among the 2^{HW} ways for each square in the grid to be painted white or black, how many can be obtained from the initial state by performing the operations below any number of times (possibly zero) in any order? Find this count modulo 998,244,353.

• Choose one row, then paint all the squares in that row white.
• Choose one row, then paint all the squares in that row black.
• Choose one column, then paint all the squares in that column white.
• Choose one column, then paint all the squares in that column black.

Constraints

• 1 \leq H, W \leq 10
• |A_i| = W (1 \leq i \leq H)
• All strings A_i consist of . and #.
• H and W are integers.

Sample Input 1

2 2
#.
.#

Sample Output 1

15

For example, if we paint the second row black, the grid becomes:

#.
##

Sample Input 2

3 3
...
...
...

Sample Output 2

230

Sample Input 3

2 4
#...
...#

Sample Output 3

150

Sample Input 4

6 7
.......
.......
.#.....
..#....
.#.#...
.......

Sample Output 4

203949910