Вам задан массив \(a\) длины \(2^n\). Вам нужно обработать \(q\) запросов к нему. Каждый запрос одного из следующих \(4\) типов:
- \(Replace(x, k)\) — присвоить элементу \(a_x\) значение \(k\);
- \(Reverse(k)\) — развернуть каждый подмассив \([(i-1) \cdot 2^k+1, i \cdot 2^k]\) для всех \(i\) (\(i \ge 1\));
- \(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\));
- \(Sum(l, r)\) — вывести сумму элементов подмассива \([l, r]\).
Напишите программу, которая может достаточно быстро обрабатывать заданные запросы.
Примечание
В первом примере, первоначально, массив \(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\}\). Далее происходит следующее:
- \(Sum(3, 7)\) \(\to\) \(8 + 8 + 7 + 1 + 5 = 29\);
- \(Reverse(1)\) \(\to\) \(\{0,7,8,8,1,7,2,5\}\);
- \(Swap(2)\) \(\to\) \(\{1,7,2,5,0,7,8,8\}\);
- \(Sum(1, 6)\) \(\to\) \(1 + 7 + 2 + 5 + 0 + 7 = 22\);
- \(Reverse(3)\) \(\to\) \(\{8,8,7,0,5,2,7,1\}\);
- \(Replace(5, 16)\) \(\to\) \(\{8,8,7,0,16,2,7,1\}\);
- \(Sum(8, 8)\) \(\to\) \(1\);
- \(Swap(0)\) \(\to\) \(\{8,8,0,7,2,16,1,7\}\).