题目背景

本题的故事发生在巨龙之国，在这里我们将为你介绍一些必要的设定。

巨龙之国幅员辽阔，你可以将其想象成一个 $r$ 行 $c$ 列的网格，每个格点上均有城市坐落。为了方便起见，我们在下面将用坐标 $\left( x,y\right)$ 来指代第 $x$ 行第 $y$ 列的城市。

作为一个现代化的国家，巨龙之国的城际交通工具主要由火车、飞机构成。

• 火车依赖铁路：巨龙之国包含 $r$ 条水平的铁路和 $c$ 条竖直的铁路。

  • 第 $i$ 条水平的铁路（$1\leq i\leq r$）依次连接了第 $i$ 行的各城市。

  • 第 $j$ 条竖直的铁路（$1\leq j\leq c$）依次连接了第 $j$ 列的各城市。

  • 对于每条铁路，每天都有贯穿其的列车运行。但在多条铁路间穿行的列车是不存在的（这意味着如果你需要乘坐火车到达一个横纵坐标均不同于起点的城市，那么你至少需要换乘一次）。

    • 乘坐贯穿第 $i$ 行的列车的单次开销为 $cr_i$；乘坐贯穿第 $j$ 列的列车的单次开销为 $cc_j$。（需要注意的是，乘坐火车的开销与起点、终点无关）

• 飞机依赖机场：巨龙之国有 $a$ 座机场建设在了不同的城市，编号从 $1$ 至 $a$。其中第 $i$ 座机场所在城市为 $\left( ax_i,ay_i\right)$。

  • 任意两座机场之间都有互达的航班。

    • 乘坐任意航班的单次开销均为 $ca$。

题目描述

近日，受恶劣天气影响，巨龙之国的部分机场、铁路受到影响无法正常运行：

• 第 $i$ 座机场自即日起直到第 $da_i$ 天才能恢复正常，在此之前所有涉及该机场的航班均被取消。（特别地，如果 $da_i=0$，那么该机场没有受到影响）

• 同时，还有额外 $m$ 座城市受雷雨影响，第 $i$ 座受到影响的城市（$1\leq i\leq m$）自即日起直到 $dr_i$ 天后才能恢复正常，在此之前，所有途经（包括始发、到达）该城市的铁路均被封锁，相关列车全部停运。

你有 $Q$ 位朋友需要出行。他们每位都会告诉你各自的起点、目的地，你需要告诉他们：

1. 他们最早能在自即日起几天后到达目的地。

2. 在最早到达目的地的前提下，他们的最小花费。

为了方便起见，你可以忽略乘坐、换乘交通工具的时间。这也就意味着，只要存在合法的交通线路组合，你可以在当天内完成移动。

输入格式

• 第一行 $2$ 个正整数 $r,c$。

• 接下来一行 $r$ 个非负整数 $cr_i$。

• 接下来一行 $c$ 个非负整数 $cc_j$。

• 接下来一行 $1$ 个非负整数 $m$。

• 接下来 $m$ 行，每行 $3$ 个非负整数 $x_i,y_i,dr_i$ 描述一个受雷雨影响的城市 $\left(x_i,y_i\right)$。

• 接下来一行 $2$ 个非负整数 $a,ca$。

• 接下来 $a$ 行，每行 $3$ 个非负整数 $ax_i,ay_i,da_i$ 描述一个机场。

• 接下来一行 $1$ 个非负整数 $Q$。

• 接下来 $Q$ 行，每行 $4$ 个整数 $u_x,u_y,v_x,v_y$，描述一个从 $\left(u_x,u_y\right)$ 出发，希望前往 $\left(v_x,v_y\right)$ 的朋友。

对于每一行，若行内包含多个数，则用单个空格将它们隔开。

我们保证所有坐标均合法，不会超出范围。

保证所有 $cr,cc,ca\leq 10^8$。

保证所有 $dr,da\leq 10^9$。

保证 $a,m\leq \min{\left\{r\times c,2\times 10^5\right\}}$。

保证不同机场的坐标两两不同；保证受雷雨影响的城市的坐标两两不同。

输出格式

输出共 $Q$ 行，依次输出每个朋友的答案。

• 每行两个用单个空格隔开的整数，分别表示两个问题的答案。具体问题见【题目描述】。

2 3
1000 2000
3000 4000 5000
2
1 1 20
2 3 30
2 10000
1 2 10
2 3 0
3
1 2 2 2
1 1 2 3
2 1 1 3

0 4000
20 11000
20 4000

对于第 $1$ 个朋友，他可以直接坐竖直行驶的列车到达目的地，开销为 $4000$。

对于第 $2$ 个朋友，他可以等待 $20$ 天，并乘坐火车到达 $\left(1,2\right)$，并换乘飞机直达目的地，开销为 $1000+10000=11000$。

对于第 $3$ 个朋友，虽然他所在的城市风平浪静，但其他城市受雷雨影响，导致铁路系统瘫痪，他必须等到第 $20$ 天才能开始行动。

子任务

评分

本题将使用 Special Judge 实现如下评分规则。

在任意一个子任务中：

• 如果你正确地作答了所有的第一个问题，则你将获得这个子任务 $60\%$ 的分数；

• 在上面的基础上，如果你正确地作答了所有的第二个问题，则你将获得这个子任务的剩余 $40\%$ 的分数。

需要注意的是，如果存在被错误作答的第一个问题，那么即便你正确作答了所有的第二个问题，仍将无法获得对应子任务的分数。

同时，需要提醒你的是，即使你只希望获得第一部分的分数，你也需要保证输出格式的合法性。即如果你在每行仅输出了第一个问题的答案，那么即使它们都是正确的，你也将可能无法获得对应的分数。