Задача . D. Скалолазание

Эта задача никак не связана с маленьким Крисом. Здесь надо лазать по скалам (это в круг интересов Криса уж точно не входит).

В ряд расположены n гор, каждая из которых имеет форму вертикального отрезка, один конец которого находится на земле. Горы пронумерованы слева направо целыми числами от 1 до n. Гора под номером i находится в точке x_i, а ее вершина — на высоте y_i. Для каждых двух гор a и b, если вершину горы a можно видеть с вершины горы b, их вершины связаны веревкой. Формально, вершины двух гор соединены, если отрезки, соединяющие вершины, не пересекаются или не соприкасаются с любыми другими отрезками гор. С помощью этих веревок скалолазы могут взбираться на горы.

Есть m команд, в каждой ровно по два скалолаза. Первый и второй скалолаз из i-й команды стоят на вершинах a_i-й и b_i-й скалы, соответственно. Они хотят встретиться на вершине некоторой горы. Теперь каждый из двух скалолазов двигается согласно следующему алгоритму:

1. если один скалолаз находится на вершине горы, где его партнер уже находится сам, либо рано или поздно придет туда, то первый скалолаз остается ждать на этой горе;
2. в противном случае, скалолаз выбирает самую правую скалу справа от его текущей скалы, до которой он может добраться по веревке; взбирается на эту скалу и продолжает процесс (скалолаз может взобраться и на гору, которая ниже его текущей).

Для каждой команды определите номер скалы, где участники этой команды встретятся!