Problem Statement

Given integers R, C, and a 2 \times 2 matrix A, print A_{R,C}.

Constraints

• All values in input are integers.
• 1 \le R,C \le 2
• 0 \le A_{i,j} \le 100

Sample Input 1

1 2
1 0
0 1

Sample Output 1

0

We have A_{1,2}=0.

Sample Input 2

2 2
1 2
3 4

Sample Output 2

4

We have A_{2,2}=4.

Sample Input 3

2 1
90 80
70 60

Sample Output 3

70

We have A_{2,1}=70.

Problem Statement

There are N people numbered 1, 2, \dots, N in the xy-plane. Person i is at the coordinates (X_i, Y_i).
K of these people, Persons A_1, A_2, \dots, A_K, will receive lights of the same strength.
When a person at coordinates (x, y) has a light of strength R, it lights up the interior of a circle of radius R centered at (x, y) (including the boundary).
Find the minimum strength of the lights needed for every person to be lit by at least one light.

Constraints

• All values in input are integers.
• 1 \le K < N \le 1000
• 1 \le A_1 < A_2 < \dots < A_K \le N
• |X_i|,|Y_i| \le 10^5
• (X_i,Y_i) \neq (X_j,Y_j), if i \neq j.

Sample Input 1

4 2
2 3
0 0
0 1
1 2
2 0

Sample Output 1

2.23606797749978969

This input contains four people. Among them, Persons 2 and 3 will have lights.
Every person will be lit by at least one light if R \ge \sqrt{5} \approx 2.236068.

Sample Input 2

2 1
2
-100000 -100000
100000 100000

Sample Output 2

282842.712474619009

Sample Input 3

8 3
2 6 8
-17683 17993
93038 47074
58079 -57520
-41515 -89802
-72739 68805
24324 -73073
71049 72103
47863 19268

Sample Output 3

130379.280458974768

Problem Statement

You are given an integer X. The following action on this integer is called an operation.

• Choose and do one of the following.
  • Add 1 to X.
  • Subtract 1 from X.

The terms in the arithmetic progression S with N terms whose initial term is A and whose common difference is D are called good numbers.
Consider performing zero or more operations to make X a good number. Find the minimum number of operations required to do so.

Constraints

• All values in input are integers.
• -10^{18} \le X,A \le 10^{18}
• -10^6 \le D \le 10^6
• 1 \le N \le 10^{12}

Sample Input 1

6 2 3 3

Sample Output 1

1

Since A=2,D=3,N=3, we have S=(2,5,8).
You can subtract 1 from X once to make X=6 a good number.
It is impossible to make X good in zero operations.

Sample Input 2

0 0 0 1

Sample Output 2

0

We might have D=0. Additionally, no operation might be required.

Sample Input 3

998244353 -10 -20 30

Sample Output 3

998244363

Sample Input 4

-555555555555555555 -1000000000000000000 1000000 1000000000000

Sample Output 4

444445

Problem Statement

You are given a sequence of length N: A=(A_1,A_2,\dots,A_N). The following action on this sequence is called an operation.

• First, choose an integer i such that 1 \le i \le N.
• Next, choose and do one of the following.
  • Add 1 to A_i.
  • Subtract 1 from A_i.

Answer Q questions.
The i-th question is the following.

• Consider performing zero or more operations to change every element of A to X_i. Find the minimum number of operations required to do so.

Constraints

• All values in input are integers.
• 1 \le N,Q \le 2 \times 10^5
• 0 \le A_i \le 10^9
• 0 \le X_i \le 10^9

Sample Input 1

5 3
6 11 2 5 5
5
20
0

Sample Output 1

10
71
29

We have A=(6,11,2,5,5) and three questions in this input.

For the 1-st question, you can change every element of A to 5 in 10 operations as follows.

• Subtract 1 from A_1.
• Subtract 1 from A_2 six times.
• Add 1 to A_3 three times.

It is impossible to change every element of A to 5 in 9 or fewer operations.

For the 2-nd question, you can change every element of A to 20 in 71 operations.

For the 3-rd question, you can change every element of A to 0 in 29 operations.

Sample Input 2

10 5
1000000000 314159265 271828182 141421356 161803398 0 777777777 255255255 536870912 998244353
555555555
321654987
1000000000
789456123
0

Sample Output 2

3316905982
2811735560
5542639502
4275864946
4457360498

The output may not fit into 32-bit integers.

Problem Statement

You are given a sequence of N-1 integers S = (S_1, S_2, \ldots, S_{N-1}), and M distinct integers X_1, X_2, \ldots, X_M, which are called lucky numbers.

A sequence of N integers A = (A_1, A_2, \ldots, A_N) satisfying the following condition is called a good sequence.

A_i + A_{i+1} = S_i holds for every i = 1, 2, \ldots, N-1.

Find the maximum possible number of terms that are lucky numbers in a good sequence A, that is, the maximum possible number of integers i between 1 and N such that A_i \in \lbrace X_1, X_2, \ldots, X_M \rbrace.

Constraints

• 2 \leq N \leq 10^5
• 1 \leq M \leq 10
• -10^9 \leq S_i \leq 10^9
• -10^9 \leq X_i \leq 10^9
• X_1 \lt X_2 \lt \cdots \lt X_M
• All values in input are integers.

Sample Input 1

9 2
2 3 3 4 -4 -7 -4 -1
-1 5

Sample Output 1

4

A good sequence A = (3, -1, 4, -1, 5, -9, 2, -6, 5) contains four terms that are lucky numbers: A_2, A_4, A_5, A_9, which is the maximum possible count.

Sample Input 2

20 10
-183260318 206417795 409343217 238245886 138964265 -415224774 -499400499 -313180261 283784093 498751662 668946791 965735441 382033304 177367159 31017484 27914238 757966050 878978971 73210901
-470019195 -379631053 -287722161 -231146414 -84796739 328710269 355719851 416979387 431167199 498905398

Sample Output 2

8

Problem Statement

Consider a binary tree with N vertices numbered 1, 2, \ldots, N. Here, a binary tree is a rooted tree where each vertex has at most two children. Specifically, each vertex in a binary tree has at most one left child and at most one right child.

Determine whether there exists a binary tree rooted at Vertex 1 satisfying the conditions below, and present such a tree if it exists.

• The depth-first traversal of the tree in pre-order is (P_1, P_2, \ldots, P_N).
• The depth-first traversal of the tree in in-order is (I_1, I_2, \ldots, I_N).

Constraints

• 2 \leq N \leq 2 \times 10^5
• N is an integer.
• (P_1, P_2, \ldots, P_N) is a permutation of (1, 2, \ldots, N).
• (I_1, I_2, \ldots, I_N) is a permutation of (1, 2, \ldots, N).

Sample Input 1

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

Sample Output 1

3 6
0 0
0 5
0 0
0 0
4 2

The binary tree rooted at Vertex 1 shown in the following image satisfies the conditions.

Sample Input 2

2
2 1
1 2

Sample Output 2

-1

No binary tree rooted at Vertex 1 satisfies the conditions, so -1 should be printed.

Problem Statement

Takahashi and Aoki will play a game against each other using N piles of stones.

Initially, for each i = 1, 2, \ldots, N, the i-th pile is composed of A_i stones. The players alternately perform the following action, with Takahashi going first.

• Choose a pile with at least one stone remaining, and remove one or more stones.

However, there are M forbidden moves.
For each i = 1, 2, \ldots, M, it is not allowed to remove exactly Y_i stones from a pile composed of exactly X_i stones.

The first player to become unable to perform the action loses, resulting in the other player's victory. Which player will win when both players employ the optimal strategy for the victory?

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq A_i \leq 10^{18}
• 1 \leq Y_i \leq X_i \leq 10^{18}
• i \neq j \Rightarrow (X_i, Y_i) \neq (X_j, Y_j)
• All values in input are integers.

Sample Input 1

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

Sample Output 1

Takahashi

For each i = 1, 2, 3, let A'_i be the number of stones remaining in the i-th pile. Now, we use the sequence A' = (A'_1, A'_2, A'_3) to represent the numbers of stones remaining in the piles.

Before the start of the game, we have A' = (1, 2, 4). One possible progression of the game is as follows.

• First, Takahashi removes 1 stone from the 3-rd pile. Now, A' = (1, 2, 3).
• Next, Aoki removes 2 stones from the 2-nd pile. Now, A' = (1, 0, 3).
• Then, Takahashi removes 2 stones from the 3-rd pile. Now, A' = (1, 0, 1).

At this point, the 1-st and 3-rd piles still have 1 stone each, but it is forbidden ー as the fourth forbidden move ー to remove exactly 1 stone from a pile composed of exactly 1 stone, so Aoki cannot play. Thus, Takahashi wins.

Sample Input 2

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

Sample Output 2

Aoki

Problem Statement

There are N trees. On Day 0, each tree bears no fruits.
On the morning of Day 1 and subsequent days, the i-th tree bears i new fruits for each i = 1, 2, \ldots, N.

Takahashi will perform Q harvesting. For each i = 1, 2, \ldots, Q, the i-th harvesting takes place on the night of Day D_i, collecting all fruits remaining on the L_i-th through R_i-th trees at that point.

For each of the Q harvesting, print the number of fruits Takahashi will collect, modulo 998244353.

Constraints

• 1 \leq N \leq 10^{18}
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq D_1 \lt D_2 \lt \cdots \lt D_Q \leq 10^{18}
• 1 \leq L_i \leq R_i \leq N
• All values in input are integers.

Sample Input 1

5 3
2 2 3
3 3 4
5 1 5

Sample Output 1

10
15
50

For each i = 1, 2, 3, 4, 5, let A_i be the number of fruits remaining on the i-th tree. Now, we use the sequence A = (A_1, A_2, A_3, A_4, A_5) to represent the numbers of fruits remaining in the trees.

• On Day 0, we have A = (0, 0, 0, 0, 0).
• On the morning of Day 1, each tree bears new fruits, and we have A = (1, 2, 3, 4, 5).
• On the morning of Day 2, each tree bears new fruits, and we have A = (2, 4, 6, 8, 10).
• On the night of Day 2, Takahashi performs the 1-st harvesting. 4 + 6 = 10 fruits are collected, and we have A = (2, 0, 0, 8, 10).
• On the morning of Day 3, each tree bears new fruits, and we have A = (3, 2, 3, 12, 15).
• On the night of Day 3, Takahashi performs the 2-nd harvesting. 3 + 12 = 15 fruits are collected, and we have A = (3, 2, 0, 0, 15).
• On the morning of Day 4, each tree bears new fruits, and we have A = (4, 4, 3, 4, 20).
• On the morning of Day 5, each tree bears new fruits, and we have A = (5, 6, 6, 8, 25).
• On the night of Day 5, Takahashi performs the 3-rd harvesting. 5 + 6 + 6 + 8 + 25 = 50 fruits are collected, and we have A = (0, 0, 0, 0, 0).

Sample Input 2

711741968710511029 1
82803157126515475 516874290286751784 588060532191410838

Sample Output 2

603657470

Be sure to print the numbers modulo 998244353.