Peng the Penguin has hired a chef to cook dishes for him daily. Peng assigns a value to each dish, which represents how much satisfaction he gains from that dish. If he really hates the dish, he will assign it a negative number. He wants to gain the most satisfaction possible, but he can only eat a consecutive portion of the meal because he's Peng. He needs someone to write a program to help him determine the maximum amount of satisfaction he can gain daily for days. Furthermore, the chef will only change one dish per day so he doesn't run out of ideas for dishes. The new dish can have the same satisfaction level as the previous one. Note that if the satisfaction Peng can gain by taking any consecutive portion of the meal is negative, he can choose to not take any portion and gain satisfaction as a result.

#### Input Format

An integer , followed by integers on the next line, with the th integer representing .

This is followed by an integer , followed by lines containing two integers each, and , where the dish (0-indexed) now has satisfaction value.

#### Output Format

integers on separate lines, with the th integer representing the maximum satisfaction Peng can obtain on day .

#### Constraints

For all subtasks:

##### Subtask 1 [15%]

##### Subtask 2 [50%]

##### Subtask 3 [35%]

#### Sample Input

```
5
3 -4 2 5 1
3
1 1
2 -6
1 -3
```

#### Sample Output

```
8
12
6
6
```

#### Explanation for Sample Output

On the 1st day, the dishes were 3 -4 2 5 1, and Peng will pick 2 5 1.

On the 2nd day, the dishes were 3 1 2 5 1, and Peng eats everything.

On the 3rd day, the dishes were 3 1 -6 5 1, and Peng will pick 5 1.

On the 4th day, the dishes were 3 -3 -6 5 1, and Peng will pick 5 1.

## Comments

This comment is hidden due to too much negative feedback. Click here to view it.