时间限制： 5.0 秒 1.0 秒~5.0 秒

空间限制： 1024 MB

题目背景

ReLU 函数是机器学习中常用的一个激活函数，其定义为：$\mathrm{ReLU}(x)=\max(0,x)$。

题目描述

在西西艾弗岛上有一台基于哥德尔机原理设计的通用人工智能机器，小 C 是负责维修这台机器的机器人。

有一天小 C 发现这个机器在一个算法部分上遇到了计算瓶颈，这个算法是这样的：

机器内部维护了一个神经网络，这个神经网络的权重是一个二维矩阵 $V$，并且权重是一个整数。

即对于每个二维坐标 $(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)$ 修改为 $v + \mathrm{ReLU}(V(x,y) - v)$；

在所有学习操作之后，神经网络的参数定下来不变了，紧接着有 $m$ 次神经网络推理操作，每次推理操作给出 $x_1,x_2,y_1,y_2$，查询对应子矩阵范围内最大的神经网络权重，即 $\max\limits_{\scriptsize\begin{matrix}x_1\le x\le x_2\\y_1\le y\le y_2\end{matrix}}V(x,y)$。

小 C 发现机器在枚举这个问题优秀的算法时卡住了，目前只枚举出了一个很暴力的算法，为了让机器可以快点启动，他决定自己写好这个问题的算法来降低其启动常数，你能帮帮他吗？

输入格式

从标准输入读入数据。

输入的第一行包含两个整数 $n,m$；

接下来 $n$ 行每行五个整数 $x_1,x_2,y_1,y_2,v$，依次表示每次学习操作的参数；

接下来 $m$ 行每行四个整数 $x_1,x_2,y_1,y_2$，依次表示每次推理操作的参数。

输出格式

输出到标准输出。

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

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

4
4
4
4
4

10 10
3 10 7 7 10
1 10 9 9 3
4 6 7 7 7
1 8 5 5 1
6 8 1 1 1
1 3 8 8 2
2 10 10 10 9
1 10 6 6 4
1 8 9 9 4
5 9 9 9 2
1 9 2 2
2 10 1 10
2 10 6 9
2 2 1 4
2 10 8 10
7 10 1 10
1 8 1 9
1 8 5 7
3 7 5 8
2 10 1 7

0
10
10
0
9
10
10
10
10
10

子任务

对于全部数据，满足：

• $1\le n,m\le 5\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$；
• 所有数值为整数。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

提示

本题输入量较大，请采用效率较高的读入方式。

本题对于同时间复杂度下的常数优化也有一定考察，请保证你的时间常数是比较优秀的。此外，由于评测 I/O 量较大，常数较大的做法可能会在评测时间结果上产生波动，请不要频繁提交，从而得到相对准确的评测结果。