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

You are given strings S and T consisting of lowercase English letters. Determine whether T is a (contiguous) substring of S.

A string Y is said to be a (contiguous) substring of X if and only if Y can be obtained by performing the operation below on X zero or more times.

• Do one of the following.
  • Delete the first character in X.
  • Delete the last character in X.

For instance, tag is a (contiguous) substring of voltage, while ace is not a (contiguous) substring of atcoder.

Constraints

• S and T consist of lowercase English letters.
• 1 \le |S|,|T| \le 100 (|X| denotes the length of a string X.)

Sample Input 1

voltage
tag

Sample Output 1

Yes

tag is a (contiguous) substring of voltage.

Sample Input 2

atcoder
ace

Sample Output 2

No

ace is not a (contiguous) substring of atcoder.

Sample Input 3

gorilla
gorillagorillagorilla

Sample Output 3

No

Sample Input 4

toyotasystems
toyotasystems

Sample Output 4

Yes

It is possible that S=T.

Problem Statement

There are non-negative integers A, B, C, D, E, and F, which satisfy A\times B\times C\geq D\times E\times F.
Find the remainder when (A\times B\times C)-(D\times E\times F) is divided by 998244353.

Constraints

• 0\leq A,B,C,D,E,F\leq 10^{18}
• A\times B\times C\geq D\times E\times F
• A, B, C, D, E, and F are integers.

Sample Input 1

2 3 5 1 2 4

Sample Output 1

22

Since A\times B\times C=2\times 3\times 5=30 and D\times E\times F=1\times 2\times 4=8,
we have (A\times B\times C)-(D\times E\times F)=22. Divide this by 998244353 and print the remainder, which is 22.

Sample Input 2

1 1 1000000000 0 0 0

Sample Output 2

1755647

Since A\times B\times C=1000000000 and D\times E\times F=0,
we have (A\times B\times C)-(D\times E\times F)=1000000000. Divide this by 998244353 and print the remainder, which is 1755647.

Sample Input 3

1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000

Sample Output 3

0

We have (A\times B\times C)-(D\times E\times F)=0. Divide this by 998244353 and print the remainder, which is 0.

Problem Statement

Takahashi, who works for a pizza restaurant, is making a delicious cheese pizza for staff meals.
There are N kinds of cheese in front of him.
The deliciousness of the i-th kind of cheese is A_i per gram, and B_i grams of this cheese are available.
The deliciousness of the pizza will be the total deliciousness of cheese he puts on top of the pizza.
However, using too much cheese would make his boss angry, so the pizza can have at most W grams of cheese on top of it.
Under this condition, find the maximum possible deliciousness of the pizza.

Constraints

• All values in input are integers.
• 1 \le N \le 3 \times 10^5
• 1 \le W \le 3 \times 10^8
• 1 \le A_i \le 10^9
• 1 \le B_i \le 1000

Sample Input 1

3 5
3 1
4 2
2 3

Sample Output 1

15

The optimal choice is to use 1 gram of cheese of the first kind, 2 grams of the second kind, and 2 grams of the third kind.
The pizza will have a deliciousness of 15.

Sample Input 2

4 100
6 2
1 5
3 9
8 7

Sample Output 2

100

There may be less than W grams of cheese in total.

Sample Input 3

10 3141
314944731 649
140276783 228
578012421 809
878510647 519
925326537 943
337666726 611
879137070 306
87808915 39
756059990 244
228622672 291

Sample Output 3

2357689932073

Problem Statement

You are given six integers: h_1, h_2, h_3, w_1, w_2, and w_3.
Consider writing a positive integer on each square of a 3 \times 3 grid so that all of the following conditions are satisfied:

• For i=1,2,3, the sum of numbers written in the i-th row from the top is h_i.
• For j=1,2,3, the sum of numbers written in the j-th column from the left is w_i.

For example, if (h_1, h_2, h_3) = (5, 13, 10) and (w_1, w_2, w_3) = (6, 13, 9), then all of the following three ways satisfy the conditions. (There are other ways to satisfy the conditions.)

How many ways are there to write numbers to satisfy the conditions?

Constraints

• 3 \leq h_1, h_2, h_3, w_1, w_2, w_3 \leq 30
• All values in input are integers.

Sample Input 1

3 4 6 3 3 7

Sample Output 1

1

The following is the only way to satisfy the conditions. Thus, 1 should be printed.

Sample Input 2

3 4 5 6 7 8

Sample Output 2

0

There may not be a way to satisfy the conditions.

Sample Input 3

5 13 10 6 13 9

Sample Output 3

120

Sample Input 4

20 25 30 22 29 24

Sample Output 4

30613

Problem Statement

You are given a string S of length N consisting of digits.

Find the number of square numbers that can be obtained by interpreting a permutation of S as a decimal integer.

More formally, solve the following.

Let s _ i be the number corresponding to the i-th digit (1\leq i\leq N) from the beginning of S.

Find the number of square numbers that can be represented as \displaystyle \sum _ {i=1} ^ N s _ {p _ i}10 ^ {N-i} with a permutation P=(p _ 1,p _ 2,\ldots,p _ N) of (1, \dots, N).

Constraints

• 1\leq N\leq 13
• S is a string of length N consisting of digits.
• N is an integer.

Sample Input 1

4
4320

Sample Output 1

2

For P=(4,2,3,1), we have s _ 4\times10 ^ 3+s _ 2\times10 ^ 2+s _ 3\times10 ^ 1+s _ 1=324=18 ^ 2.
For P=(3,2,4,1), we have s _ 3\times10 ^ 3+s _ 2\times10 ^ 2+s _ 4\times10 ^ 1+s _ 1=2304=48 ^ 2.

No other permutations result in square numbers, so you should print 2.

Sample Input 2

3
010

Sample Output 2

2

For P=(1,3,2) or P=(3,1,2), we have \displaystyle\sum _ {i=1} ^ Ns _ {p _ i}10 ^ {N-i}=1=1 ^ 2.
For P=(2,1,3) or P=(2,3,1), we have \displaystyle\sum _ {i=1} ^ Ns _ {p _ i}10 ^ {N-i}=100=10 ^ 2.

No other permutations result in square numbers, so you should print 2. Note that different permutations are not distinguished if they result in the same number.

Sample Input 3

13
8694027811503

Sample Output 3

840

Problem Statement

There are N kinds of coins used in the Kingdom of Atcoder: A_1-yen, A_2-yen, \ldots, A_N-yen coins.
Here, 1=A_1 < \ldots < A_N holds, and A_{i+1} is a multiple of A_i for every 1\leq i \leq N-1.

When paying for a product worth X yen using just these coins, what is the minimum total number of coins used in payment and returned as change?

Accurately, when Y is an integer at least X, find the minimum sum of the number of coins needed to represent exactly Y yen and the number of coins needed to represent exactly Y-X yen.

Constraints

• All values in input are integers.
• 1 \leq N \leq 60
• 1=A_1 < \ldots <A_N \leq 10^{18}
• A_{i+1} is a multiple of A_i for every 1\leq i \leq N-1.
• 1\leq X \leq 10^{18}

Sample Input 1

3 87
1 10 100

Sample Output 1

5

If we pay with one 100-yen coin and receive one 10-yen coin and three 1-yen coins as the change, the total number of coins will be 5.

Sample Input 2

2 49
1 7

Sample Output 2

7

It is optimal to pay with seven 7-yen coins.

Sample Input 3

10 123456789012345678
1 100 10000 1000000 100000000 10000000000 1000000000000 100000000000000 10000000000000000 1000000000000000000

Sample Output 3

233

Problem Statement

You are given a sequence P = (p_1,p_2,\ldots,p_N) that contains 1,2,\ldots,N exactly once each.
You may perform the following operations between 0 and K times in total in any order:

• Choose one term of P and remove it.
• Move the last term of P to the head.

Find the lexicographically smallest P that can be obtained as a result of the operations.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq K \leq N-1
• 1 \leq p_i \leq N
• (p_1,p_2,\ldots,p_N) contains 1,2,\ldots,N exactly once each.
• All values in input are integers.

Sample Input 1

5 3
4 5 2 3 1

Sample Output 1

1 2 3

The following operations make P equal (1,2,3).

• Removing the first term makes P equal (5,2,3,1).
• Moving the last term to the head makes P equal (1,5,2,3).
• Removing the second term makes P equal (1,2,3).

There is no way to obtain P lexicographically smaller than (1,2,3), so this is the answer.

Sample Input 2

3 0
3 2 1

Sample Output 2

3 2 1

You may be unable to perform operations.

Sample Input 3

15 10
12 10 7 2 8 11 9 1 6 14 3 15 13 5 4

Sample Output 3

1 3 4 7 2 8 11 9