Little L は正三角形のグリッドを持っています。各グリッド線は、隣接する辺の対応する $n$ 等分点を結ぶ線分です。これらのグリッド線は、正三角形をいくつかの合同な小さい正三角形に分割します。
図におけるグリッド線の各交点を座標 $(x, y)$ で表します。上から下への $x$ 座標の範囲は $1$ から $n + 1$ までです。$x = 1$ は最も上の点を表し、$x = n + 1$ は底辺の直線を表します。上から $i$ 行目では、左から右への格子点の $y$ 座標の範囲は $1$ から $i$ までです。
三角形グリッドの中にはいくつかの正三角形があり、その向きは上向き(upright)または下向き(inverted)のいずれかです。それぞれの向きの三角形を 3 つの数 $x, y, d$ で表します。ここで、$(x, y)$ はグリッドの底辺に平行な辺に対する対角の頂点の座標を表し、$d$ はその一辺の長さ(線分の長さ)を表します。
例えば、下の図において、青い正三角形は上向きの三角形であり、$(x, y, d) = (4, 2, 3)$ です。黄色い正三角形は下向きの三角形であり、$(x, y, d) = (6, 3, 2)$ です。

いま、各単位小正三角形グリッド(向きに関わらず、一辺の長さが $1$ の正三角形)には数が 1 つ書かれています。初期状態では、すべてのグリッド上の数は $0$ です。Little L は以下の操作を行います:
- 正三角形を 1 つ選び、その内部にあるすべてのグリッド上の数に $w$ を加算する。
- 正三角形を 1 つ選び、その内部にあるすべてのグリッド上の数の総和を質問する。
各質問操作に対する答えを計算してください。Little L は大きな数が好きではないため、答えを $2^{32}$ で割った余りのみを出力すれば十分です。
入力
入力の最初の行には 2 つの整数 $n, q$ ($2 \le n \le 10^5, 1 \le q \le 10^5$) が与えられます。
続く $q$ 行はそれぞれ 1 つの操作を表します。
各行は 5 つの数 $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 つの数を新しい行に出力してください。
入出力例
入力 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