Problem Statement

We have five variables x_1, x_2, x_3, x_4, and x_5.

The variable x_i was initially assigned a value of i.

Snuke chose one of these variables and assigned it 0.

You are given the values of the five variables after this assignment.

Find out which variable Snuke assigned 0.

Constraints

• The values of x_1, x_2, x_3, x_4, and x_5 given as input are a possible outcome of the assignment by Snuke.

Sample Input 1

0 2 3 4 5

Sample Output 1

1

In this case, Snuke assigned 0 to x_1, so we should print 1.

Sample Input 2

1 2 0 4 5

Sample Output 2

3

Problem Statement

There are some animals in a garden. Each of them is a crane with two legs or a turtle with four legs.

Takahashi says: "there are X animals in total in the garden, and they have Y legs in total." Determine whether there is a combination of numbers of cranes and turtles in which this statement is correct.

Constraints

• 1 \leq X \leq 100
• 1 \leq Y \leq 100
• All values in input are integers.

Sample Input 1

3 8

Sample Output 1

Yes

The statement "there are 3 animals in total in the garden, and they have 8 legs in total" is correct if there are two cranes and one turtle. Thus, there is a combination of numbers of cranes and turtles in which the statement is correct.

Sample Input 2

2 100

Sample Output 2

No

There is no combination of numbers of cranes and turtles in which this statement is correct.

Sample Input 3

1 2

Sample Output 3

Yes

We also consider the case in which there are only cranes or only turtles.

Problem Statement

Given are an integer X and an integer sequence of length N: p_1, \ldots, p_N.

Among the integers not contained in the sequence p_1, \ldots, p_N (not necessarily positive), find the integer nearest to X, that is, find the integer whose absolute difference with X is the minimum. If there are multiple such integers, report the smallest such integer.

Constraints

• 1 \leq X \leq 100
• 0 \leq N \leq 100
• 1 \leq p_i \leq 100
• p_1, \ldots, p_N are all distinct.
• All values in input are integers.

Sample Input 1

6 5
4 7 10 6 5

Sample Output 1

8

Among the integers not contained in the sequence 4, 7, 10, 6, 5, the one nearest to 6 is 8.

Sample Input 2

10 5
4 7 10 6 5

Sample Output 2

9

Among the integers not contained in the sequence 4, 7, 10, 6, 5, the ones nearest to 10 are 9 and 11. We should print the smaller one, 9.

Sample Input 3

100 0

Sample Output 3

100

When N = 0, the second line in the input will be empty. Also, as seen here, X itself can be the answer.

Problem Statement

Given is a number sequence A of length N.

Find the number of integers i \left(1 \leq i \leq N\right) with the following property:

• For every integer j \left(1 \leq j \leq N\right) such that i \neq j , A_j does not divide A_i.

Constraints

• All values in input are integers.
• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 10^6

Sample Input 1

5
24 11 8 3 16

Sample Output 1

3

The integers with the property are 2, 3, and 4.

Sample Input 2

4
5 5 5 5

Sample Output 2

0

Note that there can be multiple equal numbers.

Sample Input 3

10
33 18 45 28 8 19 89 86 2 4

Sample Output 3

5

Problem Statement

There are N infants registered in AtCoder, numbered 1 to N, and 2\times 10^5 kindergartens, numbered 1 to 2\times 10^5. Infant i has a rating of A_i and initially belongs to Kindergarten B_i.

From now on, Q transfers will happen. After the j-th transfer, Infant C_j will belong to Kindergarten D_j.

Here, we define the evenness as follows. For each kindergarten with one or more infants registered in AtCoder, let us find the highest rating of an infant in the kindergarten. The evenness is then defined as the lowest among those ratings.

For each of the Q transfers, find the evenness just after the transfer.

Constraints

• 1 \leq N,Q \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9
• 1 \leq C_j \leq N
• 1 \leq B_i,D_j \leq 2 \times 10^5
• All values in input are integers.
• In the j-th transfer, Infant C_j changes the kindergarten it belongs to.

Sample Input 1

6 3
8 1
6 2
9 3
1 1
2 2
1 3
4 3
2 1
1 2

Sample Output 1

6
2
6

Initially, Infant 1, 4 belongs to Kindergarten 1, Infant 2, 5 belongs to Kindergarten 2, and Infant 3, 6 belongs to Kindergarten 3.

After the 1-st transfer that makes Infant 4 belong to Kindergarten 3, Infant 1 belongs to Kindergarten 1, Infant 2, 5 belong to Kindergarten 2, and Infant 3, 4, 6 belong to Kindergarten 3. The highest ratings of an infant in Kindergarten 1, 2, 3 are 8, 6, 9, respectively. The lowest among them is 6, so the 1-st line in the output should contain 6.

After the 2-nd transfer that makes Infant 2 belong to Kindergarten 1, Infant 1, 2 belong to Kindergarten 1, Infant 5 belongs to Kindergarten 2, and Infant 3, 4, 6 belong to Kindergarten 3. The highest ratings of an infant in Kindergarten 1, 2, 3 are 8, 2, 9, respectively. The lowest among them is 2, so the 2-nd line in the output should contain 2.

After the 3-rd transfer that makes Infant 1 belong to Kindergarten 2, Infant 2 belongs to Kindergarten 1, Infant 1, 5 belong to Kindergarten 2, and Infant 3, 4, 6 belong to Kindergarten 3. The highest ratings of an infant in Kindergarten 1, 2, 3 are 6, 8, 9, respectively. The lowest among them is 6, so the 3-rd line in the output should contain 6.

Sample Input 2

2 2
4208 1234
3056 5678
1 2020
2 2020

Sample Output 2

3056
4208

Problem Statement

Snuke, a water strider, lives in a rectangular pond that can be seen as a grid with H east-west rows and W north-south columns. Let (i,j) be the square at the i-th row from the north and j-th column from the west.

Some of the squares have a lotus leaf on it and cannot be entered. The square (i,j) has a lotus leaf on it if c_{ij} is @, and it does not if c_{ij} is ..

In one stroke, Snuke can move between 1 and K squares (inclusive) toward one of the four directions: north, east, south, and west. The move may not pass through a square with a lotus leaf. Moving to such a square or out of the pond is also forbidden.

Find the minimum number of strokes Snuke takes to travel from the square (x_1,y_1) to (x_2,y_2). If the travel from (x_1,y_1) to (x_2,y_2) is impossible, point out that fact.

Constraints

• 1 \leq H,W,K \leq 10^6
• H \times W \leq 10^6
• 1 \leq x_1,x_2 \leq H
• 1 \leq y_1,y_2 \leq W
• x_1 \neq x_2 or y_1 \neq y_2.
• c_{i,j} is . or @.
• c_{x_1,y_1} = .
• c_{x_2,y_2} = .
• All numbers in input are integers.

Sample Input 1

3 5 2
3 2 3 4
.....
.@..@
..@..

Sample Output 1

5

Initially, Snuke is at the square (3,2). He can reach the square (3, 4) by making five strokes as follows:

• From (3, 2), go west one square to (3, 1).

• From (3, 1), go north two squares to (1, 1).

• From (1, 1), go east two squares to (1, 3).

• From (1, 3), go east one square to (1, 4).

• From (1, 4), go south two squares to (3, 4).

Sample Input 2

1 6 4
1 1 1 6
......

Sample Output 2

2

Sample Input 3

3 3 1
2 1 2 3
.@.
.@.
.@.

Sample Output 3

-1