题目背景

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

题目描述

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

练功时，蓑笠翁的双手在某竖直平面内运动，以改平面上某点作为坐标原点，向右为 $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}\le |x_l-x_r|+|y_l-y_r|\le d_{max}$。

从一个停顿点移动到另一个停顿点也有讲究，而且对于左右手还不一样。有 $m$ 个移动条件，每个移动条件形如：左手在 $a$ 号停顿点时能移动到 $b$ 号停顿点且在 $b$ 号停顿点时也能移动到 $a$ 号停顿点，或右手在 $a$ 号停顿点时能移动到 $b$ 号停顿点且在 $b$ 号停顿点时也能移动到 $a$ 号停顿点。对于某一秒末，袭笠翁的手没那么快，所以每只手至多只能进行移动一次。上面未提到的移动方式均为非法。

蓑笠翁希望能发动连击。即先发动第 $i$ 种绝招，经过 $t$ 秒的移动后，又发动了第 $j$ 种绝招，且 $i\neq j$。

给出 $p_1,\cdots,p_n$，$v_1,\cdots,v_k,u_1,\cdots,u_k$，$d_{min},d_{max}$，和 $m$ 个移动条件，现在 蓑笠翁想知道，发动第 $i$ 种绝招之后，最少经过多少秒的移动后能发动某个编号不为 $i$ 的绝招，即发动连击的最短耗时。请对于每个 $1\le i\le 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$ 号绝招。左手处于 $v$ 号可停顿点，右手处于 $u$ 号可停顿点时能发动该绝招。保证 $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\}$。

样例输入#1

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

样例输出#1

2
2
-1

样例说明#1

对于绝招 $1$，可以先同时将左手移动到 $2$ 号可停顿点，右手移动到 $3$ 号可停顿点，这样耗时 $1 \textrm{s}$，再将左手移动到 $1$ 号可停顿点，右手不动，这样可以发动绝招 $2$，共用时 $2 \textrm{s}$。对于绝招 $2$ 可以把刚才的过程反过来，发动绝招 $1$。对于绝招 $3$，无论如何右手都无法移动，不能发动任何绝招，故输出 $−1$。

样例输入#2

6 14
2 7
3 10
8 9
3 4
6 5
3 10
6 7
4
6 2
1 2
5 2
3 6
5 2 0
4 5 1
2 3 1
5 4 0
1 2 1
1 4 0
6 4 1
5 4 1
4 6 0
1 5 0
4 1 0
6 4 0
5 5 0
1 2 0

样例输出#2

2
1
1
-1

样例说明#2

不解释。

数据规模与约定

其中 $20 \%$ 的数据，$n \leq 50,m \leq 100,k \leq 100$。

另有 $30 \%$ 的数据，$n \leq 500,m \leq 2\times10^3,k \leq 10^4,d_{min}=0,d_{max}=10^4$。

对于 $100 \%$ 的数据，$n \leq 10^3,m \leq 4\times10^3,1\le x_i,y_i\le 10^3,0\le d_{min}\le d_{max} \le 10^9$。

题目来源

2013湖北互测week1