该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

B 地区在地震过后，所有公路都造成了一定的损毁，而这场地震却没对村庄造成什么影响。当地部门正在对公路进行重建。

题目描述

B 地区共有 N 个村庄，编号从 1 到 N。有 M 条双向通行的公路将所有村庄连通起来。每条公路都连接两个不同的村庄（无自环），两个不同的村庄之间最多有一条公路（无重边）。任意两个村庄之间有且仅有一条通路。

所有的公路都是南北或东西方向的。不存在两条中途相交的公路。

地震后，小 A 作为重建公路的负责人，计划在接下来的 M 天内，每天修建一条公路，一共 M 天完成该项工程。

小 C 询问了小 A 一些奇怪的问题。小 A 正在忙着修路，于是把这些问题交给了你。

你能帮助小 A 吗？

输入格式

第一行包含两个整数 $N, M$，依次表示村庄的数目、公路的数目。

接下来 $M$ 行，按顺序依次给出了每天需要修建的公路信息：每行 $4$ 个整数 $u, v, w, d$，表示村庄 $u$ 的 $d$ 方向有一个村庄 $v$，中间有一条长度为 $w$ 的公路需要在该天修建，保证 $u \neq v$。$d$ 只可能为 1 2 3 4 中的一个数字，分别表示 东 西 南 北 方向。

接下来一行一个整数 K，表示询问的个数。

接下来 $K$ 行，每行三个整数 $u, v, t$ ，表示在第 $t$ 天结束后，村庄 $u$ 和 $v$ 之间的曼哈顿距离是多少？

输出格式

$K$ 行，每行一个整数，依次表示每个问题的答案：如果询问的 $u$ 和 $v$ 在第 $t$ 天结束后连通了，则输出二者之间的曼哈顿距离，如果二者当时仍未连通，则在对应行输出 -1。

样例输入

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

样例输出

3
6
-1

数据范围

100% 的数据： $2 ≤ N, M ≤ 4 × 10^4$， $1 ≤ u, v ≤ N$， $1 ≤ w ≤ 10^3$， $1 ≤ K ≤ 10^4$