23196번 - Landscape Generator 다국어

Interactive Creative Players Collective (ICPC) is working on a new computer game for which they want to generate realistic landscapes. One of the ICPC engineers proposed an algorithm inspired by geological processes. The algorithm starts with a flat landscape and repeatedly modifies it by lifting or lowering continuous blocks, thus forming horsts (lifted blocks) and grabens (lowered blocks). The blocks to be lifted or lowered are selected at random. ICPC hopes to obtain realistic landscapes this way.

Your task is to interpret any sequence of such modifications and output the resulting landscape. The landscape is represented by a sequence of n integer height values, one for each integer point from 1 to n on the x-axis. Figure E.1 illustrates an example by connecting the height values with line segments.

Figure E.1: Illustration of the landscape generated by Sample Input 1.

Initially the height is 0 at all n points. This flat shape is subjected to a sequence of modifications. Each modification applies one of the following four operations with two integer parameters x₁ ≤ x₂:

• R: Raise – increase the height by 1 at all points between x₁ and x₂ inclusive.
• D: Depress – decrease the height by 1 at all points between x₁ and x₂ inclusive.
• H: Hill – add a new linearly shaped hill between x₁ and x₂.
• V: Valley – add a new linearly shaped valley between x₁ and x₂.

Adding a hill to the current landscape works as follows. The heights at points x₁ and x₂ are increased by 1. If x₂ − x₁ > 1, the heights at points x₁ + 1 and x₂ − 1 are increased by 2. If x₂ − x₁ > 3, the heights at points x₁ + 2 and x₂ − 2 are increased by 3, and so on. Figure E.2 shows an example. Adding a valley works in the same way except the heights are decreased instead. The maximal change of height happens in the middle between x₁ and x₂. If x₂ − x₁ is odd, there will be two neighboring points with maximal change, otherwise just one.

Figure E.2: Illustration of the landscape generated by Sample Input 2.

The first line of input contains two integers n and k, where n (1 ≤ n ≤ 200 000) is the number of points, and k (0 ≤ k ≤ 200 000) is the number of modifications. The n points along the x-axis are numbered from 1 to n. The next k lines describe the modifications. Each line contains one character c and two integers x₁ and x₂, where c (one of R, D, H or V) designates the operation and x₁ and x₂ (1 ≤ x₁ ≤ x₂ ≤ n) specify its parameters.

Output n lines, where the i^th line contains the height at point i after applying all modifications in the given order.