#P18017. Kitchen

Kitchen

Kitchen

Petya 的厨房里有 nn 只蟑螂。他在厨房里放了 mm 份有毒诱饵,希望知道各只蟑螂何时死亡。

厨房是宽 WW、高 HH 的矩形,坐标范围为 [0,W]×[0,H][0,W]\times[0,H]。每只蟑螂的速度都是每秒 11 米。它从 (x1,y1)(x_1,y_1) 前往 (x2,y2)(x_2,y_2) 时,必须先沿水平方向到达 (x2,y1)(x_2,y_1),再沿竖直方向到达 (x2,y2)(x_2,y_2)。

每只蟑螂选择到达时间最短的剩余诱饵作为目标;若有多个,选择坐标 (x,y)(x,y) 字典序最小的诱饵,即先比较 xx,相同再比较 yy。到达诱饵时,它立即将整份诱饵吃掉。原本奔向这份诱饵的其他蟑螂立即按上述规则,从当前位置重新选择目标并前进。

若多只蟑螂同时到达同一份诱饵,初始坐标在输入中出现较早的蟑螂吃到它。

一只蟑螂吃到少于 aa 份诱饵时不会因中毒而死。它吃到第 aa 份诱饵后,还能继续活动 tt 秒,然后死亡。如果恰好在死亡时刻到达一份诱饵,它仍然来得及将其吃掉。之后继续吃到诱饵不会延后已经确定的死亡时刻。

请输出每只蟑螂从初始时刻起经过多少秒死亡;若它最终存活,则输出 −1-1。

输入格式

第一行四个整数 n,m,a,tn,m,a,t。第二行两个整数 W,HW,H。

接下来 nn 行,每行两个整数 x,yx,y,按顺序描述各只蟑螂的初始坐标。蟑螂初始坐标可以相同。

再接下来 mm 行,每行两个整数 x,yx,y,描述一份诱饵的位置。诱饵位置两两不同,允许与蟑螂初始位置重合。

输出格式

输出 nn 行,按蟑螂输入顺序输出死亡时刻,或者表示存活的 -1。

数据范围

1≤n≤1001\le n\le100,1≤m≤10001\le m\le1000,1≤a≤10001\le a\le1000,0≤t≤1090\le t\le10^9,1≤W,H≤1091\le W,H\le10^9。所有坐标均为整数且满足 0≤x≤W0\le x\le W、0≤y≤H0\le y\le H。

样例 1

输入

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

输出

-1
9
4