Jian-Jia is building a wall by stacking bricks of the same size together. This wall consists of ~n~ columns of bricks, which are numbered ~0~ to ~n-1~ 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 ~k~ phases of adding or removing bricks. The building process completes when all ~k~ phases are finished. In each phase Jian-Jia is given a range of consecutive brick columns and a height ~h~, 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 ~h~ bricks, so that they have exactly ~h~ bricks. He does nothing on the columns having ~h~ or more bricks.
• In a removing phase, Jian-Jia removes bricks from those columns in the given range that have more than ~h~ bricks, so that they have exactly ~h~ bricks. He does nothing on the columns having ~h~ bricks or less.

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

Example

We assume that there are ~10~ brick columns and ~6~ 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 ~1~ to ~8~	~4~
1	remove	columns ~4~ to ~9~	~1~
2	remove	columns ~3~ to ~6~	~5~
3	add	columns ~0~ to ~5~	~3~
4	add	columns ~2~	~5~
5	remove	columns ~6~ to ~7~	~0~

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

Given the description of the ~k~ 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 ~k~; op[i] is the type of phase ~i~: ~1~ for an adding phase and ~2~ for a removing phase, for ~0 \le i \le k-1~.
  • left and right: arrays of length ~k~; the range of columns in phase ~i~ starts with column left[i] and ends with column right[i] (including endpoints left[i] and right[i]), for ~0 \le i \le k-1~. You will always have left[i] ~\le~ right[i].
  • height: array of length k; height[i] is the height parameter of phase ~i~, for ~0 \le i \le k-1~.
  • finalHeight: array of length ~n~; you should return your results by placing the final number of bricks in column ~i~ into finalHeight[i], for ~0 \le i \le n-1~.

Subtasks

For all subtasks the height parameters of all phases are nonnegative integers less or equal to ~100\,000~.

subtask	points	~n~	~k~	note
1	8	~1 \le n \le 10\,000~	~1 \le k \le 5\,000~	no additional limits
2	24	~1 \le n \le 100\,000~	~1 \le k \le 500\,000~	all adding phases are before all removing phases
3	29	~1 \le n \le 100\,000~	~1 \le k \le 500\,000~	no additional limits
4	39	~1 \le n \le 2\,000\,000~	~1 \le k \le 500\,000~	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[]);