一进入厨房，Petya 就发现了一个可怕的惊喜：厨房里到处都是蟑螂！

他一刻也不耽误，在好几个地方放置了毒饵以消灭它们。由于他行色匆匆，有些蟑螂可能会幸存下来。请帮助他预测结果。

根据它们长方形的身体形状，Petya 能够确定这些蟑螂属于一种罕见的曼哈顿蟑螂。如果这样的一只蟑螂从点 $(x_1, y_1)$ 跑到点 $(x_2, y_2)$，它会先沿直线跑到点 $(x_2, y_1)$，然后再从那里沿直线跑到 $(x_2, y_2)$。

每只蟑螂都会选择能使其移动时间最短的毒饵（如果存在多个这样的毒饵，它会选择坐标 $(x_j, y_j)$ 字典序最小的那一个），并以每秒 1 米的速度向其移动。当一只蟑螂到达毒饵时，它会立即将其完全吃掉，随后所有原本正朝该毒饵移动的蟑螂都会根据上述算法重新选择它们的目标。如果多只蟑螂同时到达同一个毒饵，在激烈的种内竞争中，其原始坐标在输入数据中较早出现的那只蟑螂会吃掉它。

由于这些蟑螂具有极强的生命力，如果它们吃掉的毒饵少于 $a$ 个，它们就能存活下来；而一旦吃掉该数量或更多的毒饵，它们在死亡前还能保持活动 $t$ 秒。如果一只蟑螂恰好在它死亡的瞬间到达某个毒饵，它仍然有时间吃掉它。

输入格式

第一行包含四个整数 $n, m, a, t$（$1 \le n \le 100$，$1 \le m \le 1000$，$1 \le a \le 1000$，$0 \le t \le 10^9$），表示有 $n$ 只蟑螂和 $m$ 个毒饵；在吃掉 $a$ 个毒饵后，蟑螂将在 $t$ 秒后死亡。

第二行包含两个整数 $W$ 和 $H$（$1 \le W, H \le 10^9$）：Petya 的矩形厨房的尺寸（单位：米）。

接下来的 $n$ 行，每行包含两个整数 $x, y$（$0 \le x \le W$，$0 \le y \le H$）：表示一只蟑螂的初始坐标。

接下来的 $m$ 行，每行包含两个整数 $x, y$（$0 \le x \le W$，$0 \le y \le H$）：表示一个毒饵的坐标。保证没有两个毒饵位于同一个点。

输出格式

对于每只蟑螂，在单独的一行中输出一个整数：它在多少秒后会因毒药而死；如果该蟑螂存活，则输出 -1。蟑螂的答案顺序应与输入数据中蟑螂坐标出现的顺序相同。

样例

输入样例 1

3 3 1 2
4 4
0 0
0 1
1 1
2 2
3 3
4 4

输出样例 1

-1
9
4

说明

如果 $x_1 < x_2$，或者 $x_1 = x_2$ 且 $y_1 < y_2$，则称坐标 $(x_1, y_1)$ 的字典序小于坐标 $(x_2, y_2)$。