美团打车是美团的一项重要业务，在努力为用户提供便捷出行服务选择的同时，也希望能充分利用平台的力量，为司机带来更多的价值。
    众所周知，大城市上班族的出行会造成几个特定时间点的高峰期，比如早高峰和晚高峰。通常在两个高峰期之间，用户的出行需求会较少，司机会选择在一些合适的地点等待下一单生意。美团希望能够利用大数据的力量辅助司机决策，计算在哪个地点等待能够使得到用户上车地点的期望时间最短。
    经过抽象和简化，我们认为一块区域能够被描述成n行m列的马路，这些马路每行每列都会交叉。如果我们把它抽象成一个平面直角坐标系，东西方向的马路可以看做y=y1, y=y2, ..., y=yn这样的直线，南北方向的马路可以看做x=x1, x=x2, ..., x=xm这样的直线。
    经过美团大数据统计，用户可能的上车地点共有k个，第i个地点坐标为(ai, bi)。这些地点的位置都在路边上，也就是说它的横坐标会和某条南北向的马路的坐标相同或者说纵坐标会和某条东西向的马路坐标相同。当然也有可能两个都相同，也就是说这个地点的位置在某个路口。根据历史数据统计，每个上车地点有不同的权重ci，简单来说，就是下一单出现在第i个地点的概率为ci/(c1+c2+…+ck)。
    当一个用户订单出现的时候，司机会在马路上沿着最短路径尽快赶往上车地点。我们希望能找到一个合适的位置（必须在路边或路口），使得该位置到用户下一次上车地点的期望时间最短。
    同时我们还希望对每个司机，我们能快速地回答这个位置到下一次上车地点的期望时间，我们会给出q个询问。

第一行三个整数n, m, k(1≤n, m, k≤100,000)。第二行包含n个整数y1, y2, ..., yn(0≤y1<y2<...<yn≤1,000,000)。第三行包含m个正整数x1, x2, ..., xn(0≤x1<x2<...<xm≤1,000,000)。接下来k行，每行包含3个整数ai, bi, ci (0≤ai,bi,ci≤1,000,000)，保证ci之和大于0。
接下来一行一个整数q(0≤q≤100,000)，接下来q每行两个整数ui,vi(0≤ui,vi≤1,000,000)，表示一个司机所在的位置，保证司机和用户的位置都在路边或者路口。

为了保证是整数，我们把期望的时间乘上ci的总和。
第一行输出最短的期望时间乘以ci之和。接下来q行，表示q个司机的位置所需要的期望时间乘上ci之和。

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

7
10
8

最合适位置是(4,4)这个点

3 3 3
2 4 6
2 4 6
2 3 1
4 5 100
5 2 1
0

8

最合适位置是(4,5)这个点