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

У них есть две последовательности отрезков на числовой прямой: последовательность из $$$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$$$), и Боб еще не выиграл — то выигрывает Алиса. Если текущий отрезок совпадает с одним из конечных отрезков после хода Алисы — игра продолжается.

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

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