410568: GYM104053 B Ayano and sequences
Description
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}$$$.
InputThe 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.
OutputOutput one line containing $$$n$$$ integers. the $$$i$$$-th integer represents $$$b_i$$$ modulo $$$2^{64}$$$.
ExampleInput5 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 2Output
2 12 12 36 0