三角形

小 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$。

接下来的 $q$ 行，每行代表一次操作。

每行的开头有五个数字 $opt,type,x,y,d$。$opt$ 代表本次操作的类型，$opt=1$ 时为修改操作，$opt=2$ 时为询问操作。$type$ 为此次操作三角形的类型，$type=0$ 时为正向放置的三角形，$type=1$ 时为反向放置的三角形。$x,y,d$ 描述了这个三角形。如果 $opt=1$，则接下来还有一个数字 $w$，表示这次修改操作加上的数字。

保证所有输入的三角形均为面积非 $0$，且完全包含在大三角形内部的合法三角形。

输出格式

对于每个 $opt=2$ 的询问，输出一行一个数字，表示区域内总和模 $2^{32}$ 的结果。

提示

本题共 $25$ 组数据。

对于所有数据，$2\le n \le 10^5,1\le q \le 10^5$，$opt \in \{1,2\},type \in \{0,1\}, 1\le x \le n+1,1\le y \le x,1\le d \le n,0\le w < 2^{32}$，保证所有输入的三角形均为面积非 $0$，且完全包含在大三角形内部的合法三角形。