CF1346H.Game with Segments

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] $。

如果在游戏开始时或 Bob 操作之后，当前线段与某个终止线段重合，Bob 就赢了。如果当前线段退化为单点（即 $ c_l = c_r $），而 Bob 还没有赢，则 Alice 获胜。如果 Alice 操作后当前线段重合于某个终止线段，游戏继续进行。

两位玩家都以最优方式进行游戏——如果有胜算，他们会采取能在最短回合内取胜的策略；如果无法获胜，他们会尽可能延长游戏时间，通过最大化操作次数来延迟失败。

对于每个初始线段，你需要判断如果选择该线段作为起始线段，最后谁会胜出。如果是 Bob 获胜，还需计算 Alice 在失败前进行的操作次数。

第一行输入两个整数 $ n $ 和 $ m $（$ 1 \le n, m \le 2 \cdot 10^5 $），分别表示初始线段和终止线段的数量。

接下来有 $ n $ 行，每行两个整数 $ l_i $ 和 $ r_i $（$ 1 \le l_i < r_i \le 10^6 $），表示第 $ i $ 个初始线段的两个端点。

紧接着是 $ m $ 行，每行两个整数 $ L_i $ 和 $ R_i $（$ 1 \le L_i < R_i \le 10^6 $），表示第 $ i $ 个终止线段的两个端点。

请注意，输入中可能会有重复的线段。

输出 $ n $ 个整数，第 $ i $ 个整数表示如果选则第 $ i $ 个初始线段开始游戏的结果：

• 如果 Alice 胜出，输出 -1；
• 如果 Bob 胜出，输出 Alice 在败北前的操作次数。

本翻译由 AI 自动生成