Jian-Jia is building a wall by stacking bricks of the same size together. This wall consists of columns of bricks, which are numbered to from left to right. The columns may have different heights. The height of a column is the number of bricks in it.

Jian-Jia builds the wall as follows. Initially there are no bricks in any column. Then, Jian-Jia goes through phases of *adding* or *removing* bricks. The building process completes when all phases are finished. In each phase Jian-Jia is given a range of consecutive brick columns and a height , and he does the following procedure:

- In an
*adding*phase, Jian-Jia adds bricks to those columns in the given range that have less than bricks, so that they have exactly bricks. He does nothing on the columns having or more bricks. - In a
*removing*phase, Jian-Jia removes bricks from those columns in the given range that have more than bricks, so that they have exactly bricks. He does nothing on the columns having bricks or less.

Your task is to determine the final shape of the wall.

#### Example

We assume that there are brick columns and wall building phases. All ranges in the following table are inclusive. Diagrams of the wall after each phase are shown below.

phase | type | range | height |
---|---|---|---|

0 | add | columns to | |

1 | remove | columns to | |

2 | remove | columns to | |

3 | add | columns to | |

4 | add | columns | |

5 | remove | columns to |

Since all columns are initially empty, after phase each of the columns to will have bricks. Columns and remain empty. In phase , the bricks are removed from columns to until each of them has brick, and column remains empty. Columns to , which are out of the given range, remain unchanged. Phase makes no change since columns to do not have more than bricks. After phase the numbers of bricks in columns , , and increase to . There are bricks in column after phase . Phase removes all bricks from columns and .

Given the description of the phases, please calculate the number of bricks in each column after all phases are finished. You need to implement the function `buildWall`

.

`buildWall(n, k, op, left, right, height, finalHeight)`

`n`

: the number of columns on the wall.`k`

: the number of phases.`op`

: array of length ;`op[i]`

is the type of phase : for an adding phase and for a removing phase, for .`left`

and`right`

: arrays of length ; the range of columns in phase starts with column`left[i]`

and ends with column`right[i]`

(including endpoints`left[i]`

and`right[i]`

), for . You will always have`left[i]`

`right[i]`

.`height`

: array of length`k`

;`height[i]`

is the height parameter of phase , for .`finalHeight`

: array of length ; you should return your results by placing the final number of bricks in column into`finalHeight[i]`

, for .

#### Subtasks

For all subtasks the height parameters of all phases are nonnegative integers less or equal to .

subtask | points | note | ||
---|---|---|---|---|

1 | 8 | no additional limits | ||

2 | 24 | all adding phases are before all removing phases | ||

3 | 29 | no additional limits | ||

4 | 39 | no additional limits |

#### Implementation details

Your submission should implement the subprogram described above using the following signatures.

```
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]);
```

## Comments

columns...

that's a pretty long wall

who's gonna pay for it?

MEXICOOOOO!