Alice 和 Bob 正在玩游戏(再次)。
它们有两个坐标轴线段序列:$$$n$$$ 初始线段序列:$$$[l_1, r_1]$$$、$$$[l_2, r_2]$$$, ..., $$$[l_n, r_n]$$$ 和 $$$m$$$ 终端线段序列:$$$[L_1, R_1]$$$, $$$[L_2,R_2]$$$,...,$$$[L_m,R_m]$$$。在游戏开始时,他们选择一个初始片段并将其设置为当前片段。
Alice 和 Bob 交替着棋:Alice 迈出第一步,Bob 迈出第二步,Alice 迈出第三步,以此类推。在每次移动过程中,当前玩家必须通过将其左端点增加 $$$1$$$ 或将其右端点减少 $$$1$$$ 来缩小当前段。因此,如果当前段是 $$$[c_l, c_r]$$$,则它会变为 $$$[c_l + 1, c_r]$$$ 或 $$$[c_l, c_r - 1]$$$。
如果在游戏开始时或鲍勃移动之后当前片段与终止片段之一重合,则鲍勃获胜。如果当前段变得退化($$$c_l = c_r$$$),并且 Bob 尚未获胜,则 Alice 获胜。如果当前片段与爱丽丝移动后的终止片段之一重合,则不会发生任何事情 - 游戏继续。
两名玩家都处于最佳状态——如果他们能赢,他们总是使用一种策略,让他们在最少的回合内获胜,如果他们不能赢,他们会尝试延长游戏,使用允许他们进行尽可能多的移动的策略,直到失败。
对于每个初始分段,如果在游戏开始时选择该分段作为当前分段,您必须确定谁将赢得游戏。如果鲍勃获胜,您还必须计算爱丽丝在失败之前将采取的步数。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — 分别是初始段和终止段的数量。
接下来是 $$$n$$$ 行,第 $$$i$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i < r_i \le 10^6$$$) — 第 $$$i$$$ 初始段的端点。
接下来是 $$$m$$$ 行,第 $$$i$$$ 行包含两个整数 $$$L_i$$$ 和 $$$R_i$$$ ($$$1 \le L_i < R_i \le 10^6$$$) — 第 $$$i$$$ 终端段的端点。
请注意,输入中给出的某些段可能会重合。
输出
打印 $$$n$$$ 个整数,如果在游戏开始时选择第 $$$i$$$ 个初始段,则其中第 $$$i$$$ 应该描述游戏的结果:
- 如果 Alice 获胜,则打印 $$$-1$$$;
- 如果鲍勃获胜,则打印爱丽丝在被击败之前将进行的步数。
示例
输入 #1
1 1 4 7 4 7
输出 #1
0
输入 #2
1 2 2 5 2 4 3 5
输出 #2
-1
输入 #3
2 1 1 5 1 4 2 3
输出 #3
-1 1