F. Reverse и Swap
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задан массив $$$a$$$ длины $$$2^n$$$. Вам нужно обработать $$$q$$$ запросов к нему. Каждый запрос одного из следующих $$$4$$$ типов:

  1. $$$Replace(x, k)$$$ — присвоить элементу $$$a_x$$$ значение $$$k$$$;
  2. $$$Reverse(k)$$$ — развернуть каждый подмассив $$$[(i-1) \cdot 2^k+1, i \cdot 2^k]$$$ для всех $$$i$$$ ($$$i \ge 1$$$);
  3. $$$Swap(k)$$$ — поменять местами подмассивы $$$[(2i-2) \cdot 2^k+1, (2i-1) \cdot 2^k]$$$ и $$$[(2i-1) \cdot 2^k+1, 2i \cdot 2^k]$$$ для всех $$$i$$$ ($$$i \ge 1$$$);
  4. $$$Sum(l, r)$$$ — вывести сумму элементов подмассива $$$[l, r]$$$.

Напишите программу, которая может достаточно быстро обрабатывать заданные запросы.

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

В первой строке заданы два целых числа $$$n$$$, $$$q$$$ ($$$0 \le n \le 18$$$; $$$1 \le q \le 10^5$$$) — длина массива $$$a$$$ и количество запросов.

Во второй строке заданы $$$2^n$$$ целых чисел $$$a_1, a_2, \ldots, a_{2^n}$$$ ($$$0 \le a_i \le 10^9$$$).

В следующих $$$q$$$ строках заданы запросы — по одному в строке. Каждый запрос одного из следующих $$$4$$$ типов:

  • «$$$1$$$ $$$x$$$ $$$k$$$» ($$$1 \le x \le 2^n$$$; $$$0 \le k \le 10^9$$$) — $$$Replace(x, k)$$$;
  • «$$$2$$$ $$$k$$$» ($$$0 \le k \le n$$$) — $$$Reverse(k)$$$;
  • «$$$3$$$ $$$k$$$» ($$$0 \le k < n$$$) — $$$Swap(k)$$$;
  • «$$$4$$$ $$$l$$$ $$$r$$$» ($$$1 \le l \le r \le 2^n$$$) — $$$Sum(l, r)$$$.

Гарантируется, что в каждом тесте есть как минимум один запрос $$$Sum$$$.

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

Выведите ответы для каждого запроса $$$Sum$$$.

Примеры
Входные данные
2 3
7 4 9 9
1 2 8
3 1
4 2 4
Выходные данные
24
Входные данные
3 8
7 0 8 8 7 1 5 2
4 3 7
2 1
3 2
4 1 6
2 3
1 5 16
4 8 8
3 0
Выходные данные
29
22
1
Примечание

В первом примере, первоначально, массив $$$a$$$ равен $$$\{7,4,9,9\}$$$.

После обработки первого запроса, массив $$$a$$$ становится $$$\{7,8,9,9\}$$$.

После обработки второго запроса, массив $$$a_i$$$ становится $$$\{9,9,7,8\}$$$.

Поэтому, ответ на третий запрос равен $$$9+7+8=24$$$.

Во втором примере, первоначально, массив $$$a$$$ равен $$$\{7,0,8,8,7,1,5,2\}$$$. Далее происходит следующее:

  1. $$$Sum(3, 7)$$$ $$$\to$$$ $$$8 + 8 + 7 + 1 + 5 = 29$$$;
  2. $$$Reverse(1)$$$ $$$\to$$$ $$$\{0,7,8,8,1,7,2,5\}$$$;
  3. $$$Swap(2)$$$ $$$\to$$$ $$$\{1,7,2,5,0,7,8,8\}$$$;
  4. $$$Sum(1, 6)$$$ $$$\to$$$ $$$1 + 7 + 2 + 5 + 0 + 7 = 22$$$;
  5. $$$Reverse(3)$$$ $$$\to$$$ $$$\{8,8,7,0,5,2,7,1\}$$$;
  6. $$$Replace(5, 16)$$$ $$$\to$$$ $$$\{8,8,7,0,16,2,7,1\}$$$;
  7. $$$Sum(8, 8)$$$ $$$\to$$$ $$$1$$$;
  8. $$$Swap(0)$$$ $$$\to$$$ $$$\{8,8,0,7,2,16,1,7\}$$$.