Problem Statement

You are given a positive integer D.

Find the area of a circle with diameter D.

Constraints

• 1\le D\le 100
• The input value is an integer.

Sample Input 1

2

Sample Output 1

3.141592653589793

The area of a circle with diameter 2 is 3.141592653589793\ldots.

Sample Input 2

7

Sample Output 2

38.48451000647496

Sample Input 3

98

Sample Output 3

7542.9639612690935

Problem Statement

There is a rectangular chocolate consisting of H rows and W columns of blocks.

You are given Q queries; process them in order and find the answer to each query. Each query is in one of the following formats:

• Type 1: An integer R is given. Find the number of chocolate blocks in the bottom R rows, then eat them.

• Type 2: An integer C is given. Find the number of chocolate blocks in the rightmost C columns, then eat them.

When the queries are processed in order, the chocolate remains rectangular after each query is processed, and it has at least R + 1 rows immediately before processing a type 1 query and has at least C + 1 columns immediately before processing a type 2 query.

Constraints

• 2 \leq H, W \leq 100
• 1 \leq Q \leq 100
• For type 1 queries, 1 \leq R.
• When the queries are processed in order, the chocolate has at least R + 1 rows immediately before processing a type 1 query.
• For type 2 queries, 1 \leq C.
• When the queries are processed in order, the chocolate has at least C + 1 columns immediately before processing a type 2 query.
• All input values are integers.

Sample Input 1

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

Sample Output 1

28
15
4
4
9

Initially, the chocolate is a rectangle with 7 rows and 9 columns.

For the first query, the number of chocolate blocks in the rightmost 4 columns is 28, so output 28. The chocolate becomes 7 rows and 5 columns.

For the second query, the number of chocolate blocks in the bottom 3 rows is 15, so output 15. The chocolate becomes 4 rows and 5 columns.

For the third query, the number of chocolate blocks in the rightmost 1 column is 4, so output 4. The chocolate becomes 4 rows and 4 columns.

For the fourth query, the number of chocolate blocks in the rightmost 1 column is 4, so output 4. The chocolate becomes 4 rows and 3 columns.

For the fifth query, the number of chocolate blocks in the bottom 3 rows is 9, so output 9. The chocolate becomes 1 row and 3 columns.

Problem Statement

You are given a string S of length N consisting of lowercase English letters.

Find the number of pairs of integers (i, j) satisfying all of the following conditions:

• 1 \leq i \leq j \leq N
• S_i = S_j
• L \leq j - i \leq R

Constraints

• 2 \leq N \leq 5 \times 10^5
• 1 \leq L \leq R \leq N - 1
• N, L, R are integers.
• S is a string of length N consisting of lowercase English letters.

Sample Input 1

6 2 4
aabcba

Sample Output 1

2

The pairs of integers satisfying all the conditions in the problem statement are (i, j) = (2, 6), (3, 5), for a total of two pairs.

Sample Input 2

9 3 6
aaaaaaaaa

Sample Output 2

18

Sample Input 3

10 2 6
aabbccaabb

Sample Output 3

6

Problem Statement

There is a two-dimensional coordinate plane. A lattice point with coordinates (x, y) is painted black if \max(|x|, |y|) is even, and white if it is odd.

Among the pairs of integers (x, y) satisfying L \leq x \leq R and D \leq y \leq U, find the number of those for which the point (x, y) is painted black.

Constraints

• -10^6 \leq L \leq R \leq 10^6
• -10^6 \leq D \leq U \leq 10^6
• All input values are integers.

Sample Input 1

-4 3 1 3

Sample Output 1

10

As shown in the figure above, the answer is 10.

Sample Input 2

-14 14 -14 14

Sample Output 2

449

Problem Statement

You are given integers N, M and an integer sequence A=(A_1,A_2,\ldots,A_N) of length N where each element is between 1 and M, inclusive.

The following operation is performed 10^{100} times on this integer sequence A:

• Let v be the integer between 1 and M, inclusive, with the fewest occurrences in A. If there are multiple such v, take the smallest among them. Then, append v to the end of A.

You are given Q queries. The i-th query gives an integer X_i, so find the value of A_{X_i} after performing the operation 10^{100} times.

Constraints

• 1\le N,M\le 5\times 10^5
• 1\le A_i \le M
• 1\le Q\le 2\times 10^5
• 1\le X_i \le 10^{18}
• All input values are integers.

Sample Input 1

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

Sample Output 1

1
1
2
3
2
3
1
2

Initially, A=(1,1,2). With each operation, A changes as follows:

• First operation: The counts of 1, 2, 3 in A are 2, 1, 0 respectively, so v=3. Append v to the end of A, giving A=(1,1,2,3).
• Second operation: The counts of 1, 2, 3 in A are 2, 1, 1 respectively, so v=2. Append v to the end of A, giving A=(1,1,2,3,2).
• Third operation: The counts of 1, 2, 3 in A are 2, 2, 1 respectively, so v=3. Append v to the end of A, giving A=(1,1,2,3,2,3).
• \vdots

After performing the operation 10^{100} times, A becomes A=(1,1,2,3,2,3,1,2,\ldots).

Sample Input 2

7 30
20 26 3 14 4 4 9
10
31
9
21
23
97
99
30
79
57
3

Sample Output 2

30
2
18
21
7
9
29
19
27
3

Problem Statement

There is a grid with H rows and W columns. The cell at the r-th row from the top and c-th column from the left is called cell (r,c). Each cell is painted black or white: cell (R_k,C_k) is black for k=1,2,\ldots,N, and the remaining HW-N cells are white.

Find the number of rectangular regions in this grid with h rows and w columns such that all cells contained in them are painted white.

More formally, find the number of pairs of integers (r_0, c_0) satisfying all of the following conditions:

• 1\le r_0 \le H-h+1
• 1\le c_0 \le W-w+1
• Cell (r_0+i,c_0+j) is painted white for all pairs of integers (i,j) satisfying 0\le i< h,\ 0\le j< w.

Constraints

• 1\le h\le H\le 10^9
• 1\le w\le W\le 10^9
• 0\le N\le 2\times 10^5
• 1\le R_k\le H
• 1\le C_k\le W
• (R_{k_1},C_{k_1}) \neq (R_{k_2},C_{k_2}) (k_1 \neq k_2)
• All input values are integers.

Sample Input 1

3 4 2 2 3
1 3
2 4
3 1

Sample Output 1

2

The two rectangular regions enclosed in red in the figure below satisfy all the conditions.

Sample Input 2

4 4 3 2 2
2 2
3 4

Sample Output 2

0

No rectangular region satisfies all the conditions.

Sample Input 3

449 449 3 14 0

Sample Output 3

194892

Sample Input 4

31 9 5 7 10
14 8
8 4
18 8
12 1
8 5
9 6
18 1
14 7
5 6
26 7

Sample Output 4

12

Problem Statement

You are given positive integers N, M.

For a positive integer d, define the repunit with d digits as the integer \displaystyle\sum_{i = 0}^{d - 1} 10^i.

Find the number, modulo 998244353, of integers that can be expressed as the sum of (not necessarily distinct) N repunits, each with at least 1 digit and at most M digits.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq M \leq 10^9
• All input values are integers.

Sample Input 1

2 3

Sample Output 1

6

We have 3 repunits with at least 1 digit and at most 3 digits: 1, 11, 111. As the sum of 2 of them, we can express 6 integers: 2, 12, 22, 112, 122, 222.

Sample Input 2

10 10

Sample Output 2

92378

Sample Input 3

12345 123456789

Sample Output 3

133394021