小 L 有一個正三角形網格,其中每條網格線都係連接相鄰兩邊對應嘅 $n$ 等分點嘅線段。呢啲網格線將個大正三角形分割成若干個全等嘅細正三角形。
對於圖入面網格線嘅每個交點,我哋用座標 $(x, y)$ 嚟表示。由上至下嘅 $x$ 座標範圍係 $1$ 到 $n + 1$。$x = 1$ 代表最頂端嘅點,而 $x = n + 1$ 代表最底嗰條線。對於第 $i$ 行,由左至右嘅網格點嘅 $y$ 座標範圍係 $1$ 到 $i$。
喺三角形網格入面,有若干個正三角形,佢哋嘅方向可能係正向(朝上)或者反向(朝下)。對於每種方向嘅三角形,我哋用三個數 $x, y, d$ 嚟表示。其中,$(x, y)$ 代表佢平行於網格底邊嘅嗰條邊所對嘅頂點座標,而 $d$ 代表佢嘅邊長(線段嘅長度)。
例如,喺下圖入面,藍色正三角形係一個正向三角形,佢嘅 $(x, y, d) = (4, 2, 3)$。黃色正三角形係一個反向三角形,佢嘅 $(x, y, d) = (6, 3, 2)$。

而家,對於每個單位細正三角形網格(邊長為 $1$ 嘅正三角形,無論方向點樣),上面都寫住一個數字。一開始,網格上面嘅所有數字都係 $0$。小 L 會執行以下操作:
- 揀一個正三角形,將佢入面所有網格上面嘅數字都加 $w$。
- 揀一個正三角形,查詢佢入面所有網格上面嘅數字總和。
佢希望你可以計出每次查詢操作嘅答案。由於小 L 唔鍾意大數,你只需要輸出答案對 $2^{32}$ 取模後嘅結果。
輸入格式
輸入嘅第一行包含兩個整數 $n, q$ ($2 \le n \le 10^5, 1 \le q \le 10^5$)。
接住落嚟嘅 $q$ 行,每行代表一次操作。
每行開頭有五個數 $opt, type, x, y, d$ ($opt \in \{1, 2\}, type \in \{0, 1\}, 1 \le x \le n + 1, 1 \le y \le x, 1 \le d \le n$)。$opt$ 代表操作類型,其中 $opt = 1$ 係修改操作,而 $opt = 2$ 係查詢操作。$type$ 表示呢次操作入面三角形嘅類型,其中 $type = 0$ 代表正向三角形,而 $type = 1$ 代表反向三角形。$x, y, d$ 用嚟描述呢個三角形。如果 $opt = 1$,仲會有一個額外嘅數 $w$ ($0 \le w < 2^{32}$),表示呢次修改操作入面加上去嘅數值。
保證所有輸入嘅三角形面積都唔為零,而且全部都係完全包含喺大三角形內部嘅合法三角形。
輸出格式
對於每個 $opt = 2$ 嘅查詢,喺新嘅一行輸出一個數,代表該區域內數字總和對 $2^{32}$ 取模後嘅結果。
範例
輸入格式 1
5 5 1 0 3 3 2 2 1 1 6 4 2 3 2 0 1 1 5 2 0 3 2 3 2 1 5 3 2
輸出格式 1
20 11 3
輸入格式 2
10 10 1 0 1 1 5 2 1 1 3 2 1 6 1 1 6 4 2 1 2 0 10 3 1 2 1 5 2 1 2 1 6 4 2 1 0 7 7 1 7 1 1 9 3 1 3 1 0 9 5 2 4 2 0 6 1 2
輸出格式 2
0 2 12 0