#P17905. Triangle Grid

Triangle Grid

把一个边长为 nn 的正三角形按单位长度划分成三角网格,其中有 n2n^2 个边长为 11 的小三角形。每个小三角形内有一个数,初始均为 00。

网格顶点按行编号:最上方是第 11 行,底边是第 n+1n+1 行。第 xx 行有 xx 个顶点,从左到右编号 y=1,…,xy=1,\ldots,x,记作 (x,y)(x,y)。

一次操作的区域是沿网格线的等边三角形,用 type,x,y,d 指定,dd 是边长:

  • type=0:朝上,三个顶点是 (x,y),(x+d,y),(x+d,y+d)(x,y),(x+d,y),(x+d,y+d);
  • type=1:朝下,三个顶点是 (x,y),(x−d,y−d),(x−d,y)(x,y),(x-d,y-d),(x-d,y)。

因此,(x,y)(x,y) 始终是与水平底边相对的尖顶。区域包含其中所有完整的单位小三角形,两种朝向的小三角形都计入。

支持两种操作:opt=1 给区域内每个小三角形的数加上 ww;opt=2 求区域内所有数的和。每次查询仅受之前的修改影响。

输入格式

第一行给出 n,qn,q,2≤n≤1052\le n\le10^5,1≤q≤1051\le q\le10^5。

接下来 qq 行,每行先给出 opt type x y d。若 opt=1,再给出 ww。

其中 opt∈{1,2}\mathrm{opt}\in\{1,2\},type∈{0,1}\mathrm{type}\in\{0,1\},1≤x≤n+11\le x\le n+1,1≤y≤x1\le y\le x,1≤d≤n1\le d\le n,0≤w<2320\le w<2^{32}。

保证每个指定三角形完整位于大三角形内。等价地,朝上时 x+d≤n+1x+d\le n+1;朝下时 y−d≥1y-d\ge1 且 y≤x−dy\le x-d。

输出格式

每次查询输出一行整数,为区域和对 232=42949672962^{32}=4294967296 取模后的非负余数。

样例 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

输出

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

输出

0
2
12
0