UOJ Logo Universal Online Judge

UOJ

#910. 【CTS2022】回

附件下载 统计

你需要维护平面上的整点,每个点初始有点权 0,共 m 次操作。

修改操作:给定 x,y,d,w,将满足 |Xx|<d,|Yy|<d 的整点 (X,Y) 的点权增加 w(dmax(|Xx|,|Yy|))

查询操作:给定 x1,x2,y1,y2,查询满足 x1Xx2,y1Yy2 的整点 (X,Y) 的点权之和,答案对 230 取模。

输入格式

从标准输入读入数据。

第一行一个整数 m,接下来 m 行,每行表示一个操作。

修改操作表示为 1 x y d w

查询操作表示为 2 x1 x2 y1 y2

输出格式

输出到标准输出。

对每个查询操作,输出一行,包含一个整数,表示取模后的答案。

样例 1

input

5
1 3 4 5 1
2 1 4 3 5
1 2 4 2 2
2 4 5 3 5
1 4 4 4 8

output

46
21

子任务

对于 23% 的数据,满足 1m103

对于 31% 的数据,满足 1m2×104

对于 39% 的数据,满足 1m4×104

对于 47% 的数据,满足 1m6×104

对于 55% 的数据,满足 1m8×104

对于另外 15% 的数据,满足对任意询问操作,不存在一个修改操作,该修改操作在该询问操作之后。

对于另外 10% 的数据,满足 x2x15y2y15d5

对于另外 10% 的数据,满足 d5

对于 100% 的数据,满足 1m1051x1x21081y1y21081x,y,d,w108

每类数据构成子任务。

时间限制:10s 12s

空间限制:512MB