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

Print all non-negative integers less than or equal to N in descending order.

Constraints

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

Sample Input 1

3

Sample Output 1

3
2
1
0

We have four non-negative integers less than or equal to 3, which are 0, 1, 2, and 3.
To print them in descending order, print 3 in the first line, 2 in the second, 1 in the third, and 0 in the fourth.

Sample Input 2

22

Sample Output 2

22
21
20
19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
0

Problem Statement

You are given N strings S_1,S_2,\ldots,S_N consisting of lowercase English letters.
Determine if there are distinct integers i and j between 1 and N, inclusive, such that the concatenation of S_i and S_j in this order is a palindrome.

A string T of length M is a palindrome if and only if the i-th character and the (M+1-i)-th character of T are the same for every 1\leq i\leq M.

Constraints

• 2\leq N\leq 100
• 1\leq \lvert S_i\rvert \leq 50
• N is an integer.
• S_i is a string consisting of lowercase English letters.
• All S_i are distinct.

Sample Input 1

5
ab
ccef
da
a
fe

Sample Output 1

Yes

If we take (i,j)=(1,4), the concatenation of S_1=ab and S_4=a in this order is aba, which is a palindrome, satisfying the condition.
Thus, print Yes.

Here, we can also take (i,j)=(5,2), for which the concatenation of S_5=fe and S_2=ccef in this order is feccef, satisfying the condition.

Sample Input 2

3
a
b
aba

Sample Output 2

No

No two distinct strings among S_1, S_2, and S_3 form a palindrome when concatenated. Thus, print No.
Note that the i and j in the statement must be distinct.

Sample Input 3

2
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

Sample Output 3

Yes

Problem Statement

You are given integers A and B, in base K.
Print A \times B in decimal.

Notes

For base-K representation, see Wikipedia's article on Positional notation.

Constraints

• 2 \leq K \leq 10
• 1 \leq A,B \leq 10^5
• A and B are in base-K representation.

Sample Input 1

2
1011 10100

Sample Output 1

220

1011 in base 2 corresponds to 11 in base 10.
10100 in base 2 corresponds to 20 in base 10.
We have 11 \times 20 = 220, so print 220.

Sample Input 2

7
123 456

Sample Output 2

15642

123 in base 7 corresponds to 66 in base 10.
456 in base 7 corresponds to 237 in base 10.
We have 66 \times 237 = 15642, so print 15642.

Problem Statement

You are given a sequence of N numbers: A=(A_1,\ldots,A_N).

Determine whether there is a pair (i,j) with 1\leq i,j \leq N such that A_i-A_j=X.

Constraints

• 2 \leq N \leq 2\times 10^5
• -10^9 \leq A_i \leq 10^9
• -10^9 \leq X \leq 10^9
• All values in the input are integers.

Sample Input 1

6 5
3 1 4 1 5 9

Sample Output 1

Yes

We have A_6-A_3=9-4=5.

Sample Input 2

6 -4
-2 -7 -1 -8 -2 -8

Sample Output 2

No

There is no pair (i,j) such that A_i-A_j=-4.

Sample Input 3

2 0
141421356 17320508

Sample Output 3

Yes

We have A_1-A_1=0.

Problem Statement

Given is a string S consisting of lowercase English letters. Determine whether adding some number of a's (possibly zero) at the beginning of S can make it a palindrome.

Here, a string of length N, A=A_1A_2\ldots A_N, is said to be a palindrome when A_i=A_{N+1-i} for every 1\leq i\leq N.

Constraints

• 1 \leq \lvert S \rvert \leq 10^6
• S consists of lowercase English letters.

Sample Input 1

kasaka

Sample Output 1

Yes

By adding one a at the beginning of kasaka, we have akasaka, which is a palindrome, so Yes should be printed.

Sample Input 2

atcoder

Sample Output 2

No

Adding any number of a's at the beginning of atcoder does not make it a palindrome.

Sample Input 3

php

Sample Output 3

Yes

php itself is a palindrome. Adding zero a's at the beginning of S is allowed, so Yes should be printed.

Problem Statement

In a town divided into a grid with N rows and 10^9 columns, there are N walls, numbered 1 to N.
Wall i ranges from the L_i-th column to the R_i-th column from the left in the i-th row from the top. (See also the figure at Sample Input and Output 1.)

Takahashi has decided to destroy all N walls.
With his superhuman strength, his one punch can damage consecutive D columns at once.

• More formally, he can choose an integer x between 1 and 10^9 - D + 1 (inclusive) to damage all walls that exist (or partly exist) in the x-th through (x + D - 1)-th columns and are not yet destroyed.

When a part of a wall is damaged, that whole wall will be destroyed by the impact of the punch.
(See also the figure at Sample Input and Output 1.)

At least how many times does Takahashi need to punch to destroy all walls?

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq D \leq 10^9
• 1 \leq L_i \leq R_i \leq 10^9
• All values in input are integers.

Sample Input 1

3 3
1 2
4 7
5 9

Sample Output 1

2

The figure below describes the arrangements of walls in Sample Input 1.

He can destroy all walls with two punches, such as the following. (Below, \lbrack a, b \rbrack denotes the range from the a-th through b-th columns.)

• First, punch \lbrack 2, 4 \rbrack. The walls existing in \lbrack 2, 4 \rbrack ― Walls 1 and 2 ― are damaged and destroyed.
• Second, punch \lbrack 5, 7 \rbrack. The wall existing in \lbrack 5, 7 \rbrack ― Wall 3 ― is damaged and destroyed.

It is also possible to destroy all walls with two punches in this way:

• First, punch \lbrack 7, 9 \rbrack to destroy Walls 2 and 3.
• Second, punch \lbrack 1, 3 \rbrack to destroy Wall 1.

Sample Input 2

3 3
1 2
4 7
4 9

Sample Output 2

1

The difference from Sample Input/Output 1 is that Wall 3 now covers \lbrack 4, 9 \rbrack, not \lbrack 5, 9 \rbrack.
In this case, he can punch \lbrack 2, 4 \rbrack to destroy all walls with one punch.

Sample Input 3

5 2
1 100
1 1000000000
101 1000
9982 44353
1000000000 1000000000

Sample Output 3

3

Problem Statement

You are given N points in the coordinate plane. For each 1\leq i\leq N, the i-th point is at the coordinates (X_i, Y_i).

Find the number of lines in the plane that pass K or more of the N points.
If there are infinitely many such lines, print Infinity.

Constraints

• 1 \leq K \leq N \leq 300
• \lvert X_i \rvert, \lvert Y_i \rvert \leq 10^9
• X_i\neq X_j or Y_i\neq Y_j, if i\neq j.
• All values in input are integers.

Sample Input 1

5 2
0 0
1 0
0 1
-1 0
0 -1

Sample Output 1

6

The six lines x=0, y=0, y=x\pm 1, and y=-x\pm 1 satisfy the requirement.
For example, x=0 passes the first, third, and fifth points.

Thus, 6 should be printed.

Sample Input 2

1 1
0 0

Sample Output 2

Infinity

Infinitely many lines pass the origin.

Thus, Infinity should be printed.

Problem Statement

Find the maximum side length of a regular triangle that can be drawn within a rectangle whose side lengths are A and B.

Constraints

• 1 \leq A,B \leq 1000
• A and B are integers.

Sample Input 1

1 1

Sample Output 1

1.03527618041008295791

The following figure shows an optimal drawing, with the side length of \sqrt{6} - \sqrt{2}.

Note that the sample output does not strictly match \sqrt{6}- \sqrt{2}, but the error is within 10^{-9}, so it is considered correct.