Problem Statement

Takahashi and Aoki are playing baseball. Takahashi is the pitcher, and Aoki is the batter.
Takahashi can throw an invisible pitch. When he throws it, the ball moves linearly at a constant speed V \, \mathrm{m / s}, and it becomes invisible between the moment T seconds after throwing and the moment S seconds after throwing (inclusive). The ball keeps moving when it is invisible.
If the ball is not invisible at the moment the ball is exactly D \, \mathrm{m} away from Takahashi, Aoki can hit the ball. Otherwise, he cannot hit it. Can Aoki hit the ball?

Constraints

• 1 \le V \le 1000
• 1 \le T \lt S \le 1000
• 1 \le D \le 1000
• All values in input are integers.

Sample Input 1

10 3 5 20

Sample Output 1

Yes

The ball is exactly 20 \, \mathrm{m} away from Takahashi at 2 seconds after throwing.
On the other hand, the ball becomes invisible between 3 and 5 seconds (inclusive) after throwing, so Aoki can hit the ball.

Sample Input 2

10 3 5 30

Sample Output 2

No

Note that the ball is also invisible at T seconds and S seconds after throwing.
Here, the ball is exactly D \, \mathrm{m} away from Takahashi at T seconds after throwing, so the ball is invisible and cannot be hit by Aoki.

Problem Statement

Given are an integer sequence A of length N, and an integer X.
Remove all elements that are equal to X from A, and arrange the remaining elements without changing the order to obtain the sequence A'. Print A'.

Constraints

• 1 \le N \le 10^5
• 1 \le X \le 10^9
• 1 \le A_i \le 10^9
• All values in input are integers.

Sample Input 1

5 5
3 5 6 5 4

Sample Output 1

3 6 4

Removing 5s from [3, 5, 6, 5, 4] results in [3, 6, 4].

Sample Input 2

3 3
3 3 3

Sample Output 2

A' can be a sequence with zero elements, in which case we should just print an empty line.

Problem Statement

We have a grid with H rows and W columns. Let (i, j) be the square at the i-th row from the top and j-th column from the left.
Each square is painted black or white. If S_{i, j} is #, (i, j) is painted black; if S_{i, j} is ., (i, j) is painted white.
It is guaranteed that the outermost squares are white. That is, the squares that can be represented as (1, j), (H, j), (i, 1), or (i, W) are white.

Consider the part of the grid that is painted black as a polygon. How many sides does it have (at least)?

Here, it is guaranteed that the part painted black forms a polygon without self-intersection, that is, the following holds:

• at least one square is painted black;
• we can travel between any two squares painted black by repeatedly moving up, down, left, or right while going through only black squares;
• we can travel between any two squares painted white by repeatedly moving up, down, left, or right while going through only white squares. (Note that the outermost squares in the grid are all painted white.)

Constraints

• 3 \le H \le 10
• 3 \le W \le 10
• S_{i, j} is # or ..
• S_{1, j} and S_{H, j} are ..
• S_{i, 1} and S_{i, W} are ..
• The part painted black forms a polygon without self-intersection.

Sample Input 1

5 5
.....
.###.
.###.
.###.
.....

Sample Output 1

4

If we use a coordinate system where the top-left, bottom-left, top-right, and bottom-right corners of the grid are (0, 0), (H, 0), (0, W), and (H, W), the given figure is a quadrilateral whose vertices are (1, 1), (4, 1), (4, 4), and (1, 4).

Problem Statement

We have a circle of radius R centered at (X, Y).
Find the number of grid points (points whose x- and y-coordinates are both integers) within or on the circle.

Constraints

• |X| \le 10^5
• |Y| \le 10^5
• 0 \lt R \le 10^5
• Each of X, Y, and R has at most four digits after the decimal point.

Sample Input 1

0.2 0.8 1.1

Sample Output 1

3

The circle is shown below. The grid points within or on the circle are marked red.

Sample Input 2

100 100 1

Sample Output 2

5

X, Y, and R may not have decimal points. Note that we also count the grid points on the circle.

Sample Input 3

42782.4720 31949.0192 99999.99

Sample Output 3

31415920098

Problem Statement

In the Republic of AtCoder, there are N towns numbered 1 through N and M roads numbered 1 through M.
Road i is a one-way road from Town A_i to Town B_i, and it takes C_i minutes to go through. It is possible that A_i = B_i, and there may be multiple roads connecting the same pair of towns.
Takahashi is thinking about taking a walk in the country. We will call a walk valid when it goes through one or more roads and returns to the town it starts at.
For each town, determine whether there is a valid walk that starts at that town. Additionally, if the answer is yes, find the minimum time such a walk requires.

Constraints

• 1 \le N \le 2000
• 1 \le M \le 2000
• 1 \le A_i \le N
• 1 \le B_i \le N
• 1 \le C_i \le 10^5
• All values in input are integers.

Sample Input 1

4 4
1 2 5
2 3 10
3 1 15
4 3 20

Sample Output 1

30
30
30
-1

By Roads 1, 2, 3, Towns 1, 2, 3 forms a ring that takes 30 minutes to go around.
From Town 4, we can go to Towns 1, 2, 3, but then we cannot return to Town 4.

Sample Input 2

4 6
1 2 5
1 3 10
2 4 5
3 4 10
4 1 10
1 1 10

Sample Output 2

10
20
30
20

There may be a road such that A_i = B_i.
Here, we can use just Road 6 to depart from Town 1 and return to that town.

Sample Input 3

4 7
1 2 10
2 3 30
1 4 15
3 4 25
3 4 20
4 3 20
4 3 30

Sample Output 3

-1
-1
40
40

Note that there may be multiple roads connecting the same pair of towns.

Problem Statement

There are N integers A_1, A_2, A_3, \dots, A_N written on a blackboard.
You will do the following operation N - 1 times:

• Choose two numbers written on the blackboard and erase them. Let x and y be the erased numbers. Then, write \gcd(x, y) or \min(x, y) on the blackboard.

After N - 1 operations, just one integer will remain on the blackboard. How many possible values of this number are there?

Constraints

• 2 \le N \le 2000
• 1 \le A_i \le 10^9
• All values in input are integers.

Sample Input 1

3
6 9 12

Sample Output 1

2

The possible values of the last remaining number are 3 and 6.
We will have 3 in the end if, for example, we do as follows:

• choose 9, 12 and erase them from the blackboard, then write \gcd(9, 12) = 3;
• choose 6, 3 and erase them from the blackboard, then write \min(6, 3) = 3.

Also, we will have 6 in the end if, for example, we do as follows:

• choose 6, 12 and erase them from the blackboard, then write \gcd(6, 12) = 6;
• choose 6, 9 and erase them from the blackboard, then write \min(6, 9) = 6.

Sample Input 2

4
8 2 12 6

Sample Output 2

1

2 is the only number that can remain on the blackboard.

Sample Input 3

7
30 28 33 49 27 37 48

Sample Output 3

7

1, 2, 3, 4, 6, 7, and 27 can remain on the blackboard.