Problem Statement

You are given a string S, which represents a weather forecast for the seven days starting tomorrow.
The i-th of those seven days is forecast to be sunny if the i-th character of S is o, and rainy if that character is x.

Tell us whether the N-th day is forecast to be sunny.

Constraints

• N is an integer between 1 and 7 (inclusive).
• S is a string of length 7 consisting of o and x.

Sample Input 1

4
oooxoox

Sample Output 1

No

The forecast for each of the seven days starting tomorrow is as follows: sunny, sunny, sunny, rainy, sunny, sunny, rainy.
In particular, the fourth day is forecast to be rainy.

Sample Input 2

7
ooooooo

Sample Output 2

Yes

Problem Statement

There are four types of oysters, labeled 1, 2, 3, and 4. Exactly one of these types causes stomach trouble if eaten. The other types do not cause stomach trouble when eaten.

Takahashi ate oysters 1 and 2, and Aoki ate oysters 1 and 3. The information on whether each person got sick is given as two strings S_1 and S_2. Specifically, S_1 = sick means Takahashi got sick, and S_1 = fine means Takahashi did not get sick. Likewise, S_2 = sick means Aoki got sick, and S_2 = fine means Aoki did not get sick.

Based on the given information, find which type of oyster causes stomach trouble.

Constraints

• Each of S_1 and S_2 is sick or fine.

Sample Input 1

sick fine

Sample Output 1

2

Takahashi (who ate oysters 1 and 2) got sick, and Aoki (who ate oysters 1 and 3) did not get sick, so it can be concluded that oyster 2 causes stomach trouble.

Sample Input 2

fine fine

Sample Output 2

4

Neither Takahashi (who ate oysters 1 and 2) nor Aoki (who ate oysters 1 and 3) got sick, so it can be concluded that oyster 4 causes stomach trouble.

Problem Statement

Takahashi is at the origin on a two-dimensional coordinate plane.

The cost for him to move from point (a, b) to point (c, d) is \sqrt{(a - c)^2 + (b - d)^2}.

Find the total cost when he starts at the origin, visits N points (X_1, Y_1), \ldots, (X_N, Y_N) in this order, and then returns to the origin.

Constraints

• 1 \leq N \leq 2 \times 10^5
• -10^9 \leq X_i, Y_i \leq 10^9
• All input values are integers.

Sample Input 1

2
1 2
-1 0

Sample Output 1

6.06449510224597979401

The journey consists of the following three steps:

• Move from (0, 0) to (1, 2). The cost is \sqrt{(0 - 1)^2 + (0 - 2)^2} = \sqrt{5} = 2.236067977....
• Move from (1, 2) to (-1, 0). The cost is \sqrt{(1 - (-1))^2 + (2 - 0)^2} = \sqrt{8} = 2.828427124....
• Move from (-1, 0) to (0, 0). The cost is \sqrt{(-1 - 0)^2 + (0 - 0)^2} = \sqrt{1} = 1.

The total cost is 6.064495102....

Sample Input 2

7
-14142 13562
-17320 50807
-22360 67977
24494 89742
-26457 51311
28284 27124
31622 77660

Sample Output 2

384694.57587932075868509383

Sample Input 3

5
-100000 100000
100000 -100000
-100000 100000
100000 -100000
-100000 100000

Sample Output 3

1414213.56237309504880168872

Problem Statement

The AtCoder amusement park has an attraction that can accommodate K people. Now, there are N groups lined up in the queue for this attraction.

The i-th group from the front (1\leq i\leq N) consists of A_i people. For all i (1\leq i\leq N), it holds that A_i \leq K.

Takahashi, as a staff member of this attraction, will guide the groups in the queue according to the following procedure.

Initially, no one has been guided to the attraction, and there are K empty seats.

1. If there are no groups in the queue, start the attraction and end the guidance.
2. Compare the number of empty seats in the attraction with the number of people in the group at the front of the queue, and do one of the following:
   • If the number of empty seats is less than the number of people in the group at the front, start the attraction. Then, the number of empty seats becomes K again.
   • Otherwise, guide the entire group at the front of the queue to the attraction. The front group is removed from the queue, and the number of empty seats decreases by the number of people in the group.
3. Go back to step 1.

Here, no additional groups will line up after the guidance has started. Under these conditions, it can be shown that this procedure will end in a finite number of steps.

Determine how many times the attraction will be started throughout the guidance.

Constraints

• 1\leq N\leq 100
• 1\leq K\leq 100
• 1\leq A_i\leq K\ (1\leq i\leq N)
• All input values are integers.

Sample Input 1

7 6
2 5 1 4 1 2 3

Sample Output 1

4

Initially, the seven groups are lined up as follows:

Part of Takahashi's guidance is shown in the following figure:

• Initially, the group at the front has 2 people, and there are 6 empty seats. Thus, he guides the front group to the attraction, leaving 4 empty seats.
• Next, the group at the front has 5 people, which is more than the 4 empty seats, so the attraction is started.
• After the attraction is started, there are 6 empty seats again, so the front group is guided to the attraction, leaving 1 empty seat.
• Next, the group at the front has 1 person, so they are guided to the attraction, leaving 0 empty seats.

In total, he starts the attraction four times before the guidance is completed. Therefore, print 4.

Sample Input 2

7 10
1 10 1 10 1 10 1

Sample Output 2

7

Sample Input 3

15 100
73 8 55 26 97 48 37 47 35 55 5 17 62 2 60

Sample Output 3

8

Problem Statement

The coordinate plane is covered with 2\times1 tiles. The tiles are laid out according to the following rules:

• For an integer pair (i,j), the square A _ {i,j}=\lbrace(x,y)\mid i\leq x\leq i+1\wedge j\leq y\leq j+1\rbrace is contained in one tile.
• When i+j is even, A _ {i,j} and A _ {i + 1,j} are contained in the same tile.

Tiles include their boundaries, and no two different tiles share a positive area.

Near the origin, the tiles are laid out as follows:

Takahashi starts at the point (S _ x+0.5,S _ y+0.5) on the coordinate plane.

He can repeat the following move as many times as he likes:

• Choose a direction (up, down, left, or right) and a positive integer n. Move n units in that direction.

Each time he enters a tile, he pays a toll of 1.

Find the minimum toll he must pay to reach the point (T _ x+0.5,T _ y+0.5).

Constraints

• 0\leq S _ x\leq2\times10 ^ {16}
• 0\leq S _ y\leq2\times10 ^ {16}
• 0\leq T _ x\leq2\times10 ^ {16}
• 0\leq T _ y\leq2\times10 ^ {16}
• All input values are integers.

Sample Input 1

5 0
2 5

Sample Output 1

5

For example, Takahashi can pay a toll of 5 by moving as follows:

• Move left by 1. Pay a toll of 0.
• Move up by 1. Pay a toll of 1.
• Move left by 1. Pay a toll of 0.
• Move up by 3. Pay a toll of 3.
• Move left by 1. Pay a toll of 0.
• Move up by 1. Pay a toll of 1.

It is impossible to reduce the toll to 4 or less, so print 5.

Sample Input 2

3 1
4 1

Sample Output 2

0

There are cases where no toll needs to be paid.

Sample Input 3

2552608206527595 5411232866732612
771856005518028 7206210729152763

Sample Output 3

1794977862420151

Note that the value to be output may exceed the range of a 32-bit integer.