Problem Statement

Naohiro has a monster. The monster's current health is H.
He also has N kinds of potions, numbered from 1 to N in ascending order of effectiveness.
If you give the monster potion n, its health will increase by P_n. Here, P_1 \lt P_2 \lt \dots \lt P_N.

He wants to increase the monster's health to X or above by giving it one of the potions.
Print the number of the least effective potion that can achieve the purpose. (The constraints guarantee that such a potion exists.)

Constraints

• 2 \leq N \leq 100
• 1 \leq H \lt X \leq 999
• 1 \leq P_1 \lt P_2 \lt \dots \lt P_N = 999
• All input values are integers.

Sample Input 1

3 100 200
50 200 999

Sample Output 1

2

Below is the change in the monster's health when one of the potions is given to the monster.

• If potion 1 is given, the monster's health becomes 100 + 50 = 150.
• If potion 2 is given, the monster's health becomes 100 + 200 = 300.
• If potion 3 is given, the monster's health becomes 100 + 999 = 1099.

The potions that increase the monster's health to at least X = 200 are potions 2 and 3. The answer is the least effective of them, which is potion 2.

Sample Input 2

2 10 21
10 999

Sample Output 2

2

Sample Input 3

10 500 999
38 420 490 585 613 614 760 926 945 999

Sample Output 3

4

Problem Statement

Naohiro had N+1 consecutive integers, one of each, but he lost one of them.

The remaining N integers are given in arbitrary order as A_1,\ldots,A_N. Find the lost integer.

The given input guarantees that the lost integer is uniquely determined.

Constraints

• 2 \leq N \leq 100
• 1 \leq A_i \leq 1000
• All input values are integers.
• The lost integer is uniquely determined.

Sample Input 1

3
2 3 5

Sample Output 1

4

Naohiro originally had four integers, 2,3,4,5, then lost 4, and now has 2,3,5.

Print the lost integer, 4.

Sample Input 2

8
3 1 4 5 9 2 6 8

Sample Output 2

7

Sample Input 3

16
152 153 154 147 148 149 158 159 160 155 156 157 144 145 146 150

Sample Output 3

151

Problem Statement

A region has N towns numbered 1 to N, and M roads numbered 1 to M.

The i-th road connects town A_i and town B_i bidirectionally with length C_i.

Find the maximum possible total length of the roads you traverse when starting from a town of your choice and getting to another town without passing through the same town more than once.

Constraints

• 2 \leq N \leq 10
• 1 \leq M \leq \frac{N(N-1)}{2}
• 1 \leq A_i < B_i \leq N
• The pairs (A_i,B_i) are distinct.
• 1\leq C_i \leq 10^8
• All input values are integers.

Sample Input 1

4 4
1 2 1
2 3 10
1 3 100
1 4 1000

Sample Output 1

1110

If you travel as 4\to 1\to 3\to 2, the total length of the roads you traverse is 1110.

Sample Input 2

10 1
5 9 1

Sample Output 2

1

There may be a town that is not connected to a road.

Sample Input 3

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

Sample Output 3

20

Problem Statement

Takahashi and Aoki are competing in an election.
There are N electoral districts. The i-th district has X_i + Y_i voters, of which X_i are for Takahashi and Y_i are for Aoki. (X_i + Y_i is always an odd number.)
In each district, the majority party wins all Z_i seats in that district. Then, whoever wins the majority of seats in the N districts as a whole wins the election. (\displaystyle \sum_{i=1}^N Z_i is odd.)
At least how many voters must switch from Aoki to Takahashi for Takahashi to win the election?

Constraints

• 1 \leq N \leq 100
• 0 \leq X_i, Y_i \leq 10^9
• X_i + Y_i is odd.
• 1 \leq Z_i
• \displaystyle \sum_{i=1}^N Z_i \leq 10^5
• \displaystyle \sum_{i=1}^N Z_i is odd.

Sample Input 1

1
3 8 1

Sample Output 1

3

Since there is only one district, whoever wins the seat in that district wins the election.
If three voters for Aoki in the district switch to Takahashi, there will be six voters for Takahashi and five for Aoki, and Takahashi will win the seat.

Sample Input 2

2
3 6 2
1 8 5

Sample Output 2

4

Since there are more seats in the second district than in the first district, Takahashi must win a majority in the second district to win the election.
If four voters for Aoki in the second district switch sides, Takahashi will win five seats. In this case, Aoki will win two seats, so Takahashi will win the election.

Sample Input 3

3
3 4 2
1 2 3
7 2 6

Sample Output 3

0

If Takahashi will win the election even if zero voters switch sides, the answer is 0.

Sample Input 4

10
1878 2089 16
1982 1769 13
2148 1601 14
2189 2362 15
2268 2279 16
2394 2841 18
2926 2971 20
3091 2146 20
3878 4685 38
4504 4617 29

Sample Output 4

86

Problem Statement

There is a field divided into a grid of H rows and W columns.
The square at the i-th row from the north (top) and the j-th column from the west (left) is represented by the character A_{i, j}. Each character represents the following.

• . : An empty square. Passable.
• # : An obstacle. Impassable.
• >, v, <, ^ : Squares with a person facing east, south, west, and north, respectively. Impassable. The person's line of sight is one square wide and extends straight in the direction the person is facing, and is blocked by an obstacle or another person. (See also the description at Sample Input/Output 1.)
• S : The starting point. Passable. There is exactly one starting point. It is guaranteed not to be in a person's line of sight.
• G : The goal. Passable. There is exactly one goal. It is guaranteed not to be in a person's line of sight.

Naohiro is at the starting point and can move one square to the east, west, south, and north as many times as he wants. However, he cannot enter an impassable square or leave the field.
Determine if he can reach the goal without entering a person's line of sight, and if so, find the minimum number of moves required to do so.

Constraints

• 2 \leq H, W \leq 2000
• A_{i,j} is ., #, >, v, <, ^, S, or G.
• Each of S and G occurs exactly once among A_{i, j}.
• Neither the starting point nor the goal is in a person's line of sight.

Sample Input 1

5 7
....Sv.
.>.....
.......
>..<.#<
^G....>

Sample Output 1

15

For Sample Input 1, the following figure shows the empty squares that are in the lines of sight of one or more people as !.

Let us describe some of the squares. (Let (i, j) denote the square in the i-th row from the north and the j-th column from the west.)

• (2, 4) is a square in the line of sight of the east-facing person at (2, 2).
• (2, 6) is a square in the lines of sight of two people, one facing east at (2, 2) and the other facing south at (1, 6).
• The square (4, 5) is not in anyone's line of sight. The line of sight of the west-facing person at (4, 7) is blocked by the obstacle at (4, 6), and the line of sight of the east-facing person at (4, 1) is blocked by the person at (4, 4).

Naohiro must reach the goal without passing through impassable squares or squares in a person's line of sight.

Sample Input 2

4 3
S..
.<.
.>.
..G

Sample Output 2

-1

Print -1 if he cannot reach the goal.

Problem Statement

You are given integers N,A_1,A_2,A_3. Find the number, modulo 998244353, of triples of positive integers (X_1,X_2,X_3) that satisfy all of the following three conditions.

• 1\leq X_i \leq N for every i.
• X_i is a multiple of A_i for every i.
• (X_1 \oplus X_2) \oplus X_3 = 0, where \oplus denotes bitwise xor.

Constraints

• 1 \leq N \leq 10^{18}
• 1 \leq A_i \leq 10
• All input values are integers.

Sample Input 1

13 2 3 5

Sample Output 1

4

Four triples (X_1,X_2,X_3) satisfy the conditions: (6,3,5),(6,12,10),(12,6,10),(12,9,5).

Sample Input 2

1000000000000000000 1 1 1

Sample Output 2

426724011

Sample Input 3

31415926535897932 3 8 4

Sample Output 3

759934997

Problem Statement

There is a grid with N rows and M columns. The square at the i-th row from the top and the j-th column from the left contains the integer A_{i,j}.
Here, the squares contain M occurrences of each of 1,\ldots,N, for a total of NM integers.

You perform the following operations to swap the numbers written on the squares.

• For i=1,\ldots,N in this order, do the following.
  • Freely rearrange the numbers written in the i-th row. That is, freely choose a permutation P=(P_{1},\ldots,P_{M}) of 1,\ldots,M, and replace A_{i,1},\ldots,A_{i,M} with A_{i,P_{1}},\ldots,A_{i,P_{M}} simultaneously.

Your goal is to perform the operations so that each column contains each of 1,\ldots,N once. Determine if this is possible, and if so, print such a resulting grid.

Constraints

• 1 \leq N,M \leq 100
• 1 \leq A_{i,j} \leq N
• All input values are integers.
• The NM numbers A_{1,1},\ldots,A_{N,M} contain exactly M occurrences of each of 1,\ldots,N.

Sample Input 1

3 2
1 1
2 3
2 3

Sample Output 1

Yes
1 1
3 2
2 3

Also, the following output is accepted.

Yes
1 1
2 3
3 2

Sample Input 2

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

Sample Output 2

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

Problem Statement

We have a directed graph with N vertices numbered 1 to N. The graph has no multi-edges but can have self-loops. Also, every edge in the graph satisfies the following condition.

• If the edge goes from vertex s to vertex t, then s and t satisfy at least one of 0 \leq t - s\leq 2 and t = 1.

The presence or absence of an edge in the graph is represented by sequences A, B, C, D, each of length N. Each element of A, B, C, D has the following meaning. (Let A_n denote the n-th element of A; the same applies to B_n, C_n, D_n.)

• A_n is 1 if there is an edge from vertex n to vertex n, and 0 otherwise.
• B_n is 1 if there is an edge from vertex n to vertex n+1, and 0 otherwise. (Here, B_N = 0.)
• C_n is 1 if there is an edge from vertex n to vertex n+2, and 0 otherwise. (Here, C_{N-1} = C_N = 0.)
• D_n is 1 if there is an edge from vertex n to vertex 1, and 0 otherwise. (Here, D_1 = A_1.)

In the given graph, find the number, modulo 998244353, of walks with K edges starting at vertex 1 and ending at vertex N.

Here, a walk with K edges starting at vertex 1 and ending at vertex N is a sequence of vertices v_0 = 1, v_1, \dots, v_K = N such that for each i (0 \leq i \lt K) there is an edge from vertex v_i to vertex v_{i + 1}. Two walks are distinguished when they differ as sequences.

Constraints

• 2 \leq N \leq 5 \times 10^4
• 1 \leq K \leq 5 \times 10^5
• A_i, B_i, C_i, D_i \in \lbrace 0, 1 \rbrace
• A_1 = D_1
• B_N = C_{N-1} = C_N = 0

Sample Input 1

3 3
1 0 1
1 1 0
1 0 0
1 0 1

Sample Output 1

6

The following figure shows the graph.

The following six walks satisfy the conditions.

• 1, 1, 1, 3
• 1, 1, 2, 3
• 1, 1, 3, 3
• 1, 2, 3, 3
• 1, 3, 1, 3
• 1, 3, 3, 3

Sample Input 2

4 6
1 1 1 1
1 1 1 0
1 1 0 0
1 0 0 0

Sample Output 2

50

Sample Input 3

10 500000
0 1 0 1 0 0 0 0 1 1
1 1 1 0 1 1 1 0 1 0
0 0 1 1 0 0 1 1 0 0
0 1 1 1 1 1 0 1 1 0

Sample Output 3

866263864