The Tropical Banana, also known as the Musa verylongnamea, is a delicacy known all over the otherworld. However there is one thing about the Musa verylongnamea that most people do not know: this specific type of banana is extremely picky and will refuse to grow unless heaps and heaps of fertilizer are dumped all over the place it grows, a place known as The Infernal Isles.

With the early retirement of the previous Keeper of Bananas, Florence has been chosen to groom those bananas to perfection. This would normally be an extremely joyous event because of the exorbitant pay, however, there are two problems: she has no idea how to fertilize Tropical Bananas, and each spray of the TURF BUILDER 999 PRO launches layers of fertilizer all over the place. The Infernal Isles is made up of ~N~ separate columns of soil, each originally starting with ~0~ layers of fertilizer. Florence can do one of two tricks with the TURF BUILDER 999 PRO: she can spray column ~l~ to ~r~, adding ~a + b \cdot 1~ layers to column ~l~, ~a + b \cdot 2~ layers to column ~l+1~, and so on until column ~r~ where she adds ~a + b \cdot (r-l+1)~ layers. Otherwise, she can do the opposite, spraying column ~l~ to ~r~ and adding ~a + b \cdot 1~ layers to column ~r~, ~a + b \cdot 2~ layers to column ~r-1~ and so on until column ~l~ where she adds ~a + b \cdot (r-l+1)~ layers. Specifically, there are two operations where:

0 l r a b - for all ~i~ between ~l~ and ~r~ inclusive, increase ~col_i~ by ~a + b \cdot (i-l+1)~.

1 l r a b - for all ~i~ between ~l~ and ~r~ inclusive, increase ~col_i~ by ~a + b \cdot (r-i+1)~.

In fact, the TURF BUILDER 999 PRO is so powerful that it can remove layers of fertilizer and may even cause some columns to have a negative amount of layers of fertilizer! Don't ask what this means, since Florence doesn't know either. She needs to record the number of layers of fertilizer at each column in order to efficiently grow Tropical Bananas, but unfortunately speed math is not her strong suit. Desperate, she asks you, a world renowned Scratch programmer to help her calculate the number of layers of fertilizer at each column after she sprays fertilizer ~Q~ times.

For this problem, Python users are recommended to use PyPy over CPython.

Constraints

For all subtasks:

~1 \le l_i \le r_i \le N~

Subtask 1 [30%]

~1 \le N \le 2\,000~

~1 \le Q \le 2\,000~

~-1\,000 \le a_i, b_i \le 1\,000~

Subtask 2 [70%]

~1 \le N \le 200\,000~

~1 \le Q \le 1\,000\,000~

~-100\,000 \le a_i, b_i \le 100\,000~

Input Specification

The first line will contain two integers ~N~ and ~Q~, representing the number of columns and the number of operations respectively.

Each of the next ~Q~ lines will contain an operation in the form of ~x_i~, ~l_i~, ~r_i~, ~a_i~ and ~b_i~ where ~x_i~ is either ~0~ or ~1~.

Output Specification

Output ~N~ lines, the ~i^\text{th}~ line containing the value of ~col_i~ after all the operations have been applied.

Sample Input 1

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

Sample Output 1

19
12
-7
12

Explanation for Sample 1

The first operation adds ~9~ to all the elements between index ~1~ and ~4~ inclusive. The second operation adds ~-7 \cdot 1 + 10 = 3~ to index ~4~, ~-7 \cdot 2 + 10 = -4~ to index ~3~ and ~-7 \cdot 3 + 10 = -11~ to index ~2~. The third operation adds ~4 + 6 \cdot 1 = 10~ to index ~1~ and ~4 + 6 \cdot 2 = 16~ to index ~2~. Doing all the operations will result in a final list of numbers: ~19~, ~12~, ~-7~ and ~12~.

Sample Input 2

4 5
0 2 4 45 73
1 3 4 61 -10
0 2 4 96 86
1 4 4 27 23
0 1 2 12 48

Sample Output 2

60
408
500
719

Explanation for Sample 2

The first operation adds ~45 + 73 \cdot 1 = 118~ to index ~2~, ~45 + 73 \cdot 2 = 191~ to index ~3~ and ~45 + 73 \cdot 3 = 264~ to index ~4~. The second operation adds ~-10 \cdot 1 + 61 = 51~ to index ~4~ and ~-10 \cdot 2 + 61 = 41~ to index ~3~. Doing all the operations will result in a final list of numbers: ~60~, ~408~, ~500~ and ~719~.