Problem Statement

You are given integers L and R.

Find how many integers are between L and R, inclusive.

Constraints

• 1\le L\le R\le 100
• All input values are integers.

Sample Input 1

3 5

Sample Output 1

3

The integers between 3 and 5, inclusive, are 3,4,5, which is three integers. Thus, output 3.

Sample Input 2

1 7

Sample Output 2

7

Sample Input 3

14 79

Sample Output 3

66

Problem Statement

You are given a string S consisting of lowercase English letters and a positive integer N. The length of S is at least 2N+1.

Find the string obtained by removing N characters from the beginning and N characters from the end of S.

Constraints

• S is a string consisting of lowercase English letters.
• N is an integer.
• 2N+1 \leq |S| \leq 30
• 1 \leq N \leq 10

Sample Input 1

chemotherapy
3

Sample Output 1

mother

Removing the first three characters (che) and the last three characters (apy) from chemotherapy gives mother.

Sample Input 2

thermometer
4

Sample Output 2

mom

Sample Input 3

burger
1

Sample Output 3

urge

Problem Statement

You are given a string S consisting of lowercase English letters. Find the character that appears most frequently in S. If multiple such characters exist, report the one that comes earliest in alphabetical order.

Constraints

• 1 \leq |S| \leq 1000 (|S| is the length of the string S.)
• Each character in S is a lowercase English letter.

Sample Input 1

frequency

Sample Output 1

e

In frequency, the letter e appears twice, which is more than any other character, so you should print e.

Sample Input 2

atcoder

Sample Output 2

a

In atcoder, each of the letters a, t, c, o, d, e, and r appears once, so you should print the earliest in alphabetical order, which is a.

Sample Input 3

pseudopseudohypoparathyroidism

Sample Output 3

o

Problem Statement

You are given a positive integer X.

Find the minimum value among all positive integers that can be obtained by rearranging the digits appearing in the decimal representation of X (without leading zeros) such that there is no leading zero.

Constraints

• 1\leq X < 10^5
• X is an integer.

Sample Input 1

903

Sample Output 1

309

There are four positive integers that can be obtained by rearranging the digits appearing in the decimal representation of X such that there is no leading zero: 903, 930, 309, 390; the minimum value among them is 309.

Sample Input 2

432

Sample Output 2

234

Sample Input 3

100

Sample Output 3

100

Problem Statement

A bag contains N balls numbered 1 to N. Ball i has the integer A_i written on it.
Process Q queries.
For each query, a sequence B_1, B_2, \dots, B_{K} of length K is given, and you should perform the following sequence of operations. Here, all B_i are between 1 and N inclusive and are distinct.

• First, remove balls B_1, B_2, \dots, B_K from the bag.
• Then, output the minimum value among the integers written on the balls currently in the bag. (It is guaranteed by the constraints that the bag is not empty at this point.)
• Afterwards, return all K removed balls to the bag.

Constraints

• 6 \leq N \leq 3 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9
• 1 \leq K \leq 5
• 1 \leq B_1 \lt B_2 \lt \dots \lt B_K \leq N
• The sum of K over all queries is at most 4 \times 10^5.
• All input values are integers.

Sample Input 1

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

Sample Output 1

2
1
3
5
2
1

For example, in the first query, balls 4 and 5 are removed from the bag. At this point, the following four balls remain in the bag:

• Ball 1 with 3 written on it
• Ball 2 with 2 written on it
• Ball 3 with 5 written on it
• Ball 6 with 2 written on it

Thus, the minimum value among the integers written on the balls in the bag is 2.

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

You are given a tree with N vertices numbered 1 to N. The i-th edge connects vertices A_i and B_i.

Consider a tree that can be obtained by removing some (possibly zero) edges and vertices from this graph. Find the minimum number of vertices in such a tree that includes all of K specified vertices V_1,\ldots,V_K.

Constraints

• 1 \leq K \leq N \leq 2\times 10^5
• 1 \leq A_i,B_i \leq N
• 1 \leq V_1 < V_2 < \ldots < V_K \leq N
• The given graph is a tree.
• All input values are integers.

Sample Input 1

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

Sample Output 1

4

The given tree is shown on the left in the figure below. The tree with the minimum number of vertices that includes all of vertices 1,3,5 is shown on the right.

Sample Input 2

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

Sample Output 2

4

Sample Input 3

5 1
1 4
2 3
5 2
1 2
1

Sample Output 3

1

Problem Statement

For positive integers a and b, define \mathrm{concat}(a, b) as the integer formed by writing a and b one after another. More formally, \mathrm{concat}(a, b) is defined as follows.

• Let A and B be the strings formed by writing a and b in decimal, respectively. Let C be the string formed by concatenating A and B in this order. The value of C interpreted as an integer in decimal notation is \mathrm{concat}(a, b).

For example, if a = 123 and b = 45, then \mathrm{concat}(a, b) = 12345.

You are given positive integers N and M.
Find the number, modulo 998244353, of pairs (x, y) of positive integers not greater than N such that \mathrm{concat}(x, y) \equiv x + y \pmod{M}.

You are given T test cases; solve each one.

Constraints

• 1 \leq T \leq 10^4
• 1 \leq N \leq 10^{18}
• 2 \leq M \leq 10^9
• All input values are integers.

Sample Input 1

4
3 2
123 456
20260530 460
123456789123456789 998244353

Sample Output 1

3
0
922576091
422081792

For the first test case, three pairs (x, y) satisfy the condition: (2, 1), (2, 2), (2, 3).

Problem Statement

There are N sequences of length M, denoted as A_1, A_2, \ldots, A_N. The i-th sequence is represented by M integers A_{i,1}, A_{i,2}, \ldots, A_{i,M}.

Two sequences X and Y of length M are said to be similar if and only if the number of indices i (1 \leq i \leq M) such that X_i = Y_i is odd.

Find the number of pairs of integers (i,j) satisfying 1 \leq i < j \leq N such that A_i and A_j are similar.

Constraints

• 1 \leq N \leq 2000
• 1 \leq M \leq 2000
• 1 \leq A_{i,j} \leq 999
• All input values are integers.

Sample Input 1

3 3
1 2 3
1 3 4
2 3 4

Sample Output 1

1

The pair (i,j) = (1,2) satisfies the condition because there is only one index k such that A_{1,k} = A_{2,k}, which is k=1.

The pairs (i,j) = (1,3), (2,3) do not satisfy the condition, making (1,2) the only pair that does.

Sample Input 2

6 5
8 27 27 10 24
27 8 2 4 5
15 27 26 17 24
27 27 27 27 27
27 7 22 11 27
19 27 27 27 27

Sample Output 2

5