To organize the upcoming CCC, Troy is creating test data for the problems! The test data for one question consists of a list of integers . Unfortunately, the CCC Grader requires that test cases be manually entered into the system. Troy knows that this will be really tedious, so he starts right away.

However, the CCC Grader has another weird bug! When Troy submits the test case, the system scans the list in order from left to right. Whenever it comes across an integer , the offending integer and the previous integers are removed from the test case. If there are less than integers currently preceding the offending integer, all integers before the offending integer are removed.

Knowing that this year's CCC is in jeopardy, Troy asks you to perform the following task: For each possible value of from to , can you determine the sum of the integers in the resulting test case?

#### Constraints

##### Subtask 1 [20%]

##### Subtask 2 [40%]

##### Subtask 3 [40%]

No additional constraints.

#### Input Specification

The first line of input contains two integers and .

The next line contains integers .

The next line contains integers .

#### Output Specification

Output lines, where the line is the sum of the integers in the resulting test case if .

#### Sample Input 1

```
5 3
3 2 1 3 1
1 2 1
```

#### Sample Output 1

```
3
5
3
```

#### Explanation for Sample 1

When , we have . We'll denote the resultant test case as a list . Initially .

At , so we remove and the preceeding element from . now becomes

At , so we remove and the preceeding element from . now becomes

has a sum of so this is our answer when .

#### Sample Input 2

```
10 5
2 4 4 1 3 2 2 3 1 4
2 1 2 3 8
```

#### Sample Output 2

```
11
16
11
6
26
```

## Comments