В Центре Помощи Магистрам наступил Новый год, а значит время добавить нововведение!
Теперь ученикам даются дистанционные курсы, при этом всего есть \(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\) учеников скажите, какую максимальную итоговую оценку он может получить.
Выходные данные
Для каждого набора входных данных выведите \(q\) целых чисел, \(j\)-е из которых является максимальной итоговой оценкой, которую может получить \(j\)-й ученик.
Примечание
В первом наборе входных данных:
- Максимальная оценка для первого ученика равна \(1\):
- На первом дистанционном курсе он получит оценку \(1\).
Таким образом, итоговая оценка равна \(1\).
- Максимальная оценка для второго ученика равна \(5\):
- На первом дистанционном курсе он получит оценку \(1\).
- На втором дистанционном курсе он получит оценку \(4\).
Таким образом, итоговая оценка равна \(1\) \(|\) \(4\) \(=\) \(5\). - Максимальная оценка для третьего ученика равна \(4\):
- На втором дистанционном курсе он получит оценку \(4\).
Таким образом, итоговая оценка равна \(4\).
Во втором наборе входных данных:
- Максимальная оценка для первого ученика равна \(15\):
- На первом дистанционном курсе он получит оценку \(7\).
- На втором дистанционном курсе он получит оценку \(4\).
- На третьем дистанционном курсе он получит оценку \(8\).
Тем самым, итоговая оценка равна \(7\) \(|\) \(4\) \(|\) \(8\) \(=\) \(15\).
- Максимальная оценка для второго ученика равна \(11\):
- На третьем дистанционном курсе он получит оценку \(9\).
- На четвертом дистанционном курсе он получит оценку \(2\).
Тем самым, итоговая оценка равна \(9\) \(|\) \(2\) \(=\) \(11\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|