B. Ayano and sequences
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Ayano have three arrays of integers $$$a_1,\ldots,a_n$$$ , $$$b_1,\ldots,b_n$$$ and $$$c_1,\ldots,c_n$$$ . Initially, the value of every $$$b_i,c_i$$$ is zero.

Now she wants you to do $$$q$$$ operations. There are two types of operations:

  • 1 l r w ($$$1\leq l\le r \leq n$$$, $$$1\leq w\leq n$$$): for each $$$i$$$ that $$$l\leq i \leq r$$$ , set $$$a_i$$$ to $$$w$$$.
  • 2 l r w ($$$1\leq l\le r \leq n$$$, $$$1\leq w\leq 10^9$$$): for each $$$i$$$ that $$$l\leq i \leq r$$$ , increase $$$c_i$$$ by $$$w$$$.

At the end of each operation, for each $$$i$$$ ($$$1\leq i\leq n$$$), Ayano will increase $$$b_{a_i}$$$ by $$$c_i$$$.

Please tell her the array $$$b_1,\ldots,b_n$$$ after all of the operations. Because the answer is very large, you only have to output each number modulo $$$2^{64}$$$.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1\leq n,q \leq 5\cdot 10^5$$$), representing the length of the arrays and the number of operations.

The next line contains $$$n$$$ integers $$$a_1,\ldots,a_n$$$ ($$$1\leq a_i\leq n$$$).

Each line of the following $$$q$$$ lines contains four integers $$$t_i,l_i,r_i,w_i$$$ ($$$1\leq t_i\leq 2$$$) — the operations.

Output

Output one line containing $$$n$$$ integers. the $$$i$$$-th integer represents $$$b_i$$$ modulo $$$2^{64}$$$.

Example
Input
5 6
1 2 3 4 5
2 2 4 1
1 2 3 3
2 3 4 3
1 3 5 4
2 1 5 2
1 1 3 2
Output
2 12 12 36 0