背景

    出于保护鱼类的目的,最优秀的渔翁才能在洞庭湖继续捕鱼。经过层层选拔,洞庭湖上只剩下孤舟蓑笠翁。以前跟其他渔翁一起钓鱼、打牌、切磋武艺,而如今只剩孤单一人,蓑笠翁不禁黯然神伤。选拔被淘汰,如今他们都去哪里了呢?大概回家种田养猪了吧。

描述

    蓑笠翁现在闲暇时在练的武术名为"左右互搏术",相传是周伯通首创的武功。

    练功时,蓑笠翁的双手在某竖直平面内运动,以该平面上某点作为坐标原点,向右为x轴正方向,向上为y轴正方向建立直角坐标系。那么该平面内的一个点就可以用坐标(x, y)来表示。
    该武功有n个可停顿点,分别为p_1 = (x_1, y_1), p_2 = (x_2, y_2), \cdots, p_n = (x_n, y_n)。我们可以将蓑笠翁练功的过程分成一秒一秒来看,第i秒时,双手都处于可停顿点上。而第i秒末双手进行移动,移动到其它可停顿点上。(当然也可以不移动)
    左右互搏术中,有k种绝招。第i种绝招为:左手处于v_i号可停顿点,右手处于u_i号可停顿点,则可以发动绝招。
    练武功也有禁忌,在两只手停顿的时候,如果两只手的曼哈顿距离小于d_{min},则容易走火入魔。如果两只手的曼哈顿距离大于d_{max},则蓑笠翁的胳膊显然快被扯断了。所以假设左手在l号停顿点,右手在r号停顿点,则需要满足d_{min} \leq |x_l - x_r| + |y_l - y_r| \leq d_{max}
    从一个停顿点移动到另一个停顿点也有讲究,而且对于左右手还不一样。有m个移动条件,每个移动条件形如:左手在a号停顿点时能移动到b号停顿点且在b号停顿点时也能移动到a号停顿点,或右手在a号停顿点时能移动到b号停顿点且在b号停顿点时也能移动到a号停顿点。对于某一秒末,蓑笠翁的手没那么快,所以每只手至多只能进行移动一次。上面未提到的移动方式均为非法。

    蓑笠翁希望能发动连击。即先发动第i种绝招,经过t秒的移动后,又发动了第j种绝招,且i \neq j
    给出p_1, \cdots, p_nv_1, \cdots v_k, u_1, \cdots, u_kd_{min}d_{max},和m个移动条件,现在蓑笠翁想知道,发动第i种绝招之后,最少经过多少秒的移动后能发动某个编号不为i的绝招,即发动连击的最短耗时。请对于每个1 \leq i \leq k输出答案。

输入格式

第一行两个正整数n,m。
第二行两个非负整数d_{min}, d_{max}。保证d_{min} \leq d_{max}
接下来n行,这n行中的第i行每行两个正整数x,y表示i号停顿点的坐标。
接下来的一行一个正整数k。
接下来k行,这k行中的第i行每行两个正整数v,u表示i号绝招。保证1 \leq v, u \leq n,不会有两个绝招完全相同,保证v,u的曼哈顿距离不小于d_{min}不大于d_{max}
接下来m行,每行三个正整数a,b,type,若type=0则表示左手在a号停顿点时能移动到b号停顿点且在b号停顿点时也能移动到a号停顿点,若type=1则表示右手在a号停顿点时能移动到b号停顿点且在b号停顿点时也能移动到a号停顿点。保证1 \leq a, b \leq n,type \in \{0, 1\}

输出格式

k行,第i行表示第i个绝招发动一次连击的最短耗时。
如果无论如何都无法连击,请输出-1。

样例输入

更多样例请参考pdf
5 5
1 6
3 2
9 2
7 3
7 8
4 9
3
5 4
1 3
1 2
1 2 0
2 5 0
1 5 1
1 3 1
3 4 1

样例输出

2
2
-1

样例解释

对于绝招1,可以先将左手移动到2号可停顿点,右手移动到3号可停顿点,再将左手移动到1号可停顿点,这样可以发动绝招2,共用时2秒。对于绝招2可以把刚才的过程反过来,发动绝招1。对于绝招3,无论如何右手都无法移动,不能发动任何绝招,故输出-1。

数据范围与约定

其中20%的数据,n \leq 50, m \leq 100, k \leq 100
另有30%的数据,n \leq 500, m \leq 2000,k \leq 10000, d_{min} = 0, d_{max} = 10000
对于100%的数据,n \leq 1000, m \leq 4000, 1 \leq x_i, y_i \leq 1000, 0 \leq d_{min} \leq d_{max} \leq 10^9

来源

VFleaKing