Problem Statement

You are given an integer sequence of length N. The i-th term in the sequence is a_i. In one operation, you can select a term and either increment or decrement it by one.

At least how many operations are necessary to satisfy the following conditions?

• For every i (1≤i≤n), the sum of the terms from the 1-st through i-th term is not zero.
• For every i (1≤i≤n-1), the sign of the sum of the terms from the 1-st through i-th term, is different from the sign of the sum of the terms from the 1-st through (i+1)-th term.

Constraints

• 2 ≤ n ≤ 10^5
• |a_i| ≤ 10^9
• Each a_i is an integer.

Sample Input 1

4
1 -3 1 0

Sample Output 1

4

For example, the given sequence can be transformed into 1, -2, 2, -2 by four operations. The sums of the first one, two, three and four terms are 1, -1, 1 and -1, respectively, which satisfy the conditions.

Sample Input 2

5
3 -6 4 -5 7

Sample Output 2

0

The given sequence already satisfies the conditions.

Sample Input 3

6
-1 4 3 2 -5 4

Sample Output 3

8

Problem Statement

Alice and Brown loves games. Today, they will play the following game.

In this game, there are two piles initially consisting of X and Y stones, respectively. Alice and Bob alternately perform the following operation, starting from Alice:

• Take 2i stones from one of the piles. Then, throw away i of them, and put the remaining i in the other pile. Here, the integer i (1≤i) can be freely chosen as long as there is a sufficient number of stones in the pile.

The player who becomes unable to perform the operation, loses the game.

Given X and Y, determine the winner of the game, assuming that both players play optimally.

Constraints

• 0 ≤ X, Y ≤ 10^{18}

Sample Input 1

2 1

Sample Output 1

Brown

Alice can do nothing but taking two stones from the pile containing two stones. As a result, the piles consist of zero and two stones, respectively. Then, Brown will take the two stones, and the piles will consist of one and zero stones, respectively. Alice will be unable to perform the operation anymore, which means Brown's victory.

Sample Input 2

5 0

Sample Output 2

Alice

Sample Input 3

0 0

Sample Output 3

Brown

Sample Input 4

4 8

Sample Output 4

Alice

Problem Statement

Alice lives on a line. Today, she will travel to some place in a mysterious vehicle. Initially, the distance between Alice and her destination is D. When she input a number x to the vehicle, it will travel in the direction of the destination by a distance of x if this move would shorten the distance between the vehicle and the destination, and it will stay at its position otherwise. Note that the vehicle may go past the destination when the distance between the vehicle and the destination is less than x.

Alice made a list of N numbers. The i-th number in this list is d_i. She will insert these numbers to the vehicle one by one.

However, a mischievous witch appeared. She is thinking of rewriting one number in the list so that Alice will not reach the destination after N moves.

She has Q plans to do this, as follows:

• Rewrite only the q_i-th number in the list with some integer so that Alice will not reach the destination.

Write a program to determine whether each plan is feasible.

Constraints

• 1≤ N ≤ 5*10^5
• 1≤ Q ≤ 5*10^5
• 1≤ D ≤ 10^9
• 1≤ d_i ≤ 10^9(1≤i≤N)
• 1≤ q_i ≤ N(1≤i≤Q)
• D and each d_i are integers.

Sample Input 1

4 10
3 4 3 3
2
4 3

Sample Output 1

NO
YES

For the first plan, Alice will already arrive at the destination by the first three moves, and therefore the answer is NO. For the second plan, rewriting the third number in the list with 5 will prevent Alice from reaching the destination as shown in the following figure, and thus the answer is YES.

Sample Input 2

5 9
4 4 2 3 2
5
1 4 2 3 5

Sample Output 2

YES
YES
YES
YES
YES

Alice will not reach the destination as it is, and therefore all the plans are feasible.

Sample Input 3

6 15
4 3 5 4 2 1
6
1 2 3 4 5 6

Sample Output 3

NO
NO
YES
NO
NO
YES

Problem Statement

You are in charge of controlling a dam. The dam can store at most L liters of water. Initially, the dam is empty. Some amount of water flows into the dam every morning, and any amount of water may be discharged every night, but this amount needs to be set so that no water overflows the dam the next morning.

It is known that v_i liters of water at t_i degrees Celsius will flow into the dam on the morning of the i-th day. You are wondering about the maximum possible temperature of water in the dam at noon of each day, under the condition that there needs to be exactly L liters of water in the dam at that time. For each i, find the maximum possible temperature of water in the dam at noon of the i-th day. Here, consider each maximization separately, that is, the amount of water discharged for the maximization of the temperature on the i-th day, may be different from the amount of water discharged for the maximization of the temperature on the j-th day (j≠i).

Also, assume that the temperature of water is not affected by anything but new water that flows into the dam. That is, when V_1 liters of water at T_1 degrees Celsius and V_2 liters of water at T_2 degrees Celsius are mixed together, they will become V_1+V_2 liters of water at \frac{T_1*V_1+T_2*V_2}{V_1+V_2} degrees Celsius, and the volume and temperature of water are not affected by any other factors.

Constraints

• 1≤ N ≤ 5*10^5
• 1≤ L ≤ 10^9
• 0≤ t_i ≤ 10^9(1≤i≤N)
• 1≤ v_i ≤ L(1≤i≤N)
• v_1 = L
• L, each t_i and v_i are integers.

Sample Input 1

3 10
10 10
20 5
4 3

Sample Output 1

10.0000000
15.0000000
13.2000000

• On the first day, the temperature of water in the dam is always 10 degrees: the temperature of the only water that flows into the dam on the first day.

• 10 liters of water at 15 degrees of Celsius can be stored on the second day, by discharging 5 liters of water on the night of the first day, and mix the remaining water with the water that flows into the dam on the second day.

• 10 liters of water at 13.2 degrees of Celsius can be stored on the third day, by discharging 8 liters of water on the night of the first day, and mix the remaining water with the water that flows into the dam on the second and third days.

Sample Input 2

4 15
0 15
2 5
3 6
4 4

Sample Output 2

0.0000000
0.6666667
1.8666667
2.9333333

Sample Input 3

4 15
1000000000 15
9 5
8 6
7 4

Sample Output 3

1000000000.0000000
666666669.6666666
400000005.0000000
293333338.8666667

Although the temperature of water may exceed 100 degrees Celsius, we assume that water does not vaporize.