Problem Statement

Print an arithmetic sequence with first term A, last term B, and common difference D.

You are only given inputs for which such an arithmetic sequence exists.

Constraints

• 1 \leq A \leq B \leq 100
• 1 \leq D \leq 100
• There is an arithmetic sequence with first term A, last term B, and common difference D.
• All input values are integers.

Sample Input 1

3 9 2

Sample Output 1

3 5 7 9

The arithmetic sequence with first term 3, last term 9, and common difference 2 is (3,5,7,9).

Sample Input 2

10 10 1

Sample Output 2

10

The arithmetic sequence with first term 10, last term 10, and common difference 1 is (10).

Problem Statement

You have an empty sequence A. There are Q queries given, and you need to process them in the order they are given.
The queries are of the following two types:

• 1 x: Append x to the end of A.
• 2 k: Find the k-th value from the end of A. It is guaranteed that the length of A is at least k when this query is given.

Constraints

• 1 \leq Q \leq 100
• In the first type of query, x is an integer satisfying 1 \leq x \leq 10^9.
• In the second type of query, k is a positive integer not greater than the current length of sequence A.

Sample Input 1

5
1 20
1 30
2 1
1 40
2 3

Sample Output 1

30
20

• Initially, A is empty.
• The first query appends 20 to the end of A, making A=(20).
• The second query appends 30 to the end of A, making A=(20,30).
• The answer to the third query is 30, which is the 1-st value from the end of A=(20,30).
• The fourth query appends 40 to the end of A, making A=(20,30,40).
• The answer to the fifth query is 20, which is the 3-rd value from the end of A=(20,30,40).

Problem Statement

There is a single integer N written on a blackboard.
Takahashi will repeat the following series of operations until all integers not less than 2 are removed from the blackboard:

• Choose one integer x not less than 2 written on the blackboard.
• Erase one occurrence of x from the blackboard. Then, write two new integers \left \lfloor \dfrac{x}{2} \right\rfloor and \left\lceil \dfrac{x}{2} \right\rceil on the blackboard.
• Takahashi must pay x yen to perform this series of operations.

Here, \lfloor a \rfloor denotes the largest integer not greater than a, and \lceil a \rceil denotes the smallest integer not less than a.

What is the total amount of money Takahashi will have paid when no more operations can be performed?
It can be proved that the total amount he will pay is constant regardless of the order in which the operations are performed.

Constraints

• 2 \leq N \leq 10^{17}

Sample Input 1

3

Sample Output 1

5

Here is an example of how Takahashi performs the operations:

• Initially, there is one 3 written on the blackboard.
• He chooses 3. He pays 3 yen, erases one 3 from the blackboard, and writes \left \lfloor \dfrac{3}{2} \right\rfloor = 1 and \left\lceil \dfrac{3}{2} \right\rceil = 2 on the blackboard.
• There is one 2 and one 1 written on the blackboard.
• He chooses 2. He pays 2 yen, erases one 2 from the blackboard, and writes \left \lfloor \dfrac{2}{2} \right\rfloor = 1 and \left\lceil \dfrac{2}{2} \right\rceil = 1 on the blackboard.
• There are three 1s written on the blackboard.
• Since all integers not less than 2 have been removed from the blackboard, the process is finished.

Takahashi has paid a total of 3 + 2 = 5 yen for the entire process, so print 5.

Sample Input 2

340

Sample Output 2

2888

Sample Input 3

100000000000000000

Sample Output 3

5655884811924144128

Problem Statement

Takahashi is playing a game.

The game consists of N stages numbered 1,2,\ldots,N. Initially, only stage 1 can be played.

For each stage i ( 1\leq i \leq N-1 ) that can be played, you can perform one of the following two actions at stage i:

• Spend A_i seconds to clear stage i. This allows you to play stage i+1.
• Spend B_i seconds to clear stage i. This allows you to play stage X_i.

Ignoring the times other than the time spent to clear the stages, how many seconds will it take at the minimum to be able to play stage N?

Constraints

• 2 \leq N \leq 2\times 10^5
• 1 \leq A_i, B_i \leq 10^9
• 1 \leq X_i \leq N
• All input values are integers.

Sample Input 1

5
100 200 3
50 10 1
100 200 5
150 1 2

Sample Output 1

350

By acting as follows, you will be allowed to play stage 5 in 350 seconds.

• Spend 100 seconds to clear stage 1, which allows you to play stage 2.
• Spend 50 seconds to clear stage 2, which allows you to play stage 3.
• Spend 200 seconds to clear stage 3, which allows you to play stage 5.

Sample Input 2

10
1000 10 9
1000 10 10
1000 10 2
1000 10 3
1000 10 4
1000 10 5
1000 10 6
1000 10 7
1000 10 8

Sample Output 2

90

Sample Input 3

6
1000000000 1000000000 1
1000000000 1000000000 1
1000000000 1000000000 1
1000000000 1000000000 1
1000000000 1000000000 1

Sample Output 3

5000000000

Problem Statement

There are N boxes numbered 0 to N-1. Initially, box i contains A_i balls.

Takahashi will perform the following operations for i=1,2,\ldots,M in order:

• Set a variable C to 0.
• Take out all the balls from box B_i and hold them in hand.
• While holding at least one ball in hand, repeat the following process:
  • Increase the value of C by 1.
  • Put one ball from hand into box (B_i+C) \bmod N.

Determine the number of balls in each box after completing all operations.

Constraints

• 1 \leq N \leq 2\times 10^5
• 1 \leq M \leq 2\times 10^5
• 0 \leq A_i \leq 10^9
• 0 \leq B_i < N
• All input values are integers.

Sample Input 1

5 3
1 2 3 4 5
2 4 0

Sample Output 1

0 4 2 7 2

The operations proceed as follows:

Sample Input 2

3 10
1000000000 1000000000 1000000000
0 1 0 1 0 1 0 1 0 1

Sample Output 2

104320141 45436840 2850243019

Sample Input 3

1 4
1
0 0 0 0

Sample Output 3

1

Problem Statement

You are given integers X and Y, which satisfy at least one of X \neq 0 and Y \neq 0.
Find a pair of integers (A, B) that satisfies all of the following conditions. If no such pair exists, report so.

• -10^{18} \leq A, B \leq 10^{18}
• The area of the triangle with vertices at points (0, 0), (X, Y), (A, B) on the xy-plane is 1.

Constraints

• -10^{17} \leq X, Y \leq 10^{17}
• (X, Y) \neq (0, 0)
• X and Y are integers.

Sample Input 1

3 5

Sample Output 1

1 1

The area of the triangle with vertices at points (0, 0), (3, 5), (1, 1) is 1. Thus, (A, B) = (1, 1) satisfies the conditions.

Sample Input 2

-2 0

Sample Output 2

0 1

Sample Input 3

8752654402832944 -6857065241301125

Sample Output 3

-1

Problem Statement

There is a tree T with N vertices numbered from 1 to N. The i-th edge connects vertices u_i and v_i. Additionally, vertex i is painted with color A_i.
Find the number, modulo 998244353, of (non-empty) subsets S of the vertex set of T that satisfy the following condition:

• The induced subgraph G of T by S satisfies all of the following conditions:
  • G is a tree.
  • All vertices with degree 1 have the same color.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq N
• 1 \leq u_i \lt v_i \leq N
• The graph given in the input is a tree.
• All input values are integers.

Sample Input 1

3
1 2 1
1 2
2 3

Sample Output 1

4

The following four sets of vertices satisfy the condition.

• \lbrace 1 \rbrace
• \lbrace 1, 2, 3 \rbrace
• \lbrace 2 \rbrace
• \lbrace 3 \rbrace

Sample Input 2

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

Sample Output 2

9

Sample Input 3

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

Sample Output 3

48