The following languages are only available languages for the problems from the contest

Kotlin Heroes: Episode 4:

- Kotlin 1.4.0

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
H. Game with Segments

time limit per test

3 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputAlice 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

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

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.

Examples

Input

1 1 4 7 4 7

Output

0

Input

1 2 2 5 2 4 3 5

Output

-1

Input

2 1 1 5 1 4 2 3

Output

-1 1

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/23/2021 05:59:13 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|