Problem Statement

There was an exam consisting of three problems worth 1, 2, and 4 points.

Takahashi, Aoki, and Snuke took this exam. Takahashi scored A points, and Aoki scored B points.

Snuke solved all of the problems solved by at least one of Takahashi and Aoki, and failed to solve any of the problems solved by neither of them.

Find Snuke's score.

It can be proved that Snuke's score is uniquely determined under the Constraints of this problem.

Constraints

• 0\leq A,B \leq 7
• A and B are integers.

Sample Input 1

1 2

Sample Output 1

3

Since Takahashi scored 1 point, we see that he solved only the 1-point problem and failed to solve the other two.
Similarly, since Aoki scored 2 points, we see that he solved only the 2-point problem and failed to solve the other two.

Therefore, Snuke must have solved the 1- and 2-point problems, but not the 4-point one, which Takahashi and Aoki both failed to solve, for a score of 3 points. Thus, 3 should be printed.

Sample Input 2

5 3

Sample Output 2

7

Since Takahashi scored 5 points, we see that he solved the 1- and 4-point problems but not the 2-point one.
Similarly, since Aoki scored 3 points, we see that he solved the 1- and 2-point problems but not the 4-point one.

Therefore, each of the three problems is solved by at least one of Takahashi and Aoki, so we see that Snuke solved all of the problems, for a score of 7 points. Thus, 7 should be printed.

Sample Input 3

0 0

Sample Output 3

0

Both Takahashi and Aoki solved none of the problems. Therefore, so did Snuke. Thus, 0 should be printed.

Problem Statement

Takahashi is at the origin of a number line. He wants to reach a goal at coordinate X.

There is a wall at coordinate Y, which Takahashi cannot go beyond at first.
However, after picking up a hammer at coordinate Z, he can destroy that wall and pass through.

Determine whether Takahashi can reach the goal. If he can, find the minimum total distance he needs to travel to do so.

Constraints

• -1000 \leq X,Y,Z \leq 1000
• X, Y, and Z are distinct, and none of them is 0.
• All values in the input are integers.

Sample Input 1

10 -10 1

Sample Output 1

10

Takahashi can go straight to the goal.

Sample Input 2

20 10 -10

Sample Output 2

40

The goal is beyond the wall. He can get there by first picking up the hammer and then destroying the wall.

Sample Input 3

100 1 1000

Sample Output 3

-1

Problem Statement

There is a tree T with N vertices. The i-th edge (1\leq i\leq N-1) connects vertex U_i and vertex V_i.

You are given two different vertices X and Y in T. List all vertices along the simple path from vertex X to vertex Y in order, including endpoints.

It can be proved that, for any two different vertices a and b in a tree, there is a unique simple path from a to b.

Constraints

• 1\leq N\leq 2\times 10^5
• 1\leq X,Y\leq N
• X\neq Y
• 1\leq U_i,V_i\leq N
• All values in the input are integers.
• The given graph is a tree.

Sample Input 1

5 2 5
1 2
1 3
3 4
3 5

Sample Output 1

2 1 3 5

The tree T is shown below. The simple path from vertex 2 to vertex 5 is 2 \to 1 \to 3 \to 5.
Thus, 2,1,3,5 should be printed in this order, with spaces in between.

Sample Input 2

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

Sample Output 2

1 2

The tree T is shown below.

Problem Statement

Takahashi and Aoki will play a game of taking stones using a sequence (A_1, \ldots, A_K).

There is a pile that initially contains N stones. The two players will alternately perform the following operation, with Takahashi going first.

• Choose an A_i that is at most the current number of stones in the pile. Remove A_i stones from the pile.

The game ends when the pile has no stones.

If both players attempt to maximize the total number of stones they remove before the end of the game, how many stones will Takahashi remove?

Constraints

• 1 \leq N \leq 10^4
• 1 \leq K \leq 100
• 1 = A_1 < A_2 < \ldots < A_K \leq N
• All values in the input are integers.

Sample Input 1

10 2
1 4

Sample Output 1

5

Below is one possible progression of the game.

• Takahashi removes 4 stones from the pile.
• Aoki removes 4 stones from the pile.
• Takahashi removes 1 stone from the pile.
• Aoki removes 1 stone from the pile.

In this case, Takahashi removes 5 stones. There is no way for him to remove 6 or more stones, so this is the maximum.

Below is another possible progression of the game where Takahashi removes 5 stones.

• Takahashi removes 1 stone from the pile.
• Aoki removes 4 stones from the pile.
• Takahashi removes 4 stones from the pile.
• Aoki removes 1 stone from the pile.

Sample Input 2

11 4
1 2 3 6

Sample Output 2

8

Below is one possible progression of the game.

• Takahashi removes 6 stones.
• Aoki removes 3 stones.
• Takahashi removes 2 stones.

In this case, Takahashi removes 8 stones. There is no way for him to remove 9 or more stones, so this is the maximum.

Sample Input 3

10000 10
1 2 4 8 16 32 64 128 256 512

Sample Output 3

5136

Problem Statement

There are N baskets numbered 1, 2, \ldots, N arranged in a circle.
For each 1\leq i \leq N-1, basket i+1 is to the immediate right of basket i, and basket 1 is to the immediate right of basket N.

Basket i now contains A_i apples.

Takahashi starts in front of basket 1 and repeats the following action.

• If the basket he is facing contains an apple, take one and eat it. Then, regardless of whether he has eaten an apple now, go on to the next basket to the immediate right.

Find the number of apples remaining in each basket when Takahashi has eaten exactly K apples in total.

Constraints

• 1 \leq N \leq 10^5
• 0 \leq A_i \leq 10^{12}
• 1 \leq K \leq 10^{12}
• There are at least K apples in total. That is, \sum_{i=1}^{N}A_i\geq K.
• All values in the input are integers.

Sample Input 1

3 3
1 3 0

Sample Output 1

0 1 0 

Takahashi will do the following.

• Basket 1, which he is facing, contains an apple, so he takes one and eats it. Then, he goes on to basket 2. Now, the baskets have 0,3,0 apples.
• Basket 2, which he is facing, contains an apple, so he takes one and eats it. Then, he goes on to basket 3. Now, the baskets have 0,2,0 apples.
• Basket 3, which he is facing, contains no apple. Then, he goes on to basket 1. Now, the baskets have 0,2,0 apples.
• Basket 1, which he is facing, contains no apple. Then, he goes on to basket 2. Now, the baskets have 0,2,0 apples.
• Basket 2, which he is facing, contains an apple, so he takes one and eats it. Then, he goes on to basket 3. Now, the baskets have 0,1,0 apple(s).

Sample Input 2

2 1000000000000
1000000000000 1000000000000

Sample Output 2

500000000000 500000000000 

Problem Statement

The Republic of AtCoder has N islands. Initially, none of the islands has an airport or harbor, and there is no road between any two of them. Takahashi, the king, will provide some means of transportation between these islands. Specifically, he can do the following operations any number of times in any order.

• Choose an integer i such that 1\leq i\leq N and pay a cost of X_i to build an airport on island i.
• Choose an integer i such that 1\leq i\leq N and pay a cost of Y_i to build a harbor on island i.
• Choose an integer i such that 1\leq i\leq M and pay a cost of Z_i to build a road that bidirectionally connects island A_i and island B_i.

Takahashi's objective is to make it possible, for every pair of different islands U and V, to reach island V from island U when one can perform the following actions any number of times in any order.

• When islands S and T both have airports, go from island S to island T.
• When islands S and T both have harbors, go from island S to island T.
• When islands S and T are connected by a road, go from island S to island T.

Find the minimum total cost Takahashi needs to pay to achieve his objective.

Constraints

• 2 \leq N \leq 2\times 10^5
• 1 \leq M \leq 2\times 10^5
• 1\leq X_i\leq 10^9
• 1\leq Y_i\leq 10^9
• 1\leq A_i<B_i\leq N
• 1\leq Z_i\leq 10^9
• (A_i,B_i)\neq (A_j,B_j), if i\neq j.
• All values in the input are integers.

Sample Input 1

4 2
1 20 4 7
20 2 20 3
1 3 5
1 4 6

Sample Output 1

16

Takahashi will build the following infrastructure.

• Pay a cost of X_1=1 to build an airport on island 1.
• Pay a cost of X_3=4 to build an airport on island 3.
• Pay a cost of Y_2=2 to build a harbor on island 2.
• Pay a cost of Y_4=3 to build a harbor on island 4.
• Pay a cost of Z_2=6 to build a road connecting island 1 and island 4.

Then, the objective will be achieved at a cost of 16. There is no way to achieve the objective for a cost of 15 or less, so 16 should be printed.

Sample Input 2

3 1
1 1 1
10 10 10
1 2 100

Sample Output 2

3

It is not mandatory to build all three types of facilities at least once.

Sample Input 3

7 8
35 29 36 88 58 15 25
99 7 49 61 67 4 57
2 3 3
2 5 36
2 6 89
1 6 24
5 7 55
1 3 71
3 4 94
5 6 21

Sample Output 3

160

Problem Statement

There is a sequence X=(X_0, X_1, \ldots) defined by the following recurrence relation.

X_i = \left\{ \begin{array}{ll} S & (i = 0)\\ (A X_{i-1}+B) \bmod P & (i \geq 1) \end{array} \right.

Determine whether there is an i such that X_i=G. If it exists, find the smallest such i.
Here, x \bmod y denotes the remainder when x is divided by y (the least non-negative residue).

You are given T test cases for each input file.

Constraints

• 1 \leq T \leq 100
• 2 \leq P \leq 10^9
• P is a prime.
• 0\leq A,B,S,G < P
• All values in the input are integers.

Sample Input 1

3
5 2 1 1 0
5 2 2 3 0
11 1 1 0 10

Sample Output 1

3
-1
10

For the first test case, we have X=(1,3,2,0,\ldots), so the smallest i such that X_i=0 is 3.
For the second test case, we have X=(3,3,3,3,\ldots), so there is no i such that X_i=0.

Problem Statement

You are given a tuple of N non-negative integers A=(A_1,A_2,\ldots,A_N) such that A_1=0 and A_N>0.

Takahashi has N counters. Initially, the values of all counters are 0.
He will repeat the following operation until, for every 1\leq i\leq N, the value of the i-th counter is at least A_i.

Choose one of the N counters uniformly at random and set its value to 0. (Each choice is independent of others.)
Increase the values of the other counters by 1.

Print the expected value of the number of times Takahashi repeats the operation, modulo 998244353 (see Notes).

Notes

It can be proved that the sought expected value is always finite and rational. Additionally, under the Constraints of this problem, when that value is represented as \frac{P}{Q} using two coprime integers P and Q, one can prove that there is a unique integer R such that R \times Q \equiv P\pmod{998244353} and 0 \leq R \lt 998244353. Find this R.

Constraints

• 2\leq N\leq 2\times 10^5
• 0=A_1\leq A_2\leq \cdots \leq A_N\leq 10^{18}
• A_N>0
• All values in the input are integers.

Sample Input 1

2
0 2

Sample Output 1

6

Let C_i denote the value of the i-th counter.

Here is one possible progression of the process.

• Set the value of the 1-st counter to 0, and then increase the value of the other counter by 1. Now, (C_1,C_2)=(0,1).
• Set the value of the 2-nd counter to 0, and then increase the value of the other counter by 1. Now, (C_1,C_2)=(1,0).
• Set the value of the 1-st counter to 0, and then increase the value of the other counter by 1. Now, (C_1,C_2)=(0,1).
• Set the value of the 1-st counter to 0, and then increase the value of the other counter by 1. Now, (C_1,C_2)=(0,2).

In this case, the operation is performed four times.

The probabilities that the process ends after exactly 1,2,3,4,5,\ldots operation(s) are 0,\frac{1}{4}, \frac{1}{8}, \frac{1}{8}, \frac{3}{32},\ldots, respectively, so the sought expected value is 2\times\frac{1}{4}+3\times\frac{1}{8}+4\times\frac{1}{8}+5\times\frac{3}{32}+\dots=6. Thus, 6 should be printed.

Sample Input 2

5
0 1 3 10 1000000000000000000

Sample Output 2

874839568