#P18017. Kitchen
Kitchen
Kitchen
Petya 的厨房里有 只蟑螂。他在厨房里放了 份有毒诱饵,希望知道各只蟑螂何时死亡。
厨房是宽 、高 的矩形,坐标范围为 。每只蟑螂的速度都是每秒 米。它从 前往 时,必须先沿水平方向到达 ,再沿竖直方向到达 。
每只蟑螂选择到达时间最短的剩余诱饵作为目标;若有多个,选择坐标 字典序最小的诱饵,即先比较 ,相同再比较 。到达诱饵时,它立即将整份诱饵吃掉。原本奔向这份诱饵的其他蟑螂立即按上述规则,从当前位置重新选择目标并前进。
若多只蟑螂同时到达同一份诱饵,初始坐标在输入中出现较早的蟑螂吃到它。
一只蟑螂吃到少于 份诱饵时不会因中毒而死。它吃到第 份诱饵后,还能继续活动 秒,然后死亡。如果恰好在死亡时刻到达一份诱饵,它仍然来得及将其吃掉。之后继续吃到诱饵不会延后已经确定的死亡时刻。
请输出每只蟑螂从初始时刻起经过多少秒死亡;若它最终存活,则输出 。
输入格式
第一行四个整数 。第二行两个整数 。
接下来 行,每行两个整数 ,按顺序描述各只蟑螂的初始坐标。蟑螂初始坐标可以相同。
再接下来 行,每行两个整数 ,描述一份诱饵的位置。诱饵位置两两不同,允许与蟑螂初始位置重合。
输出格式
输出 行,按蟑螂输入顺序输出死亡时刻,或者表示存活的 -1。
数据范围
,,,,。所有坐标均为整数且满足 、。
样例 1
输入
3 3 1 2
4 4
0 0
0 1
1 1
2 2
3 3
4 4
输出
-1
9
4