Having finished a stressful school term, you finally arrive home, kick back, and relax! It is at this time that your friend calls you, and tells you about a new algorithm he's found!
This algorithm allows for sharing the data of two stacks within a single array of length . Any data belonging to stack A must be placed at the beginning of the array, starting at index . Any data belonging to stack B must be placed at the end of the array, counting downwards from index . To prevent the stacks from colliding with each other, the algorithm uses a buffer zone of some width .
This buffer zone is represented by two integers and , with . These values and are permitted to be any integers, not necessarily nonnegative or less than . The buffer zone can only be changed by the operation of incrementing and together, or decrementing and together. If an index of the array is to be associated with stack , then the condition must hold. If an index of the array is to be associated with stack , then the condition must hold.
There will be queries where one of the stacks temporarily requests use of the some number of array indices. This may require performing operations to change the buffer zone. After each operation, the stack will be cleared and no immediately requires any array indices. The stacks responsible for the queries will alternate between A and B in the order A, B, A, B, and so on. The number of requested indices for each query will be given by the integers , and so on.
For a given width , you want to minimize the number of operations performed on the buffer zone to keep it in a valid state throughout the queries. The initial state of the buffer zone can be determined freely without any extra cost.
However, he needs your help to find the minimum number of operations for every . You'd help your friend, even over the break...right?
The first line contains two space-separated integers and .
lines follow; the -th one contains two space-separated integers and .
Output lines, each containing a single integer: the minimum number of operations for a buffer width of . Output the lines for in increasing order of .
Sample Input 1
3 5 2 1 3 2 1 2
Output for Sample Input 1
0 1 3 8 13
Explanation for Sample Input 1
Consider , for which the answer is 3. To achieve this, use an initial buffer state of . This state is valid for the first two queries. Before the third query, perform one operation to change the state to . Before the fourth query, perform two operations to change the state to . This state remains valid for the remaining queries.