D. Скалолазание
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

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

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

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

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

В первой строке содержится единственное целое число n (1 ≤ n ≤ 105) — количество скал. Следующие n строк описывают скалы: i-я из них содержит два целых числа через пробел xi, yi (1 ≤ xi ≤ 107; 1 ≤ yi ≤ 1011) — позиция и высота i-й скалы. Скалы даны в порядке увеличения xi, то есть, xi < xj для i < j.

В следующей строке записано единственное целое число m (1 ≤ m ≤ 105) — количество команд. Следующие m строк описывают команды: i-я строка содержит два целых числа через пробел ai, bi (1 ≤ ai, bi ≤ n) — номера скал, где расположены участники i-й команды. Числа ai и bi могут быть равны.

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

В единственной строке выведите m целых чисел через пробел, где i-е число — номер скалы, на которой встретятся скалолазы из i-й команды.

Примеры
Входные данные
6
1 4
2 1
3 2
4 3
6 4
7 4
3
3 1
5 6
2 3
Выходные данные
5 6 3