题目描述

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

让我们把教学楼抽象成一个有$H\times 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

数据范围与提示

本题共有$15$个测试点，每个测试点$10$分。

对于全部测试点:$1\leq x\leq M$且所有$x$各不相同。

$1\leq h1<h2\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−10$:$H=M=50$

对于测试点$11−15$:没有特殊限制