Problem Statement

The number pi to the 100-th decimal place is

3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679.

You are given an integer N between 1 and 100, inclusive.

Print the value of pi to the N-th decimal place.

More precisely, truncate the value of pi to N decimal places and print the result without removing the trailing 0s.

Constraints

• 1\leq N\leq 100
• N is an integer.

Sample Input 1

2

Sample Output 1

3.14

Truncating the value of pi to 2 decimal places results in 3.14. Thus, you should print 3.14.

Sample Input 2

32

Sample Output 2

3.14159265358979323846264338327950

Do not remove the trailing 0s.

Sample Input 3

100

Sample Output 3

3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679

Problem Statement

Does 2^n \gt n^2 hold?

Constraints

• n is an integer between 1 and 10^9 (inclusive).

Sample Input 1

5

Sample Output 1

Yes

Since 2^5=32,\ 5^2=25, we have 2^n \gt n^2, so Yes should be printed.

Sample Input 2

2

Sample Output 2

No

For n=2, we have 2^n=n^2=2^2, so 2^n \gt n^2 does not hold. Thus, No should be printed.

Sample Input 3

623947744

Sample Output 3

Yes

Problem Statement

There are N people numbered 1, 2, \dots, N in the xy-plane. Person i is at the coordinates (X_i, Y_i).
K of these people, Persons A_1, A_2, \dots, A_K, will receive lights of the same strength.
When a person at coordinates (x, y) has a light of strength R, it lights up the interior of a circle of radius R centered at (x, y) (including the boundary).
Find the minimum strength of the lights needed for every person to be lit by at least one light.

Constraints

• All values in input are integers.
• 1 \le K < N \le 1000
• 1 \le A_1 < A_2 < \dots < A_K \le N
• |X_i|,|Y_i| \le 10^5
• (X_i,Y_i) \neq (X_j,Y_j), if i \neq j.

Sample Input 1

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

Sample Output 1

2.23606797749978969

This input contains four people. Among them, Persons 2 and 3 will have lights.
Every person will be lit by at least one light if R \ge \sqrt{5} \approx 2.236068.

Sample Input 2

2 1
2
-100000 -100000
100000 100000

Sample Output 2

282842.712474619009

Sample Input 3

8 3
2 6 8
-17683 17993
93038 47074
58079 -57520
-41515 -89802
-72739 68805
24324 -73073
71049 72103
47863 19268

Sample Output 3

130379.280458974768

Problem Statement

You are given three strings S_1, S_2, S_3 consisting of lowercase English letters, and a string T consisting of 1, 2, 3.

Concatenate the three strings according to the characters in T and print the resulting string. Formally, conform to the following instructions.

• For each integer i such that 1 \leq i \leq |T|, let the string s_i be defined as follows:
  • S_1, if the i-th character of T is 1;
  • S_2, if the i-th character of T is 2;
  • S_3, if the i-th character of T is 3.
• Concatenate the strings s_1, s_2, \dots, s_{|T|} in this order and print the resulting string.

Constraints

• 1 \leq |S_1|, |S_2|, |S_3| \leq 10
• 1 \leq |T| \leq 1000
• S_1, S_2, and S_3 consist of lowercase English letters.
• T consists of 1, 2, and 3.

Sample Input 1

mari
to
zzo
1321

Sample Output 1

marizzotomari

We have s_1 = mari, s_2 = zzo, s_3 = to, s_4 = mari. Concatenate these and print the resulting string: marizzotomari.

Sample Input 2

abra
cad
abra
123

Sample Output 2

abracadabra

Sample Input 3

a
b
c
1

Sample Output 3

a

Problem Statement

Takahashi has created a game where the player controls a dragon on a coordinate plane.

The dragon consists of N parts numbered 1 to N, with part 1 being called the head.

Initially, part i is located at the coordinates (i,0). Process Q queries as follows.

• 1 C: Move the head by 1 in direction C. Here, C is one of R, L, U, and D, which represent the positive x-direction, negative x-direction, positive y-direction, and negative y-direction, respectively. Each part other than the head moves to follow the part in front of it. That is, part i (2\leq i \leq N) moves to the coordinates where part i-1 was before the move.
• 2 p: Find the coordinates of part p.

Constraints

• 2 \leq N \leq 10^6
• 1 \leq Q \leq 2\times 10^5
• For the first type of query, C is one of R, L, U, and D.
• For the second type of query, 1\leq p \leq N.
• All numerical input values are integers.

Sample Input 1

5 9
2 3
1 U
2 3
1 R
1 D
2 3
1 L
2 1
2 5

Sample Output 1

3 0
2 0
1 1
1 0
1 0

At each time when processing the second type of query, the parts are at the following positions:

Note that multiple parts may exist at the same coordinates.

Problem Statement

Given an integer N, find the number of integers X that satisfy all of the following conditions, modulo 998244353.

• X is an N-digit positive integer.
• Let X_1,X_2,\dots,X_N be the digits of X from top to bottom. They satisfy all of the following:
  • 1 \le X_i \le 9 for all integers 1 \le i \le N;
  • |X_i-X_{i+1}| \le 1 for all integers 1 \le i \le N-1.

Constraints

• N is an integer.
• 2 \le N \le 10^6

Sample Input 1

4

Sample Output 1

203

Some of the 4-digit integers satisfying the conditions are 1111,1234,7878,6545.

Sample Input 2

2

Sample Output 2

25

Sample Input 3

1000000

Sample Output 3

248860093

Be sure to find the count modulo 998244353.

Problem Statement

You are given integers X,Y, and an integer K that is at least 2.

There is a variable x, which is initially x=X. You can perform the following operation on x zero or more times:

• Choose an integer y satisfying \displaystyle \left\lfloor \frac xK \right\rfloor=y or \displaystyle \left\lfloor \frac yK \right\rfloor=x, and replace the value of x with y.

Here, \displaystyle \left\lfloor z \right\rfloor is defined as the greatest integer not exceeding z, for a real number z.

Find the minimum number of operations required to make x=Y. Under the given constraints, it can be proved that there always exists a way to make x=Y in a finite number of operations.

You are given T test cases; solve each of them.

Constraints

• 1\le T\le 2\times 10^5
• 0\le X,Y\le 10^{18}
• 2\le K\le 10^{18}
• All input values are integers.

Sample Input 1

4
11 9 3
0 0 2
842 180 7
1948706013487601 48019760148910476 89014537

Sample Output 1

2
0
7
5

Consider the first test case.

By performing the following operations, x=Y can be achieved in two operations:

• Choose y=3. Since \displaystyle\left\lfloor\frac{x}K \right\rfloor=\left\lfloor\frac{11}3 \right\rfloor=3, this choice is valid. Then, replace the value of x with 3.
• Choose y=9. Since \displaystyle\left\lfloor\frac{y}K \right\rfloor=\left\lfloor\frac{9}3 \right\rfloor=3, this choice is valid. Then, replace the value of x with 9.

x=Y cannot be achieved in fewer than two operations, so output 2 on the first line.

Problem Statement

You are given an integer sequence A = (A_1, \dots, A_N) of length N, and integers M and K.
For each i = 1, \dots, N - M + 1, solve the following independent problem.

Find the sum of the first K values in the sorted list of the M integers A_i, A_{i + 1}, \dots, A_{i + M - 1} in ascending order.

Constraints

• 1 \leq K \leq M \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9
• All values in the input are integers.

Sample Input 1

6 4 3
3 1 4 1 5 9

Sample Output 1

5 6 10

• For i = 1, sorting A_i, A_{i+1}, A_{i+2}, A_{i+3} in ascending order yields 1, 1, 3, 4, where the sum of the first three values is 5.
• For i = 2, sorting A_i, A_{i+1}, A_{i+2}, A_{i+3} in ascending order yields 1, 1, 4, 5, where the sum of the first three values is 6.
• For i = 3, sorting A_i, A_{i+1}, A_{i+2}, A_{i+3} in ascending order yields 1, 4, 5, 9, where the sum of the first three values is 10.

Sample Input 2

10 6 3
12 2 17 11 19 8 4 3 6 20

Sample Output 2

21 14 15 13 13

Problem Statement

You are given a string S consisting of digits.

A string T is called a 1122-string if it satisfies all of the following conditions. (The definition is the same as in Problem C.)

• T is a non-empty string consisting of digits.
• |T| is even, where |T| denotes the length of string T.
• All characters from the 1-st through the \frac{|T|}2-th character of T are the same digit.
• All characters from the (\frac{|T|}2+1)-th through the |T|-th character of T are the same digit.
• Adding 1 to the digit of the 1-st character of T gives the digit of the |T|-th character.

For example, 1122, 01, and 444555 are 1122-strings, but 1222 and 90 are not 1122-strings.

Find the number, modulo 998244353, of (not necessarily contiguous) subsequences of S that are 1122-strings.

Two subsequences are counted separately if they are extracted from different positions, even if they are identical as strings.

Constraints

• S is a string consisting of digits with length between 1 and 10^6, inclusive.

Sample Input 1

1122

Sample Output 1

5

The following five subsequences satisfy the condition.

• 12 extracted from the 1-st and 3-rd characters of S
• 12 extracted from the 1-st and 4-th characters of S
• 12 extracted from the 2-nd and 3-rd characters of S
• 12 extracted from the 2-nd and 4-th characters of S
• 1122 extracted from the 1-st through 4-th characters of S

Thus, output 5.

Note that two subsequences are counted separately if they are extracted from different positions, even if they are identical as strings.

Sample Input 2

2025

Sample Output 2

0

There may be no subsequence that is a 1122-string.

Sample Input 3

0777468889971

Sample Output 3

30