Game with Segments
Contest: Kotlin Heroes: Episode 4
Difficulty rating: 2700
Tags: *special, data structures, games

Alice and Bob are playing a game (yet again).

They have two sequences of segments of the coordinate axis: a sequence of $$$n$$$ initial segments: $$$[l_1, r_1]$$$, $$$[l_2, r_2]$$$, ..., $$$[l_n, r_n]$$$, and a sequence of $$$m$$$ terminal segments: $$$[L_1, R_1]$$$, $$$[L_2, R_2]$$$, ..., $$$[L_m, R_m]$$$. At the beginning of the game, they choose one of the initial segments and set it as the current segment.

Alice and Bob make alternating moves: Alice makes the first move, Bob makes the second move, Alice makes the third one, and so on. During each move, the current player must shrink the current segment either by increasing its left endpoint by $$$1$$$, or by decreasing its right endpoint by $$$1$$$. So, if the current segment is $$$[c_l, c_r]$$$, it becomes either $$$[c_l + 1, c_r]$$$, or $$$[c_l, c_r - 1]$$$.

If at the beginning of the game or after Bob's move the current segment coincides with one of the terminal segments, Bob wins. If the current segment becomes degenerate ($$$c_l = c_r$$$), and Bob hasn't won yet, Alice wins. If the current segment coincides with one of the terminal segments after Alice's move, nothing happens — the game continues.

Both players play optimally — if they can win, they always use a strategy that leads them to victory in the minimum number of turns, and if they cannot win, they try to prolong the game, using the strategy allowing them to make the maximum possible number of moves until their defeat.

For each of the initial segments you have to determine who will win the game if this segment is chosen as the current segment at the beginning of the game. If Bob wins, you also have to calculate the number of moves Alice will make before her defeat.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — the number of initial segments and terminal segments, respectively.

Then $$$n$$$ lines follow, the $$$i$$$-th line contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i < r_i \le 10^6$$$) — the endpoints of the $$$i$$$-th initial segment.

Then $$$m$$$ lines follow, the $$$i$$$-th line contains two integers $$$L_i$$$ and $$$R_i$$$ ($$$1 \le L_i < R_i \le 10^6$$$) — the endpoints of the $$$i$$$-th terminal segment.

Note that some of the segments given in the input may coincide.

Output format:
Print $$$n$$$ integers, the $$$i$$$-th of them should describe the result of the game if the $$$i$$$-th initial segment is chosen at the beginning of the game:

- if Alice wins, print $$$-1$$$;
- if Bob wins, print the number of moves Alice will make before she is defeated.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Example input:
1 1
4 7
4 7

Example output:
0

Example input:
1 2
2 5
2 4
3 5

Example output:
-1

Editorial:
Let's denote the center of segment $$$[l, r]$$$ as $$$\frac{l + r}{2}$$$ (in code it's actually $$$l + r$$$, so that all calculations are integral). If for some initial segment $$$[l_i, r_i]$$$ there exists some terminal segment $$$[L_i, R_i]$$$ with the same center, and $$$R_i - L_i \le r_i - l_i$$$, then Bob can force the game to end in such a segment by using symmetric strategy: if Alice changes the left endpoint, Bob changes the right endpoint, and vice versa. So Bob can end the game in the number of turns equal to the distance to the longest such terminal segment $$$[L_i, R_i]$$$.
Now suppose there is no such segment (or Bob doesn't want to force the game into it, and instead wants to win faster). If there exist two terminal segments $$$[L_j, R_j]$$$ and $$$[L_k, R_k]$$$ such that $$$L_j + R_j = l + r - 2$$$, $$$L_k + R_k = l + r + 2$$$, $$$R_j - L_j \le r - l - 2$$$ and $$$R_k - L_k \le r - l - 2$$$, then Bob can force the game to end up in one of these segments: the first Bob's action should be the same as the first Alice's action, and then he uses symmetrical strategy. If we choose two longest segments $$$[L_j, R_j]$$$ and $$$[L_k, R_k]$$$ meeting these constraints, then Bob can end the game in $$$\dfrac{\max(r - R_j + L_j - l, r - R_k + L_k - l)}{2}$$$ moves.
Note that we only considered segments having center either equal to the center of the initial segment, or different from it exactly by $$$1$$$. It turns out that Bob can't force the game into any other segment since Alice also has a symmetric strategy after the first Bob's turn that allows her to stay near the center of the initial segment. So we only have to consider two aforementioned options.
To find the segments we are interested in, we may group all terminal segments by $$$[L_i + R_i]$$$, sort them by length in each group, and use binary search to find the segment having the biggest length not exceeding some given number.