E. Дистанционные курсы в ЦПМ
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В Центре Помощи Магистрам наступил Новый год, а значит время добавить нововведение!

Теперь ученикам даются дистанционные курсы, при этом всего есть $$$n$$$ курсов. За $$$i$$$-й дистанционный курс ученик может получить оценку от $$$x_i$$$ до $$$y_i$$$.

Но каждому ученику могут быть доступны не все курсы, а именно $$$j$$$-му ученику даются только курсы с номерами от $$$l_j$$$ до $$$r_j$$$, то есть дистанционные курсы с номерами $$$l_j, l_j + 1, \ldots, r_j$$$.

Создатели дистанционных курсов решили определять итоговую оценку особенным образом. Пусть $$$j$$$-й ученик получил оценки $$$c_{l_j}, c_{l_j + 1}, \ldots, c_{r_j}$$$ за свои дистанционные курсы, тогда его итоговая оценка будет равна $$$c_{l_j}$$$ $$$|$$$ $$$c_{l_j + 1}$$$ $$$|$$$ $$$\ldots$$$ $$$|$$$ $$$c_{r_j}$$$, где $$$|$$$ обозначает операцию побитового ИЛИ.

Так как чат-бот с решениями дистанционных курсов сломался, то ученики попросили вас помочь. Для каждого из $$$q$$$ учеников скажите, какую максимальную итоговую оценку он может получить.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество дистанционных курсов.

Каждая из следующих $$$n$$$ строк содержит два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$0 \le x_i \le y_i < 2^{30}$$$) — минимальная и максимальная оценка, которую можно получить за $$$i$$$-й курс.

Следующая строка содержит одно целое число $$$q$$$ ($$$1 \le q \le 2\cdot10^5$$$) — количество учеников.

Каждая из следующих $$$q$$$ строк содержит два целых числа $$$l_j$$$ и $$$r_j$$$ ($$$1 \le l_j \le r_j \le n$$$) — минимальный и максимальный номер дистанционных курсов, доступных для $$$j$$$-го ученика.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных и сумма $$$q$$$ по всем наборам входных данных не превосходят $$$2\cdot10^5$$$.

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

Для каждого набора входных данных выведите $$$q$$$ целых чисел, $$$j$$$-е из которых является максимальной итоговой оценкой, которую может получить $$$j$$$-й ученик.

Пример
Входные данные
3
2
0 1
3 4
3
1 1
1 2
2 2
4
1 7
1 7
3 10
2 2
5
1 3
3 4
2 3
1 4
1 2
6
1 2
2 2
0 1
1 1
3 3
0 0
4
3 4
5 5
2 5
1 2
Выходные данные
1 5 4 
15 11 15 15 7 
1 3 3 3
Примечание

В первом наборе входных данных:

  1. Максимальная оценка для первого ученика равна $$$1$$$:
    • На первом дистанционном курсе он получит оценку $$$1$$$.
    Таким образом, итоговая оценка равна $$$1$$$.

  2. Максимальная оценка для второго ученика равна $$$5$$$:
    • На первом дистанционном курсе он получит оценку $$$1$$$.
    • На втором дистанционном курсе он получит оценку $$$4$$$.
    Таким образом, итоговая оценка равна $$$1$$$ $$$|$$$ $$$4$$$ $$$=$$$ $$$5$$$.
  3. Максимальная оценка для третьего ученика равна $$$4$$$:
    • На втором дистанционном курсе он получит оценку $$$4$$$.
    Таким образом, итоговая оценка равна $$$4$$$.

Во втором наборе входных данных:

  1. Максимальная оценка для первого ученика равна $$$15$$$:
    • На первом дистанционном курсе он получит оценку $$$7$$$.
    • На втором дистанционном курсе он получит оценку $$$4$$$.
    • На третьем дистанционном курсе он получит оценку $$$8$$$.
    Тем самым, итоговая оценка равна $$$7$$$ $$$|$$$ $$$4$$$ $$$|$$$ $$$8$$$ $$$=$$$ $$$15$$$.

  2. Максимальная оценка для второго ученика равна $$$11$$$:
    • На третьем дистанционном курсе он получит оценку $$$9$$$.
    • На четвертом дистанционном курсе он получит оценку $$$2$$$.
    Тем самым, итоговая оценка равна $$$9$$$ $$$|$$$ $$$2$$$ $$$=$$$ $$$11$$$.