29277번 - Связанность и пересечения 다국어

Как известно, Зайка очень любит петь, танцевать, а в особенности любит спорт, поэтому она не могла пропустить олимпийские игры в Сочи. Приехав на Олимпиаду, Зайка сразу обратила внимание на её символ --- пять колец, связанных друг с другом. Она поняла, что ей нравится связанность и пересечения. В символе Олимпиады этого не так много, поэтому она решила придумать свой символ, где все будет связано, а пересечений будет много.

Начать она решила с отрезков на координатной прямой. Нарисовав несколько штук, она задалась вопросом: какое максимальное количество отрезков можно выбрать из нарисованных таким образом, чтобы любые два выбранных отрезка пересекались? При этом, Зайка решила, что один из нарисованных отрезков точно должен попасть в множество выбранных.

Зайка считает, что два отрезка пересекаются, если длина их пересечения больше нуля и меньше длин обоих отрезков (то есть отрезки пересекаются, но не вкладываются). Отрезки, имеющие ровно одну общую точку, не считаются пересекающимися.

Зайка уже который час пытается решить эту задачу, и у нее ничего не получается. Помогите ей, иначе Олимпиада останется без одного из её талисманов!

В первой строке входного файла задано число $n$ ($1 \le n\le 3{\,}000$) --- количество отрезков на прямой. Далее идут $n$ строк по два числа $l_i$ и $r_i$ ($1 \le l_i \le r_i \le 10^9$) --- координаты концов отрезка.

Гарантируется, что никакие два отрезка не начинаются в одной точке, и никакие два отрезка не заканчиваются в одной точке.

В $n+2$ строке входного файла дано число $k$ ($1 \le k \le 10^5$) --- количество запросов. В каждой из следующих $k$ строк записано одно число $x$ ($1 \le x \le n$) --- номер отрезка, который точно должен попасть в искомое множество.

В выходной файл выведите $k$ строк.

В $i$-ой строке выходного файла выведите ответ на $i$-ый запрос.