#P18113. Flight of the Night Butterfly

Flight of the Night Butterfly

Flight of the Night Butterfly

标准输入输出。

你要引导一只夜蝶穿过黑暗。它从六条射线状轨道的公共中心出发,轨道按顺时针编号为0到5。轨道0是主轨道,其余五条是辅助轨道。

轨道只有部分区间被照亮。主轨道有一组照明区间,五条辅助轨道共用另一组照明区间。所有照明区间都是闭区间,端点表示到中心的距离。

飞行开始前,你选择一个正实数速度 dd,之后速度保持不变。夜蝶在时刻0位于中心。在每个正整数时刻 tt,它位于编号为 t mod 6t\bmod6 的轨道上,与中心的距离为 tdtd。因此访问轨道的次序为1、2、3、4、5、0、1、2、……。

给出 qq 个相互独立的询问。每次询问给定目标距离 TT,你希望夜蝶在某个时刻 kk 到达主轨道上距离中心为 TT 的位置。因此 kk 必须是6的正整数倍,且 kd=Tkd=T。

在每个整数时刻 1,2,…,k1,2,\ldots,k,夜蝶必须位于当前轨道的照明区间中,否则就会迷失。其他时刻没有任何限制,包括时刻0。

对每次询问,求能安全到达目标的最早时刻 kk;若不能到达,输出 −1-1。每次询问可以独立选择速度 dd。

输入格式

第一行两个整数 n,mn,m,分别表示主轨道和辅助轨道的照明区间数。

接下来 nn 行,每行两个整数 l,rl,r,表示主轨道上的一个照明区间 [l,r][l,r]。

接下来 mm 行,每行两个整数 l,rl,r,表示所有辅助轨道共用的一个照明区间 [l,r][l,r]。

在各自的一组中,区间两两不相交,并按左端点递增排列。特别地,相邻区间满足 li+1>ril_{i+1}>r_i。

接下来一行一个整数 qq。随后 qq 行,每行一个整数 TT,表示一次询问的目标距离。

数据范围:

  • 1≤n,m≤501\le n,m\le50;
  • 1≤l≤r≤10181\le l\le r\le10^{18};
  • 1≤q≤1001\le q\le100;
  • 1≤T≤10181\le T\le10^{18}。

注意:虽然区间端点是整数,夜蝶经过的距离可以是非整数。因此 [1,2][1,2] 与 [3,4][3,4] 之间仍有未被照亮的实数距离。

输出格式

输出 qq 行,每行一个整数,表示最早到达时刻,或 −1-1。

样例

2 2
6 6
12 12
1 5
7 11
3
6
12
18
6
12
-1

当 T=6T=6 时,取 d=1d=1,前五个整数时刻均在辅助轨道的 [1,5][1,5] 内,时刻6到达主轨道的距离6。

当 T=12T=12 时仍可取 d=1d=1,在时刻12到达。若试图取 d=2d=2 在时刻6到达,时刻3会落在辅助轨道距离6的位置,而该位置没有照明。

当 T=18T=18 时,目标不在主轨道的任何照明区间内,因此无解。