Problem Statement

Let us define a function f as f(x) = x^2 + 2x + 3.
Given an integer t, find f(f(f(t)+t)+f(f(t))).
Here, it is guaranteed that the answer is an integer not greater than 2 \times 10^9.

Constraints

• t is an integer between 0 and 10 (inclusive).

Sample Input 1

0

Sample Output 1

1371

The answer is computed as follows.

• f(t) = t^2 + 2t + 3 = 0 \times 0 + 2 \times 0 + 3 = 3
• f(t)+t = 3 + 0 = 3
• f(f(t)+t) = f(3) = 3 \times 3 + 2 \times 3 + 3 = 18
• f(f(t)) = f(3) = 18
• f(f(f(t)+t)+f(f(t))) = f(18+18) = f(36) = 36 \times 36 + 2 \times 36 + 3 = 1371

Sample Input 2

3

Sample Output 2

722502

Sample Input 3

10

Sample Output 3

1111355571

Problem Statement

There are N points in a two-dimensional plane. The coordinates of the i-th point are (x_i,y_i).

Find the maximum length of a segment connecting two of these points.

Constraints

• 2 \leq N \leq 100
• -1000 \leq x_i,y_i \leq 1000
• (x_i,y_i) \neq (x_j,y_j)\ (i \neq j)
• All values in input are integers.

Sample Input 1

3
0 0
0 1
1 1

Sample Output 1

1.4142135624

For the 1-st and 3-rd points, the length of the segment connecting them is \sqrt 2 = 1.41421356237\dots, which is the maximum length.

Sample Input 2

5
315 271
-2 -621
-205 -511
-952 482
165 463

Sample Output 2

1455.7159750446

Problem Statement

Among the positive integers that consist of 0's and 2's when written in base 10, find the K-th smallest integer.

Constraints

• K is an integer between 1 and 10^{18} (inclusive).

Sample Input 1

3

Sample Output 1

22

The positive integers that consist of 0's and 2's when written in base 10 are 2,20,22,\dots in ascending order.
The (K=) 3-rd of them, which is 22, should be printed.

Sample Input 2

11

Sample Output 2

2022

Sample Input 3

923423423420220108

Sample Output 3

220022020000202020002022022000002020002222002200002022002200

Note that the exact value of the answer must be printed as an integer, even if it is big.

Problem Statement

Given are a permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N) and a positive integer K.

For each i=K,K+1,\ldots,N, find the following.

• The K-th greatest value among the first i terms of P.

Constraints

• 1 \leq K \leq N \leq 5 \times 10^5
• (P_1,P_2,\ldots,P_N) is a permutation of (1,2,\ldots,N).
• All values in input are integers.

Sample Input 1

3 2
1 2 3

Sample Output 1

1
2

• The (K=) 2-nd greatest value among the first 2 terms of P, (P_1,P_2)=(1,2), is 1.
• The (K=) 2-nd greatest value among the first 3 terms of P, (P_1,P_2,P_3)=(1,2,3), is 2.

Sample Input 2

11 5
3 7 2 5 11 6 1 9 8 10 4

Sample Output 2

2
3
3
5
6
7
7

Problem Statement

Let us call a positive integer n that satisfies the following condition an arithmetic number.

• Let d_i be the i-th digit of n from the top (when n is written in base 10 without unnecessary leading zeros.) Then, (d_2-d_1)=(d_3-d_2)=\dots=(d_k-d_{k-1}) holds, where k is the number of digits in n.
  • This condition can be rephrased into the sequence (d_1,d_2,\dots,d_k) being arithmetic.
  • If n is a 1-digit integer, it is assumed to be an arithmetic number.

For example, 234,369,86420,17,95,8,11,777 are arithmetic numbers, while 751,919,2022,246810,2356 are not.

Find the smallest arithmetic number not less than X.

Constraints

• X is an integer between 1 and 10^{17} (inclusive).

Sample Input 1

152

Sample Output 1

159

The smallest arithmetic number not less than 152 is 159.

Sample Input 2

88

Sample Output 2

88

X itself may be an arithmetic number.

Sample Input 3

8989898989

Sample Output 3

9876543210

Problem Statement

Given is a string S. How many different strings can be obtained as a permutation of a non-empty, not necessarily contiguous subsequence of S?

Since the count can be enormous, print it modulo 998244353.

Constraints

• S is a string of length 1 and 5000 (inclusive) consisting of lowercase English letters.

Sample Input 1

aab

Sample Output 1

8

There are 8 different strings that can be obtained as a permutation of a subsequence of S: a, b, aa, ab, ba, aab, aba, baa.

Sample Input 2

aaa

Sample Output 2

3

Sample Input 3

abcdefghijklmnopqrstuvwxyz

Sample Output 3

149621752

Be sure to print the count modulo 998244353.

Problem Statement

Given is a sequence A of N numbers.

There are 2^{N-1} ways to divide A into non-empty contiguous subsequences B_1,B_2,\ldots,B_k. Find the value below for each of those ways, and print the sum, modulo 998244353, of those values.

• \prod_{i=1}^{k} (\max(B_i)-\min(B_i))

Here, for a sequence B_i=(B_{i,1},B_{i,2},\ldots,B_{i,j}), \max(B_i) and \min(B_i) are defined to be the maximum and minimum values of an element of B_i, respectively.

Constraints

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

Sample Input 1

3
1 2 3

Sample Output 1

2

There are 4 ways to divide A=(1,2,3) into non-empty contiguous subsequences, as follows.

• (1), (2), (3)
• (1), (2,3)
• (1,2), (3)
• (1,2,3)

\prod_{i=1}^{k} (\max(B_i)-\min(B_i)) for these divisions are 0, 0, 0, 2, respectively. The sum of them, 2, should be printed.

Sample Input 2

4
1 10 1 10

Sample Output 2

90

Sample Input 3

10
699498050 759726383 769395239 707559733 72435093 537050110 880264078 699299140 418322627 134917794

Sample Output 3

877646588

Be sure to print the sum modulo 998244353.

Problem Statement

Given are N pairs of integers (x_i,y_i), numbered 1 to N, and an integer K.
List all pairs of integers (p,q) that satisfy the conditions below, in the format specified in Output.

• 1 \le p < q \le N
• \sqrt{(x_p-x_q)^2+(y_p-y_q)^2} \le K

Here, it is guaranteed that there are at most 4 \times 10^5 such pairs of integers.

Constraints

• All values in input are integers.
• 1 \le N \le 2 \times 10^5
• 1 \le K \le 1.5 \times 10^9
• 0 \le x_i,y_i \le 10^9
• There are at most 4 \times 10^5 pairs of integers that should be listed.

Sample Input 1

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

Sample Output 1

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

There are 9 pairs of integers that satisfy the conditions, which should be printed in the specified format.
(1,2),(1,3),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(5,6)

Sample Input 2

2 1414213562
0 0
1000000000 1000000000

Sample Output 2

0

There may be zero pairs of integers that satisfy the conditions.

Sample Input 3

10 150
300 300
300 400
300 500
400 300
400 400
400 400
400 500
500 300
500 400
500 500

Sample Output 3

29
1 2
1 4
1 5
1 6
2 3
2 4
2 5
2 6
2 7
3 5
3 6
3 7
4 5
4 6
4 8
4 9
5 6
5 7
5 8
5 9
5 10
6 7
6 8
6 9
6 10
7 9
7 10
8 9
9 10

There may be pairs of integers (i,j) (i < j) such that x_i=x_j and y_i=y_j.