Almost_Certainly — OOI final
Task type: batch | Time limit: 1 s | Memory limit: 512 MB | Difficulty: 24
Algorithms: data structures, sorting, greedy, coordinate compression

# Almost Certainly

| Input file:   | `standard input`  |
|---------------|-------------------|
| Output file:  | `standard output` |
| Time limit:   | 1 second          |
| Memory limit: | 512 megabytes     |

Let's say that two multisets are equal *almost certainly* if they are equal up to one element. That is, it should be possible to change at most one element in the first multiset so that they become equal. For example, the multisets {1, 1, 2} and {1, 2, 3} are equal almost certainly, {1, 1, 1} and {1, 1, 1} are equal almost certainly, and {1, 2, 3} and {3, 4, 5} are not equal almost certainly.

A boy named Vasya really liked this definition and immediately came up with a problem about it.

Vasya has two arrays *a* and *b*, where *a<sub>i</sub>* ≥ *b<sub>i</sub>* for all *i* from 1 to *n*. Vasya can apply the following operation to array *a* as many times as he wants (possibly zero times): choose any index *i* (1 ≤ *i* ≤ *n*) and subtract 1 from *a<sub>i</sub>*. At the same time, Vasya does not change array *b*.

Vasya quickly understood what sequence of operations is needed to make the multiset of values of arrays *a* and *b* equal almost certainly. Therefore, Vasya made the task more complicated—now for each prefix of these arrays, he wants to know the minimum number of operations needed to make the prefixes of the arrays equal almost certainly.

More formally, for each *k* from 1 to *n*, Vasya wants to take the elements *a*<sub>1</sub>, *a*<sub>2</sub>, ..., *a<sub>k</sub>*, as well as the elements *b*<sub>1</sub>, *b*<sub>2</sub>, ..., *b<sub>k</sub>*. Vasya wants to know the minimum number of operations needed to make the multisets of these elements equal almost certainly. Note that the task for each *k* is solved independently.

## Input

Each test consists of one or more sets of input data. The first line contains a single integer *t* (1 ≤ *t* ≤ 100 000)—the number of sets of input data. Then follows the description of the sets of input data.

The first line of each set of input data contains a single integer *n* (1 ≤ *n* ≤ 200 000)—the size of arrays *a* and *b*.

The second line of each set of input data contains *n* integers *a*<sub>1</sub>, *a*<sub>2</sub>, ..., *a<sub>n</sub>* (1 ≤ *a<sub>i</sub>* ≤ 10<sup>9</sup>)—the elements of array *a*.

The third line of each set of input data contains *n* integers *b*<sub>1</sub>, *b*<sub>2</sub>, ..., *b<sub>n</sub>* (1 ≤ *b<sub>i</sub>* ≤ *a<sub>i</sub>*)—the elements of array *b*.

Let *N* be the sum of *n* for all sets of input data in one test. It is guaranteed that *N* ≤ 200 000.

## Output

For each set of input data, output *n* integers, each of which is the answer to the task for each possible prefix length. It can be shown that the answer always exists.

## Examples

| Standard Input                                                                                                | Standard Output                     |
|---------------------------------------------------------------------------------------------------------------|-------------------------------------|
| 4<br>2<br>3 4<br>1 2<br>2<br>3 4<br>1 3<br>3<br>11 17 14<br>1 13 10<br>4<br>100 11 50 42<br>30 1 20 5     | 0 1<br>0 0<br>0 4 2<br>0 10 30 48  |
| 3<br>4<br>2 4 5 12<br>1 3 4 10<br>4<br>3 5 8 20<br>1 2 6 7<br>4<br>4 4 4 4<br>1 2 3 4                       | 0 1 1 3<br>0 1 3 6<br>0 2 3 3      |

## Note

Consider the first set of input data in the first example.

*   For a prefix of length 1, nothing needs to be done.
*   For a prefix of length 2, *a*<sub>1</sub> = 3 needs to be decreased by 1 once, after which *a* will be equal to [2, 4], *b* will be equal to [1, 2], and they will be equal almost certainly.

Consider the third set of input data in the first example.

*   For a prefix of length 1, nothing needs to be done.
*   For a prefix of length 2, *a*<sub>2</sub> = 17 needs to be decreased by 4 times, after which the prefix of *a* will be equal to [11, 13], the prefix of *b* will be equal to [1, 13], and they will be equal almost certainly.
*   For a prefix of length 3, *a*<sub>1</sub> = 11 needs to be decreased by 1 and *a*<sub>3</sub> = 14 needs to be decreased by 1, after which *a* will be equal to [10, 17, 13], *b* will be equal to [1, 13, 11], and they will be equal almost certainly.

## Scoring

The tests for this problem consist of six groups. Points for each group are given only if all tests of the group and all tests of the required groups are passed. Please note that passing the example tests is not required for some groups. *Offline-evaluation* means that the results of testing your solution on this group will only be available after the end of the competition.

| Group | Points | Additional Constraints | Required Groups | Comment                             |
|-------|--------|------------------------|-----------------|-------------------------------------|
| 0     | 0      | –                      | –               | Examples.                           |
| 1     | 16     | *N* ≤ 100              | 0               | –                                   |
| 2     | 13     | *N* ≤ 500              | 0, 1            | –                                   |
| 3     | 24     | *N* ≤ 3000             | 0–2             | –                                   |
| 4     | 13     | –                      | –               | *a<sub>i</sub>* < *b<sub>i+1</sub>*                     |
| 5     | 14     | –                      | 4               | *a<sub>i</sub>* ≤ *a<sub>i+1</sub>*, *b<sub>i</sub>* ≤ *b<sub>i+1</sub>* |
| 6     | 20     | –                      | 0–5             | Offline-evaluation.                 |

It can be shown that all tests of the fourth group satisfy the constraints of the fifth group.

Starter code: