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.