## IOI '14 P2 - Wall (Standard I/O)

View as PDF

Points: 25 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type

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.

#### 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
1 remove columns to
2 remove columns to
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.

#### Input Specification

• Line of input consists of the two integers , and . is the number of columns of the wall, and is the number of phases.
• Line of input each consists of the format: .
• is the type of phase : for an adding phase and for a removing phase, for .
• the range of columns in phase starts with column and ends with column (including both endpoints and ), for . You will always have .
• is the height parameter of phase , for .

#### Output Specification

The output should consist of integers, one per line, describing the result. Line should describe the final number of bricks in column , for .

#### Sample Input 1

10 3
1 3 4 91220
1 5 9 48623
2 3 5 39412

#### Sample Output 1

0
0
0
39412
39412
39412
48623
48623
48623
48623

#### Sample Input 2

10 6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0

#### Sample Output 2

3
4
5
4
3
3
0
0
1
0