题目描述

需要维护二维平面上的整点，每个整点 $(x,y)$ 有权值 $V(x,y)$ ，初始为 $0$。

给定 $n$ 次修改操作，每次修改给出 $x_1,x_2,y_1,y_2,v$ ，对每个满足 $x_1\le x\le x_2,\;y_1\le y\le y_2$ 的 $(x,y)$ ，将 $V(x,y)$ 修改为 $\max(V(x,y),v)$ ；

在所有修改操作之后，有 $m$ 次查询操作，每次操作给出 $x_1,x_2,y_1,y_2$ ，查询 $\sum\limits_{x=x_1}^{x_2}\sum\limits_{y=y_1}^{y_2}V(x,y)$ 。

输入格式

第一行两个整数 $n,m$；

接下来 $n$ 行每行 $5$ 个整数 $x_1,x_2,y_1,y_2,v$ ，依次表示每次修改操作；

接下来 $m$ 行每行 $4$ 个整数 $x_1,x_2,y_1,y_2$ ，依次表示每次查询操作。

输出格式

共 $m$ 行，依次表示每次查询操作的答案。

输入输出样例 #1

输入 #1

4 3
2 2 1 4 1
1 2 1 3 1
2 4 3 4 3
2 4 3 4 3
1 1 3 3
2 4 3 3
2 4 3 4

输出 #1

1
9
18

说明/提示

对于 $20\%$ 的数据，满足 $n,m\le 100$。

对于另外 $20\%$ 的数据，满足 $m\le 10$。

对于另外 $20\%$ 的数据，满足 $n,m\le 5\times 10^4$。

对于 $100\%$ 的数据，满足 $1\le n,m\le 2\times 10^5$。

对每个修改或查询操作，满足 $1\le x_1\le x_2\le n$ ， $1\le y_1\le y_2\le n$ 。

对每个修改操作，满足 $1\le v\le n$。

所有数值为整数。