H. Игра с отрезками
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса и Боб играют в игру (да, опять).

У них есть две последовательности отрезков на числовой прямой: последовательность из $$$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]$$$. В начале игры они выбирают один из начальных отрезков в качестве текущего отрезка.

Алиса и Боб ходят по очереди: Алиса делает первый ход, затем ходит Боб, после него Алиса и т. д. Во время своего хода игрок обязан уменьшить текущий отрезок либо увеличением его левой границы на $$$1$$$, либо уменьшением его правой границы на $$$1$$$. Таким образом, если текущий отрезок $$$[c_l, c_r]$$$, то он превратится либо в $$$[c_l + 1, c_r]$$$, либо в $$$[c_l, c_r - 1]$$$.

Если в начале игры либо после хода Боба текущий отрезок совпадает с одним из конечных отрезков — то Боб выигрывает. Если текущий отрезок стал вырожденным ($$$c_l = c_r$$$), и Боб еще не выиграл — то выигрывает Алиса. Если текущий отрезок совпадает с одним из конечных отрезков после хода Алисы — игра продолжается.

Оба игрока играют оптимально — если игрок может выиграть, то он выберет стратегию, которая позволит ему сделать это за минимальное количество ходов. Если же игрок не может выиграть, то он выберет стратегию, которая продлит игру как можно дольше.

Для каждого начального отрезка вам нужно определить исход игры, если выбрать этот отрезок в качестве текущего отрезка в начале игры. Также, если выигрывает Боб, вам нужно определить, сколько ходов успеет сделать Алиса.

Входные данные

Первая строка содержит два числа $$$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$$$-го начального отрезка:

  • если выигрывает Алиса — выведите $$$-1$$$;
  • если выигрывает Боб — выведите, сколько ходов успеет сделать Алиса.
Примеры
Входные данные
1 1
4 7
4 7
Выходные данные
0
Входные данные
1 2
2 5
2 4
3 5
Выходные данные
-1
Входные данные
2 1
1 5
1 4
2 3
Выходные данные
-1 1