Water Level Disturbance

Consider a lake at the top of a mountain which is modeled as a straight line of length \(m\). Initially, the water level at each point is \(0\). Then, in an instant, a number of small square "friends" jump into the water at various positions. Each friend has a volume \(v\) and lands at a specified point \(i\). Multiple friends may land at the same point.

When a friend with volume \(v\) jumps into the water at position \(i\), the water level changes as follows:

• For indices from \(i-v+1\) to \(i\), the water level decreases by amounts \(1,2,\ldots,v\) respectively. That is, at index \(j\) (where \(i-v+1 \le j \le i\)), the water level decreases by \(j-(i-v)\).
• For indices from \(i\) to \(i+v-1\), the water level decreases by amounts \(v,v-1,\ldots,1\) respectively. In particular, at index \(j\) (where \(i \le j \le i+v-1\)), the water level decreases by \(i+v-j\). Note that the point \(i\) is affected by both ranges, resulting in a total decrease of \(2v\) at \(i\).
• On the left side of the splash:
  • The water level at \(i-v\) remains unchanged.
  • For indices from \(i-v-1\) down to \(i-2v\) (i.e. \(j=i-2v,\ldots,i-v-1\) in increasing order), the water level increases by \(1,2,\ldots,v\) respectively. Equivalently, at index \(j\) the increment is \(i-v-j\) (when \(j\) is within this range).
  • For indices from \(i-2v\) down to \(i-3v+1\) (i.e. \(j=i-3v+1,\ldots,i-2v\) in increasing order), the water level increases by \(v,v-1,\ldots,1\) respectively. That is, at index \(j\) the increase is \(j-i+3v\).
• On the right side of the splash:
  • The water level at \(i+v\) remains unchanged.
  • For indices from \(i+v+1\) to \(i+2v\), the water level increases by \(1,2,\ldots,v\) respectively. That is, at index \(j\) the increase is \(j-i-v\).
  • For indices from \(i+2v\) to \(i+3v-1\), the water level increases by \(v,v-1,\ldots,1\) respectively. Equivalently, at index \(j\) the increase is \(i+3v-j\).

After all \(n\) friends have jumped into the lake, compute the final water level at each integer point along the lake (from \(1\) to \(m\)).

inputFormat

The first line contains two integers \(m\) and \(n\) \( (1 \le m, n \le \text{constraints})\), representing the length of the lake and the number of events respectively.

Each of the following \(n\) lines contains two integers \(i\) and \(v\) \( (1 \le i \le m,\ v \ge 1)\), representing the splash point and the volume of the friend that jumps into the water.

Note that if a calculated index lies outside the range \([1, m]\), its effect is ignored.

outputFormat

Output a single line with \(m\) integers, where the \(j\)th integer represents the final water level at position \(j\) after all events. The numbers should be separated by a space.

sample

10 1
5 2

4 1 0 -1 -4 -1 0 1 4 1