E. Mark and Add
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Dustin has an array $$$a_1,a_2,\dots,a_n$$$ where each element is initially $$$0$$$ and is unmarked. The distance between the $$$i$$$-th element and the $$$j$$$-th element is $$$|i-j|$$$. He also has $$$q$$$ updates of two types:

  • $$$1 \; i$$$ — toggle whether element $$$i$$$ is marked. Specifically, if element $$$i$$$ is unmarked, then mark it and if element $$$i$$$ is already marked, then unmark it.
  • $$$2 \; k \; x$$$ — add $$$x$$$ to all elements that are a distance of at most $$$k$$$ from a marked element (note that if an element is a distance of at most $$$k$$$ from multiple marked elements, $$$x$$$ is only added to it once).
Find $$$a_1,a_2,\dots,a_n$$$ after all updates are applied.
Input

The first line contains $$$2$$$ integers, $$$n$$$ and $$$q$$$ ($$$1 \leq n$$$, $$$q \leq 10^5$$$).

Then $$$q$$$ lines follow, which describes the updates. Each line is given by one of the following formats:

  • $$$1 \; i \;$$$ ($$$1 \leq i \leq n$$$) — an update of the first type
  • $$$2 \; k \; x \;$$$ ($$$0 \leq k \leq n, \, 1 \leq x \leq 10^4$$$) — an update of the second type
Output

Please output Dustin's array, $$$a_1,a_2,\dots,a_n$$$, after all updates are applied.

Examples
Input
10 10
1 3
1 6
2 2 1
1 7
2 3 5
1 6
2 1 1
2 2 1
1 3
2 10 1
Output
8 9 9 9 8 9 9 9 7 6
Input
1 1
1 1
Output
0
Note

In the first test case, the array is of size $$$10$$$ and there are $$$10$$$ updates. The array after each update is shown below.

$$$1 \; 3$$$$$$[0, 0, \color{red}{0}, 0, 0, 0, 0, 0, 0, 0]$$$
$$$1 \; 6$$$$$$[0, 0, \color{red}{0}, 0, 0, \color{red}{0}, 0, 0, 0, 0]$$$
$$$2 \; 2 \; 1$$$$$$[1, 1, \color{red}{1}, 1, 1, \color{red}{1}, 1, 1, 0, 0]$$$
$$$1 \; 7$$$$$$[1, 1, \color{red}{1}, 1, 1, \color{red}{1}, \color{red}{1}, 1, 0, 0]$$$
$$$2 \; 3 \; 5$$$$$$[6, 6, \color{red}{6}, 6, 6, \color{red}{6}, \color{red}{6}, 6, 5, 5]$$$
$$$1 \; 6$$$$$$[6, 6, \color{red}{6}, 6, 6, 6, \color{red}{6}, 6, 5, 5]$$$
$$$2 \; 1 \; 1$$$$$$[6, 7, \color{red}{7}, 7, 6, 7, \color{red}{7}, 7, 5, 5]$$$
$$$2 \; 2 \; 1$$$$$$[7, 8, \color{red}{8}, 8, 7, 8, \color{red}{8}, 8, 6, 5]$$$
$$$1 \; 3$$$$$$[7, 8, 8, 8, 7, 8, \color{red}{8}, 8, 6, 5]$$$
$$$2 \; 10 \; 1$$$$$$[8, 9, 9, 9, 8, 9, \color{red}{9}, 9, 7, 6]$$$

Problem Credits: Alex Liang