Ваня очень любит бургеры, а так же очень любит тратить деньги. На улице, где живет Ваня, находится \(n\) бургерных.
У Вани есть \(q\) друзей, \(i\)-й друг предложил Ване встретиться у бургерной с номером \(l_i\) и прогуляться до бургерной \(r_i\) \((l_i \leq r_i)\). Во время прогулки с \(i\)-м другом Ваня может зайти во все бургерные с номерами \(x\) такими, что \(l_i \leq x \leq r_i\).
Для каждой бургерной Ваня знает стоимость самого дорогого бургера \(c_i\) бурлей. Ваня хочет зайти в какое-то подмножество бургерных по пути, взять в каждой из них самый дорогой бургер и потратить как можно больше денег. Но есть небольшая проблема: карта Вани сломалась, и вместо того, чтобы снимать деньги после покупки, количество денег на карте меняется следующим образом.
Пусть до покупки у Вани было \(d\) бурлей и Ваня потратил \(c\) бурлей в бургерной, тогда после этих действий у Вани на счете останется \(d \oplus c\) бурлей, где \(\oplus\) обозначает операцию побитового исключающего ИЛИ.
Сейчас на счету Вани \(2^{2^{100}} - 1\) бурлей и он уже собирается на прогулку. Помогите Ване узнать, какое максимальное количество денег он сможет потратить, если пойдет гулять с другом под номером \(i\). Количество бурлей, потраченных Ваней, определяется как разность между начальным количеством бурлей на счете Вани и конечным количеством бурлей на его счете.
Выходные данные
Выведите \(q\) строк, в \(i\)-й строке выведите максимальное количество денег, которое Ваня может потратить вместе с другом под номером \(i\).
Примечание
В первом тесте для того, чтобы потратить максимальное количество денег с первым и третьим другом, Ване достаточно зайти в первую бургерную. Со вторым другом Ване достаточно зайти в третью бургерную. Во втором тесте для третьего друга (который собирается прогуляться от первой до третьей бургерной) всего есть 8 вариантов потратить деньги — \(0\), \(12\), \(14\), \(23\), \(12 \oplus 14 = 2\), \(14 \oplus 23 = 25\), \(12 \oplus 23 = 27\), \(12 \oplus 14 \oplus 23 = 20\). Максимальное количество денег получается потратить, если зайти в первую и третью бургерную — \(12 \oplus 23 = 27\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
7 2 3 4
3
1 4
2 3
1 3
|
7
3
7
|
|
2
|
5
12 14 23 13 7
15
1 1
1 2
1 3
1 4
1 5
2 2
2 3
2 4
2 5
3 3
3 4
3 5
4 4
4 5
5 5
|
12
14
27
27
31
14
25
26
30
23
26
29
13
13
7
|