小 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