#P18113. Flight of the Night Butterfly
Flight of the Night Butterfly
Flight of the Night Butterfly
标准输入输出。
你要引导一只夜蝶穿过黑暗。它从六条射线状轨道的公共中心出发,轨道按顺时针编号为0到5。轨道0是主轨道,其余五条是辅助轨道。
轨道只有部分区间被照亮。主轨道有一组照明区间,五条辅助轨道共用另一组照明区间。所有照明区间都是闭区间,端点表示到中心的距离。
飞行开始前,你选择一个正实数速度 ,之后速度保持不变。夜蝶在时刻0位于中心。在每个正整数时刻 ,它位于编号为 的轨道上,与中心的距离为 。因此访问轨道的次序为1、2、3、4、5、0、1、2、……。
给出 个相互独立的询问。每次询问给定目标距离 ,你希望夜蝶在某个时刻 到达主轨道上距离中心为 的位置。因此 必须是6的正整数倍,且 。
在每个整数时刻 ,夜蝶必须位于当前轨道的照明区间中,否则就会迷失。其他时刻没有任何限制,包括时刻0。
对每次询问,求能安全到达目标的最早时刻 ;若不能到达,输出 。每次询问可以独立选择速度 。
输入格式
第一行两个整数 ,分别表示主轨道和辅助轨道的照明区间数。
接下来 行,每行两个整数 ,表示主轨道上的一个照明区间 。
接下来 行,每行两个整数 ,表示所有辅助轨道共用的一个照明区间 。
在各自的一组中,区间两两不相交,并按左端点递增排列。特别地,相邻区间满足 。
接下来一行一个整数 。随后 行,每行一个整数 ,表示一次询问的目标距离。
数据范围:
- ;
- ;
- ;
- 。
注意:虽然区间端点是整数,夜蝶经过的距离可以是非整数。因此 与 之间仍有未被照亮的实数距离。
输出格式
输出 行,每行一个整数,表示最早到达时刻,或 。
样例
2 2
6 6
12 12
1 5
7 11
3
6
12
18
6
12
-1
当 时,取 ,前五个整数时刻均在辅助轨道的 内,时刻6到达主轨道的距离6。
当 时仍可取 ,在时刻12到达。若试图取 在时刻6到达,时刻3会落在辅助轨道距离6的位置,而该位置没有照明。
当 时,目标不在主轨道的任何照明区间内,因此无解。