Problem Statement

Takahashi has N pairs of socks, and the i-th pair consists of two socks of color i. One day, after organizing his chest of drawers, Takahashi realized that he had lost one sock each of colors A_1, A_2, \dots, A_K, so he decided to use the remaining 2N-K socks to make \lfloor\frac{2N-K}{2}\rfloor new pairs of socks, each pair consisting of two socks. The weirdness of a pair of a sock of color i and a sock of color j is defined as |i-j|, and Takahashi wants to minimize the total weirdness.

Find the minimum possible total weirdness when making \lfloor\frac{2N-K}{2}\rfloor pairs from the remaining socks. Note that if 2N-K is odd, there will be one sock that is not included in any pair.

Constraints

• 1\leq K\leq N \leq 2\times 10^5
• 1\leq A_1 < A_2 < \dots < A_K \leq N
• All input values are integers.

Sample Input 1

4 2
1 3

Sample Output 1

2

Below, let (i,j) denote a pair of a sock of color i and a sock of color j.

There are 1, 2, 1, 2 socks of colors 1, 2, 3, 4, respectively. Creating the pairs (1,2),(2,3),(4,4) results in a total weirdness of |1-2|+|2-3|+|4-4|=2, which is the minimum.

Sample Input 2

5 1
2

Sample Output 2

0

The optimal solution is to make the pairs (1,1),(3,3),(4,4),(5,5) and leave one sock of color 2 as a surplus (not included in any pair).

Sample Input 3

8 5
1 2 4 7 8

Sample Output 3

2

Problem Statement

Snuke the doctor prescribed N kinds of medicine for Takahashi. For the next a_i days (including the day of the prescription), he has to take b_i pills of the i-th medicine. He does not have to take any other medicine.

Let the day of the prescription be day 1. On or after day 1, when is the first day on which he has to take K pills or less?

Constraints

• 1 \leq N \leq 3 \times 10^5
• 0 \leq K \leq 10^9
• 1 \leq a_i,b_i \leq 10^9
• All input values are integers.

Sample Input 1

4 8
6 3
2 5
1 9
4 2

Sample Output 1

3

On day 1, he has to take 3,5,9, and 2 pills of the 1-st, 2-nd, 3-rd, and 4-th medicine, respectively. In total, he has to take 19 pills on this day, which is not K(=8) pills or less.
On day 2, he has to take 3,5, and 2 pills of the 1-st, 2-nd, and 4-th medicine, respectively. In total, he has to take 10 pills on this day, which is not K(=8) pills or less.
On day 3, he has to take 3 and 2 pills of the 1-st and 4-th medicine, respectively. In total, he has to take 5 pills on this day, which is K(=8) pills or less for the first time.

Thus, the answer is 3.

Sample Input 2

4 100
6 3
2 5
1 9
4 2

Sample Output 2

1

Sample Input 3

15 158260522
877914575 2436426
24979445 61648772
623690081 33933447
476190629 62703497
211047202 71407775
628894325 31963982
822804784 50968417
430302156 82631932
161735902 80895728
923078537 7723857
189330739 10286918
802329211 4539679
303238506 17063340
492686568 73361868
125660016 50287940

Sample Output 3

492686569

Problem Statement

Takahashi has N balls. Each ball has an integer not less than 2 written on it. He will insert them in a cylinder one by one. The integer written on the i-th ball is a_i.

The balls are made of special material. When k balls with k (k \geq 2) written on them line up in a row, all these k balls will disappear.

For each i (1 \leq i \leq N), find the number of balls after inserting the i-th ball.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 2 \leq a_i \leq 2 \times 10^5 \, (1 \leq i \leq N)
• All values in input are integers.

Sample Input 1

5
3 2 3 2 2

Sample Output 1

1
2
3
4
3

The content of the cylinder changes as follows.

• After inserting the 1-st ball, the cylinder contains the ball with 3.
• After inserting the 2-nd ball, the cylinder contains 3, 2 from bottom to top.
• After inserting the 3-rd ball, the cylinder contains 3, 2, 3 from bottom to top.
• After inserting the 4-th ball, the cylinder contains 3, 2, 3, 2 from bottom to top.
• After inserting the 5-th ball, the cylinder momentarily has 3, 2, 3, 2, 2 from bottom to top. The two consecutive balls with 2 disappear, and the cylinder eventually contains 3, 2, 3 from bottom to top.

Sample Input 2

10
2 3 2 3 3 3 2 3 3 2

Sample Output 2

1
2
3
4
5
3
2
3
1
0

Problem Statement

You are given a matrix A with H rows and W columns. The value of each of its elements is 0 or 1. For an integer pair (i, j) such that 1 \leq i \leq H and 1 \leq j \leq W, we denote by A_{i,j} the element at the i-th row and j-th column.

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

• Choose an integer i such that 1 \leq i \leq H. For every integer j such that 1 \leq j \leq W, replace the value of A_{i,j} with 1-A_{i,j}.

A_{i,j} is said to be isolated if and only if there is no adjacent element with the same value; in other words, if and only if none of the four integer pairs (x,y) = (i-1,j),(i+1,j),(i,j-1),(i,j+1) satisfies 1 \leq x \leq H, 1 \leq y \leq W, and A_{i,j} = A_{x,y}.

Determine if you can make the matrix A in such a state that no element is isolated by repeating the operation. If it is possible, find the minimum number of operations required to do so.

Constraints

• 2 \leq H,W \leq 1000
• A_{i,j} = 0 or A_{i,j} = 1
• All values in the input are integers.

Sample Input 1

3 3
1 1 0
1 0 1
1 0 0

Sample Output 1

1

An operation with i = 1 makes A = ((0,0,1),(1,0,1),(1,0,0)), where there is no longer an isolated element.

Sample Input 2

4 4
1 0 0 0
0 1 1 1
0 0 1 0
1 1 0 1

Sample Output 2

2

Sample Input 3

2 3
0 1 0
0 1 1

Sample Output 3

-1

Problem Statement

N players, player 1, player 2, ..., player N, participate in a game tournament. Just before the tournament starts, each player forms a one-person team, so there are N teams in total.

The tournament has a total of N-1 matches. In each match, two different teams are chosen. One team goes first, and the other goes second. Each match will result in exactly one team winning. Specifically, for each i = 1, 2, \ldots, N-1, the i-th match proceeds as follows.

• The team with player p_i goes first, and the team with player q_i goes second.
• Let a and b be the numbers of players in the first and second teams, respectively. The first team wins with probability \frac{a}{a+b}, and the second team wins with probability \frac{b}{a+b}.
• Then, the two teams are combined into a single team.

The result of each match is independent of those of the others.

For each of the N players, print the expected number of times the team with that player wins throughout the tournament, modulo 998244353.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq p_i, q_i \leq N
• Just before the i-th match, player p_i and player q_i belong to different teams.
• All input values are integers.

Sample Input 1

5
1 2
4 3
5 3
1 4

Sample Output 1

698771048 698771048 964969543 964969543 133099248

We call a team formed by player x_1, player x_2, \ldots, player x_k as team \lbrace x_1, x_2, \ldots, x_k \rbrace.

• The first match is played by team \lbrace 1 \rbrace, with player 1, and team \lbrace 2 \rbrace, with player 2. Team \lbrace 1 \rbrace wins with probability \frac{1}{2}, and team \lbrace 2 \rbrace wins with probability \frac{1}{2}. Then, the two teams are combined into a single team \lbrace 1, 2 \rbrace.
• The second match is played by team \lbrace 4 \rbrace, with player 4, and team \lbrace 3 \rbrace, with player 3. Team \lbrace 4 \rbrace wins with probability \frac{1}{2}, and team \lbrace 3 \rbrace wins with probability \frac{1}{2}. Then, the two teams are combined into a single team \lbrace 3, 4 \rbrace.
• The third match is played by team \lbrace 5 \rbrace, with player 5, and team \lbrace 3, 4 \rbrace, with player 3. Team \lbrace 5 \rbrace wins with probability \frac{1}{3}, and team \lbrace 3, 4 \rbrace wins with probability \frac{2}{3}. Then, the two teams are combined into a single team \lbrace 3, 4, 5 \rbrace.
• The fourth match is played by team \lbrace 1, 2 \rbrace, with player 1, and team \lbrace 3, 4, 5 \rbrace, with player 4. Team \lbrace 1, 2 \rbrace wins with probability \frac{2}{5}, and team \lbrace 3, 4, 5 \rbrace wins with probability \frac{3}{5}. Then, the two teams are combined into a single team \lbrace 1, 2, 3, 4, 5 \rbrace.

The expected numbers of times the teams with players 1, 2, 3, 4, 5 win throughout the tournament, E_1, E_2, E_3, E_4, E_5, are \frac{9}{10}, \frac{9}{10}, \frac{53}{30}, \frac{53}{30}, \frac{14}{15}, respectively.

Sample Input 2

15
9 2
8 10
13 6
12 11
7 10
4 10
14 2
5 4
1 15
15 2
6 9
8 11
6 3
2 8

Sample Output 2

43970290 310168785 806914186 501498951 950708909 272140427 335124893 168750835 310168785 168750835 280459129 280459129 272140427 476542843 43970290