题目描述

小 X 学校的教学楼是一栋 $H$ 层的建筑。学生在同一楼层间可以自由移动，但是只有通过爬楼梯才可以上下楼层。

让我们把教学楼抽象成一个有 $H×M$ 个格子的矩形，学生可以从一个单元格上花费 $1$ 秒移动到上下左右的相邻单元格上。学生在水平方向上的移动是没有限制的（除了不能摔出楼外），但只有在有楼梯相连的时候才能进行竖直移动。一个楼梯会连接同一列中的一段连续楼层，且一列中只会有一个楼梯。

现在有 $T$ 个学生，每个人都希望从一个位置走到另一个位置上。他们想问问小 X 最短需要花费多长时间。

输入格式

第一行 $2$ 个整数 $H$ 和 $M$ 表示教学楼大小。

第二行，$1$ 个整数 $K$ 表示楼梯的数量。

接下来 $K$ 行，每行三个整数 $x,h_1,h_2$ 表示在第 $x$ 列的 $h_1$ 层和 $h_2$ 层之间有楼梯。

接下来 $1$ 行，一个整数 $T$ 表示有 $T$ 个学生。

接下来 $T$ 行，每行四个整数 $s_x,s_y,t_x,t_y$ 表示这个学生想要从$s_x$ 列的 $s_y$ 层走到$t_x$ 列的 $t_y$ 层。

输出格式

对于每一个学生按顺序输出一行一个整数表示最短时间。

如果不可能走到，输出 -1。

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

6
9
-1

样例解释

数据范围

对于全部测试点：

• $1 \leq x \leq M$
• $1 \leq h_1< h_2 \leq H$
• $1 \leq s_x,t_x \leq M，1 \leq s_y,t_y \leq H$
• $1 \leq H,M \leq 10^5$
• $1 \leq K \leq 300$
• $1 \leq T \leq 50000$

​对于编号为奇数的测试点：$T=1$

对于测试点 $1,2$：$K=0$

对于测试点 $3,4$：$K=1$

对于测试点 $5,6$：$H=M=10$

对于测试点 $7\sim10$：$H=M=50$