Duff — королева своей страны, Andarz Gu. Она — поклоннца спортивного программирования. Поэтому, увидев своего министра Malek'а без дела, она дала ему последовательность, состоящую из n неотрицательных целых чисел a1, a2, ..., an и попросила его выполнить q запросов для неё на этой последовательности.
Дано два типа запросов:
- даны числа l, r и k, Malek должен произвести
для каждого l ≤ i ≤ r (
, побитовое исключающее ИЛИ чисел a и b) - даны числа l и r, Malek длжен назвать королеве качество данной последовательности al, al + 1, ... , ar.
качеством последовательности b1, ..., bk называется количество её Kheshtak'ов. Неотрицательное целое числа w является Kheshtak'ом последовательности тогда и только тогда, когда у неё есть подпоследовательность bi1, bi2, ..., bix (возможно, пустая), такая, что 
(1 ≤ i1 < i2 < ... < ix ≤ k). Если эта подпоследовательнось пустая, то w полагается равным нулю.
В отличие от Duff, Malek — не программист. Поэтому он попросил вас о помощи. Пожалуйста, помогите ему выполнить эти запросы.
Выходные данные
Выведите ответ на каждый запрос второго типа в своей строке.
Примечание
В первом запросе нас интересуют все Kheshtak'и последовательности (1, 2, 3, 4, 2), их восемь штук и они 0, 1, 2, 3, 4, 5, 6, 7.
В третьем запросе нас интересуют все Kheshtak'и последовательности (1, 10, 3, 4, 2), их шестнадцать штук и они 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.
В пятом запросе нас интересуют все Kheshtak'и последовательности (0). Единственный Khestak в данном случае равен 0.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 5
1 2 3 4 2
2 1 5
1 2 2 8
2 1 5
1 1 3 10
2 2 2
|
8
16
1
|