Problem Statement

2N players are running a competitive table tennis training on N tables numbered from 1 to N.

The training consists of rounds. In each round, the players form N pairs, one pair per table. In each pair, competitors play a match against each other. As a result, one of them wins and the other one loses.

The winner of the match on table X plays on table X-1 in the next round, except for the winner of the match on table 1 who stays at table 1.

Similarly, the loser of the match on table X plays on table X+1 in the next round, except for the loser of the match on table N who stays at table N.

Two friends are playing their first round matches on distinct tables A and B. Let's assume that the friends are strong enough to win or lose any match at will. What is the smallest number of rounds after which the friends can get to play a match against each other?

Constraints

• 2 \leq N \leq 10^{18}
• 1 \leq A < B \leq N
• All input values are integers.

Sample Input 1

5 2 4

Sample Output 1

1

If the first friend loses their match and the second friend wins their match, they will both move to table 3 and play each other in the next round.

Sample Input 2

5 2 3

Sample Output 2

2

If both friends win two matches in a row, they will both move to table 1.

Problem Statement

N problems are proposed for an upcoming contest. Problem i has an initial integer score of A_i points.

M judges are about to vote for problems they like. Each judge will choose exactly V problems, independently from the other judges, and increase the score of each chosen problem by 1.

After all M judges cast their vote, the problems will be sorted in non-increasing order of score, and the first P problems will be chosen for the problemset. Problems with the same score can be ordered arbitrarily, this order is decided by the chief judge.

How many problems out of the given N have a chance to be chosen for the problemset?

Constraints

• 2 \le N \le 10^5
• 1 \le M \le 10^9
• 1 \le V \le N - 1
• 1 \le P \le N - 1
• 0 \le A_i \le 10^9

Sample Input 1

6 1 2 2
2 1 1 3 0 2

Sample Output 1

5

If the only judge votes for problems 2 and 5, the scores will be 2 2 1 3 1 2. The problemset will consist of problem 4 and one of problems 1, 2, or 6.

If the only judge votes for problems 3 and 4, the scores will be 2 1 2 4 0 2. The problemset will consist of problem 4 and one of problems 1, 3, or 6.

Thus, problems 1, 2, 3, 4, and 6 have a chance to be chosen for the problemset. On the contrary, there is no way for problem 5 to be chosen.

Sample Input 2

6 1 5 2
2 1 1 3 0 2

Sample Output 2

3

Only problems 1, 4, and 6 have a chance to be chosen.

Sample Input 3

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

Sample Output 3

8

Problem Statement

Let us consider a grid of squares with N rows and N columns. You want to put some domino pieces on this grid. Each domino piece covers two squares that have a common side. Each square can be covered by at most one piece.

For each row of the grid, let's define its quality as the number of domino pieces that cover at least one square in this row. We define the quality of each column similarly.

Find a way to put at least one domino piece on the grid so that the quality of every row is equal to the quality of every column, or determine that such a placement doesn't exist.

Constraints

• 2 \le N \le 1000

Sample Input 1

6

Sample Output 1

aabb..
b..zz.
ba....
.a..aa
..a..b
..a..b

The quality of every row and every column is 2.

Sample Input 2

2

Sample Output 2

-1

Problem Statement

N problems have been chosen by the judges, now it's time to assign scores to them!

Problem i must get an integer score A_i between 1 and N, inclusive. The problems have already been sorted by difficulty: A_1 \le A_2 \le \ldots \le A_N must hold. Different problems can have the same score, though.

Being an ICPC fan, you want contestants who solve more problems to be ranked higher. That's why, for any k (1 \le k \le N-1), you want the sum of scores of any k problems to be strictly less than the sum of scores of any k+1 problems.

How many ways to assign scores do you have? Find this number modulo the given prime M.

Constraints

• 2 \leq N \leq 5000
• 9 \times 10^8 < M < 10^9
• M is a prime.
• All input values are integers.

Sample Input 1

2 998244353

Sample Output 1

3

The possible assignments are (1, 1), (1, 2), (2, 2).

Sample Input 2

3 998244353

Sample Output 2

7

The possible assignments are (1, 1, 1), (1, 2, 2), (1, 3, 3), (2, 2, 2), (2, 2, 3), (2, 3, 3), (3, 3, 3).

Sample Input 3

6 966666661

Sample Output 3

66

Sample Input 4

96 925309799

Sample Output 4

83779

Problem Statement

A balancing network is an abstract device built up of N wires, thought of as running from left to right, and M balancers that connect pairs of wires. The wires are numbered from 1 to N from top to bottom, and the balancers are numbered from 1 to M from left to right. Balancer i connects wires x_i and y_i (x_i < y_i).

Each balancer must be in one of two states: up or down.

Consider a token that starts moving to the right along some wire at a point to the left of all balancers. During the process, the token passes through each balancer exactly once. Whenever the token encounters balancer i, the following happens:

• If the token is moving along wire x_i and balancer i is in the down state, the token moves down to wire y_i and continues moving to the right.
• If the token is moving along wire y_i and balancer i is in the up state, the token moves up to wire x_i and continues moving to the right.
• Otherwise, the token doesn't change the wire it's moving along.

Let a state of the balancing network be a string of length M, describing the states of all balancers. The i-th character is ^ if balancer i is in the up state, and v if balancer i is in the down state.

A state of the balancing network is called uniforming if a wire w exists such that, regardless of the starting wire, the token will always end up at wire w and run to infinity along it. Any other state is called non-uniforming.

You are given an integer T (1 \le T \le 2). Answer the following question:

• If T = 1, find any uniforming state of the network or determine that it doesn't exist.
• If T = 2, find any non-uniforming state of the network or determine that it doesn't exist.

Note that if you answer just one kind of questions correctly, you can get partial score.

Constraints

• 2 \leq N \leq 50000
• 1 \leq M \leq 100000
• 1 \leq T \leq 2
• 1 \leq x_i < y_i \leq N
• All input values are integers.

Partial Score

• 800 points will be awarded for passing the testset satisfying T = 1.
• 800 points will be awarded for passing the testset satisfying T = 2.

Sample Input 1

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

Sample Output 1

^^^^^

This state is uniforming: regardless of the starting wire, the token ends up at wire 1.

Sample Input 2

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

Sample Output 2

v^^^^

This state is non-uniforming: depending on the starting wire, the token might end up at wire 1 or wire 2.

Sample Input 3

3 1 1
1 2

Sample Output 3

-1

A uniforming state doesn't exist.

Sample Input 4

2 1 2
1 2

Sample Output 4

-1

A non-uniforming state doesn't exist.

Problem Statement

Let us consider a grid of squares with N rows and N columns. Arbok has cut out some part of the grid so that, for each i = 1, 2, \ldots, N, the bottommost h_i squares are remaining in the i-th column from the left. Now, he wants to place rooks into some of the remaining squares.

A rook is a chess piece that occupies one square and can move horizontally or vertically, through any number of unoccupied squares. A rook can not move through squares that have been cut out by Arbok.

Let's say that a square is covered if it either contains a rook, or a rook can be moved to this square in one move.

Find the number of ways to place rooks into some of the remaining squares so that every remaining square is covered, modulo 998244353.

Constraints

• 1 \leq N \leq 400
• 1 \leq h_i \leq N
• All input values are integers.

Sample Input 1

2
2 2

Sample Output 1

11

Any placement with at least two rooks is fine. There are 11 such placements.

Sample Input 2

3
2 1 2

Sample Output 2

17

The following 17 rook placements satisfy the conditions (R denotes a rook, * denotes an empty square):

R *     * R     * *     R R     R R     R R     
**R     R**     R*R     R**     *R*     **R     


R *     R *     * R     * R     * *     R R     
R*R     *RR     RR*     R*R     RRR     RR*     


R R     R R     R *     * R     R R     
R*R     *RR     RRR     RRR     RRR     

Sample Input 3

4
1 2 4 1

Sample Output 3

201

Sample Input 4

10
4 7 4 8 4 6 8 2 3 6

Sample Output 4

263244071