Problem Statement

Given is a sequence of three integers A = (A_1, A_2, A_3). On this sequence, you can do the following operation any number of times:

• choose i\in \{1,2,3\} and add 1 to A_i.

Find the minimum number of operations needed to make A arithmetic. Here, the sequence A = (A_1, A_2, A_3) is arithmetic when A_2 - A_1 = A_3 - A_2 holds.

Constraints

• 1\leq A_1, A_2, A_3\leq 10^{15}

Sample Input 1

4 8 10

Sample Output 1

2

One operation with i = 1 and then one operation with i = 3 yield an arithmetic sequence (5, 8, 11).

Sample Input 2

10 3 4

Sample Output 2

4

Four operations with i = 2 yield an arithmetic sequence (10, 7, 4).

Sample Input 3

1 2 3

Sample Output 3

0

The sequence A is already arithmetic from the beginning, so we need zero operations.

Sample Input 4

1000000000000000 1 1000000000000000

Sample Output 4

999999999999999

Problem Statement

Given are three sequences of N integers each: A = (A_1, \ldots, A_N),\,B = (B_1, \ldots, B_N),\,C = (C_1, \ldots, C_N).

You can permute each of these sequences in any way you like. Find the maximum possible number of indices i such that A_i < B_i < C_i after permuting them.

Constraints

• 1\leq N\leq 10^5
• 1\leq A_i, B_i, C_i\leq 10^9

Sample Input 1

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

Sample Output 1

3

We should permute them as follows:

• A = (1,6,8,9,14),
• B = (3,2,10,12,11),
• C = (4,7,15,13,5).

Then, we will have three indices i (i = 1, 3, 4) such that A_i < B_i < C_i.

Sample Input 2

1
10
20
30

Sample Output 2

1

Sample Input 3

3
1 1 1
1 1 2
2 2 2

Sample Output 3

0

Problem Statement

Given is a positive integer N. Consider a sequence of integers A = (A_1, \ldots, A_K) that satisfies the conditions below:

• \sum_{i=1}^K A_i = N;
• each A_i is a positive integer such that every digit in its decimal notation is 1, 2, or 3.

Find the minimum possible value of K, that is, the number of elements in such a sequence A.

Process T test cases per input file.

Constraints

• 1\leq T\leq 1000
• 1\leq N\leq 10^{18}

Sample Input 1

5
456
10000
123
314
91

Sample Output 1

2
4
1
2
4

For each N, one optimal A is shown below.

• For N = 456: A = (133, 323).
• For N = 10000: A = (323, 3132, 3232, 3313).
• For N = 123: A = (123).
• For N = 314: A = (312,2).
• For N = 91: A = (22,23,23,23).

Problem Statement

Given is a sequence of integers A = (A_1, \ldots, A_N).

Consider a pair of sequences of integers B = (B_1, \ldots, B_N) and C = (C_1, \ldots, C_N) that satisfies the following conditions:

• A_i = B_i + C_i holds for each 1\leq i\leq N;
• B is non-decreasing, that is, B_i\leq B_{i+1} holds for each 1\leq i\leq N-1;
• C is non-increasing, that is, C_i\geq C_{i+1} holds for each 1\leq i\leq N-1.

Find the minimum possible value of \sum_{i=1}^N \bigl(\lvert B_i\rvert + \lvert C_i\rvert\bigr).

Constraints

• 1\leq N\leq 2\times 10^5
• -10^8\leq A_i\leq 10^8

Sample Input 1

3
1 -2 3

Sample Output 1

10

One pair of sequences B = (B_1, \ldots, B_N) and C = (C_1, \ldots, C_N) that yields the minimum value is:

• B = (0, 0, 5),
• C = (1, -2, -2).

Here we have \sum_{i=1}^N \bigl(\lvert B_i\rvert + \lvert C_i\rvert\bigr) = (0+1) + (0+2) + (5+2) = 10.

Sample Input 2

4
5 4 3 5

Sample Output 2

17

One pair of sequences B and C that yields the minimum value is:

• B = (0, 1, 2, 4),
• C = (5, 3, 1, 1).

Sample Input 3

1
-10

Sample Output 3

10

One pair of sequences B and C that yields the minimum value is:

• B = (-3),
• C = (-7).

Problem Statement

Two programmers, X and Y, are going to start competitive programming.

One's skill in competitive programming is represented by a positive integer called the level. Initially, X's level is A_X, and Y's level is A_Y. The two will do learning tasks to raise their levels.

We know that they level up as follows.

• X's level raises by one after every B_X learning tasks.
• Y's level raises by one after every B_Y learning tasks.

How many among n = 1, 2, \ldots, N satisfy the following?

• X's level and Y's level are equal when each of them has done exactly n learning tasks.

Process T test cases per input file.

Constraints

• 1\leq T\leq 2\times 10^5
• 1\leq N\leq 10^{9}
• 1\leq A_X, B_X, A_Y, B_Y \leq 10^6

Sample Input 1

5
10 5 3 4 2
5 5 3 4 2
100 5 3 4 2
10 5 3 4 3
10 5 10 5 9

Sample Output 1

6
3
6
0
9

We will describe the first test case.

For each n = 1, 2, \ldots, 10, the two's levels after doing n learning tasks are as follows.

• X's level: 5, 5, 6, 6, 6, 7, 7, 7, 8, 8.
• Y's level: 4, 5, 5, 6, 6, 7, 7, 8, 8, 9.

There are six scenarios (n = 2, 4, 5, 6, 7, 9) where the two's levels are equal, so the answer is 6.

Problem Statement

For a sequence of integers P = (P_1, \ldots, P_M), let f(P) denote the sequence obtained by inserting P_i + P_{i+1} between P_i and P_{i+1} for each 1\leq i\leq M-1. More formally:

• Let Q_i = P_i + P_{i+1} for each 1\leq i\leq M - 1.
• Let f(P) be defined as a sequence of 2M-1 integers f(P) = (P_1, Q_1, P_2, Q_2, \ldots, P_{M-1}, Q_{M-1}, P_M).

Given are three positive integers a, b, and N where a, b\leq N. Let us begin with a sequence A = (a, b) and define a sequence B = (B_1, B_2, \ldots) as follows.

• Do the following N times: replace A with f(A).
• Then, remove from A all values greater than N and let B be the resulting sequence.

Find B_L, \ldots, B_R.

Constraints

• 1\leq N\leq 3\times 10^5
• 1\leq a, b\leq N
• 1\leq L\leq R\leq 10^{18}
• R - L < 3\times 10^5
• R is at most the number of elements in the sequence B.

Sample Input 1

1 1 4
1 7

Sample Output 1

1 4 3 2 3 4 1

Initially, A = (1, 1). The replacements of A with f(A) take place as follows.

• After the first replacement: A = (1, 2, 1).
• After the second replacement: A = (1, 3, 2, 3, 1).
• After the third replacement: A = (1, 4, 3, 5, 2, 5, 3, 4, 1).
• After the fourth replacement: A = (1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1).

Thus, we have B = (1, 4, 3, 2, 3, 4, 1). We should report the 1-st through 7-th elements of this sequence.

Sample Input 2

1 1 4
2 5

Sample Output 2

4 3 2 3

Again, we have B = (1, 4, 3, 2, 3, 4, 1). We should report the 2-nd through 5-th elements of this sequence.

Sample Input 3

2 1 10
5 15

Sample Output 3

8 3 10 7 4 9 5 6 7 8 9

Sample Input 4

10 10 10
2 2

Sample Output 4

10