Мурад очень любит операцию XOR. Он весь день, не переставая XOR-ит различные числа между собой.

В этот раз Мурад встретился с такой задачей. Ему дан массив a размера n. Мурад должен выполнить на этом массиве q запросов. Запросы, как показано ниже, бывают двух типов:

1) 1 l r - в этом запросе на промежутке [l, r] (1 ≤ l < r ≤ n) нужно вычислить сумму всех попарных XOR-ов, то есть величину

2) 2 l r v - в этом запросе на промежутке [l, r] (1 ≤ l ≤ r ≤ n) нужно поXOR-ить все элементы с v.

Примечание: здесь XOR - побитовая операция xor.

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

В первой строке даны два числа n и q (2 ≤ n ≤ 2 * 105, 1 ≤ q ≤ 105) - размер массива и количество запросов соответственно. На следующей строке перечислены сами элементы массива ai (0 ≤ ai ≤ 109).

В следующих q строках даны сами запросы. Сначала идёт тип запроса, число 1 или 2. Если запрос типа 1, то далее идут два числа l и r (1 ≤ l < r ≤ n). Если запрос типа 2, то далее идут три числа l, r и v (1 ≤ l ≤ r ≤ n, 0 ≤ v ≤ 109).

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

Вывести ответы на все запросы типа 1.