Problem Statement

How many ways are there to choose two distinct positive integers totaling N, disregarding the order?

Constraints

• 1 \leq N \leq 10^6
• N is an integer.

Sample Input 1

4

Sample Output 1

1

There is only one way to choose two distinct integers totaling 4: to choose 1 and 3. (Choosing 3 and 1 is not considered different from this.)

Sample Input 2

999999

Sample Output 2

499999

Problem Statement

Given is an integer sequence D_1,...,D_N of N elements. Find the number, modulo 998244353, of trees with N vertices numbered 1 to N that satisfy the following condition:

• For every integer i from 1 to N, the distance between Vertex 1 and Vertex i is D_i.

Notes

• A tree of N vertices is a connected undirected graph with N vertices and N-1 edges, and the distance between two vertices are the number of edges in the shortest path between them.
• Two trees are considered different if and only if there are two vertices x and y such that there is an edge between x and y in one of those trees and not in the other.

Constraints

• 1 \leq N \leq 10^5
• 0 \leq D_i \leq N-1

Sample Input 1

4
0 1 1 2

Sample Output 1

2

For example, a tree with edges (1,2), (1,3), and (2,4) satisfies the condition.

Sample Input 2

4
1 1 1 1

Sample Output 2

0

Sample Input 3

7
0 3 2 1 2 2 1

Sample Output 3

24

Problem Statement

Given are two integer sequences of N elements each: A_1,...,A_N and B_1,...,B_N. Determine if it is possible to do the following operation at most N-2 times (possibly zero) so that, for every integer i from 1 to N, A_i \leq B_i holds:

• Choose two distinct integers x and y between 1 and N (inclusive), and swap the values of A_x and A_y.

Constraints

• 2 \leq N \leq 10^5
• 1 \leq A_i,B_i \leq 10^9

Sample Input 1

3
1 3 2
1 2 3

Sample Output 1

Yes

We should swap the values of A_2 and A_3.

Sample Input 2

3
1 2 3
2 2 2

Sample Output 2

No

Sample Input 3

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

Sample Output 3

Yes

Problem Statement

We have N points numbered 1 to N arranged in a line in this order.

Takahashi decides to make an undirected graph, using these points as the vertices. In the beginning, the graph has no edge. Takahashi will do M operations to add edges in this graph. The i-th operation is as follows:

• The operation uses integers L_i and R_i between 1 and N (inclusive), and a positive integer C_i. For every pair of integers (s, t) such that L_i \leq s < t \leq R_i, add an edge of length C_i between Vertex s and Vertex t.

The integers L_1, ..., L_M, R_1, ..., R_M, C_1, ..., C_M are all given as input.

Takahashi wants to solve the shortest path problem in the final graph obtained. Find the length of the shortest path from Vertex 1 to Vertex N in the final graph.

Constraints

• 2 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 1 \leq L_i < R_i \leq N
• 1 \leq C_i \leq 10^9

Sample Input 1

4 3
1 3 2
2 4 3
1 4 6

Sample Output 1

5

We have an edge of length 2 between Vertex 1 and Vertex 2, and an edge of length 3 between Vertex 2 and Vertex 4, so there is a path of length 5 between Vertex 1 and Vertex 4.

Sample Input 2

4 2
1 2 1
3 4 2

Sample Output 2

-1

Sample Input 3

10 7
1 5 18
3 4 8
1 3 5
4 7 10
5 9 8
6 10 5
8 10 3

Sample Output 3

28

Problem Statement

Given are positive integers N and K.

Determine if the 3N integers K, K+1, ..., K+3N-1 can be partitioned into N triples (a_1,b_1,c_1), ..., (a_N,b_N,c_N) so that the condition below is satisfied. Any of the integers K, K+1, ..., K+3N-1 must appear in exactly one of those triples.

• For every integer i from 1 to N, a_i + b_i \leq c_i holds.

If the answer is yes, construct one such partition.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq K \leq 10^9

Sample Input 1

1 1

Sample Output 1

1 2 3

Sample Input 2

3 3

Sample Output 2

-1

Problem Statement

In a two-dimensional plane, there is a square frame whose vertices are at coordinates (0,0), (N,0), (0,N), and (N,N). The frame is made of mirror glass. A ray of light striking an edge of the frame (but not a vertex) will be reflected so that the angle of incidence is equal to the angle of reflection. A ray of light striking a vertex of the frame will be reflected in the direction opposite to the direction it is coming from.

We will define the path for a grid point (a point with integer coordinates) (i,j) (0<i,j<N) strictly within the frame, as follows:

• The path for (i,j) is the union of the trajectories of four rays of light emitted from (i,j) to (i-1,j-1), (i-1,j+1), (i+1,j-1), and (i+1,j+1).

Figure: an example of a path for a grid point

There is a light bulb at each grid point strictly within the frame. We will assign a state - ON or OFF - to each bulb. The state of the whole set of bulbs are called beautiful if it is possible to turn OFF all the bulbs by repeating the following operation:

• Choose a grid point strictly within the frame, and switch the states of all the bulbs on its path.

Takahashi has set the states of some of the bulbs, but not for the remaining bulbs. Find the number of ways to set the states of the remaining bulbs so that the state of the whole set of bulbs is beautiful, modulo 998244353. The state of the bulb at the grid point (i,j) is set to be ON if A_{i,j}=o, OFF if A_{i,j}=x, and unset if A_{i,j}=?.

Constraints

• 2 \leq N \leq 1500
• A_{ij} is o, x, or ?.

Sample Input 1

4
o?o
???
?x?

Sample Output 1

1

The state of the whole set of bulbs will be beautiful if we set the state of each bulb as follows:

oxo
xox
oxo

We can turn OFF all the bulbs by, for example, choosing the point (1, 1) and switching the states of the bulbs at (1,1), (1,3), (2,2), (3,1), and (3,3).

Sample Input 2

5
o?o?
????
o?x?
????

Sample Output 2

0

Sample Input 3

6
?o???
????o
??x??
o????
???o?

Sample Output 3

32

Sample Input 4

9
????o??x
?????x??
??o?o???
?o?x????
???????x
x?o?o???
????????
x?????x?

Sample Output 4

4