Problem Statement

You are given a 3-digit positive integer N. Determine whether all digits are the same when N is represented in decimal.

Constraints

• 100 \leq N \leq 999
• The input value is an integer.

Sample Input 1

444

Sample Output 1

Yes

The digits of 444 are 4,4,4, which are the same, so output Yes.

Sample Input 2

160

Sample Output 2

No

The digits of 160 are 1,6,0, which are not the same, so output No.

Sample Input 3

999

Sample Output 3

Yes

Problem Statement

The digit sum of a positive integer n is defined as the sum of the digits when n is represented in decimal. For example, the digit sum of 2026 is 2+0+2+6=10.

Find the number of positive integers not exceeding N whose digit sum is K.

Constraints

• 1\leq N,K \leq 10^5
• All input values are integers.

Sample Input 1

30 4

Sample Output 1

3

Among the positive integers not exceeding 30, there are three integers whose digit sum is 4: 4,13,22.

Sample Input 2

2026 10

Sample Output 2

121

Sample Input 3

99999 45

Sample Output 3

1

Problem Statement

You are given a sequence of N positive integers A=(A_1,A_2,\dots,A_N).

Find all positive integers L for which the following can occur:

AtCoder Inc. has released a stick-shaped snack called "AtCoderiko." A cup contains one or more AtCoderikos, each of length L. When Takahashi shook the cup, each AtCoderiko ended up in one of the following states:

• It remained as one AtCoderiko of length L.
• It broke into two AtCoderikos whose lengths sum to L. Here, the length of each AtCoderiko is a positive integer.

After shaking the cup, there were N AtCoderikos in the cup, and the length of the i-th AtCoderiko was A_i.

The given input guarantees that there exists at least one positive integer L for which this can occur.

Constraints

• 1 \leq N \leq 3 \times 10^5
• 1 \leq A_i \leq 10^9
• There exists at least one L satisfying the condition.
• All input values are integers.

Sample Input 1

4
10 5 5 10

Sample Output 1

10 15

If the cup initially contained three AtCoderikos of length 10, and one of them broke into two AtCoderikos of length 5, the condition is satisfied.
If the cup initially contained two AtCoderikos of length 15, and each of them broke into two AtCoderikos of lengths 5 and 10, the condition is satisfied.
No other values of L satisfy the condition.

Sample Input 2

3
4 4 4

Sample Output 2

4

Sample Input 3

6
10 187 344 100 434 257

Sample Output 3

444

Problem Statement

For i=1,2,\dots,N, let B_i denote the integer formed by concatenating A_i ones.
More formally, B_i=\sum_{j=0}^{A_i-1}{10^j}.
Find \sum_{i=1}^{N}{B_i}.

Constraints

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

Sample Input 1

4
3 3 3 3

Sample Output 1

444

B_1=B_2=B_3=B_4=111, so B_1+B_2+B_3+B_4=444.

Sample Input 2

3
30 10 20

Sample Output 2

111111111122222222223333333333

The answer may be very large.

Sample Input 3

10
1 2 3 4 5 6 7 8 9 10

Sample Output 3

1234567900

Problem Statement

You are given an integer sequence of length N, (A_1,\dots,A_N), and a positive integer D.

Find the number of pairs of integers (L,R) that satisfy both of the following conditions:

• 1 \leq L \leq R \leq N
• Any two elements of (A_L,A_{L+1},\dots,A_R) have a difference of at least D.
  • That is, |A_i-A_j|\geq D for all pairs of integers (i,j) satisfying L \leq i < j \leq R.

Constraints

• 2\leq N \leq 4\times 10^5
• 1 \leq A_i \leq 10^9
• 1 \leq D \leq 10^9

Sample Input 1

5 3
3 1 4 1 5

Sample Output 1

8

The eight pairs (1,1),(2,2),(3,3),(4,4),(5,5),(2,3),(3,4),(4,5) satisfy the conditions.

Sample Input 2

9 1
1 2 3 4 5 6 7 8 9

Sample Output 2

45

Sample Input 3

6 1000000000
123456789 234567891 987654321 321987654 1000000000 1

Sample Output 3

6

Problem Statement

There are N sticks, and the length of the i-th stick is A_i.
You will perform the following operation M times:

• Choose one stick of length at least 2, and let l be the length of this stick. Divide this stick into two sticks of lengths \left\lfloor\frac{l}{2}\right\rfloor and \left\lceil\frac{l}{2}\right\rceil.

From the constraints, it can be proved that it is possible to perform the operation M times.
After M operations, N+M sticks will remain. Find the maximum possible value of the median of the lengths of these sticks.

Solve T test cases per input.

Constraints

• 1 \leq T \leq 10^5
• 1 \leq N \leq 10^5
• 1 \leq A_i \leq 10^9
• 1 \leq M \leq \sum_{i=1}^{N}{A_i} - N
• N+M is odd.
• The sum of N over all test cases is at most 10^5.
• All input values are integers.

Sample Input 1

3
5 2
14 2 5 19 1
10 1
10 6 7 6 2 20 9 16 3 3
4 1
444 444 44 444

Sample Output 1

7
7
444

In the first test case, if you choose the stick of length 14 in the first operation, it is divided into two sticks of length 7, and now you have six sticks of lengths 7,7,2,5,19,1. If you choose the stick of length 19 in the second operation, it is divided into two sticks of lengths 9,10, and now you have seven sticks of lengths 7,7,2,5,9,10,1. In this case, the median of the stick lengths is 7.

Problem Statement

On a two-dimensional coordinate plane, there is a circle with center at point (\frac{A}{C}, \frac{B}{C}) and radius \frac{\sqrt{N}}{C}. Find the number, modulo 998244353, of lattice points on the circumference of this circle.

N is given in its prime factorization form as N=\prod_{i=1}^{M} P_i^{E_i}.

Constraints

• N \geq 1
• 2 \leq P_i \leq 100
• P_i are distinct primes.
• 1 \leq E_i \leq 10^{18}
• 1 \leq C \leq 50
• 0 \leq A,B \lt C
• All input values are integers.

Sample Input 1

1 1 2 2
2 1
5 2

Sample Output 1

12

As shown in the figure below, there are 12 lattice points on the circumference.

Sample Input 2

1 5 14 4
2 1
5 1
13 1
17 1

Sample Output 2

4

As shown in the figure below, there are 4 lattice points on the circumference.

Sample Input 3

1 1 6 3
2 1
5 2
13 1

Sample Output 3

6

As shown in the figure below, there are 6 lattice points on the circumference.

Sample Input 4

0 0 1 10
97 1000000000000000000
89 1000000000000000000
73 1000000000000000000
61 1000000000000000000
59 1000000000000000000
47 1000000000000000000
31 1000000000000000000
23 1000000000000000000
11 1000000000000000000
5 1000000000000000000

Sample Output 4

7885876

Find the number modulo 998244353.