Запити щодо анти-xor
Нещодавно наш тренер Етібар винайшов нову побітову операцію, схожу на зворотну операцію xor, і назвав її анти-xor. Тепер він пропонує вам задачу, пов'язану з цим винаходом, яка включає обробку запитів. Символ для анти-xor - це #.
Вам дано N чисел. Необхідно виконати такі операції над цими цілими числами:
1) Застосувати анти-xor X до цілого числа в діапазоні від L до R. Цей запит записується як “1 L R X”.
2) Вивести суму всіх чисел у діапазоні від L до R. Цей запит записується як “2 L R”.
Вважаємо, що всі числа є 20-бітними цілими числами, тому операція анти-xor виконується на останніх 20 бітах.
Вхідні дані
Вам надано ціле число N (1 ≤ N ≤ 100000). У другому рядку наведено N цілих чисел (0 ≤ A_i ≤ 10^6). Наступний рядок містить кількість запитів Q (1 ≤ Q ≤ 100000). Кожен з наступних Q рядків містить один запит у вказаних вище формах.
Вихідні дані
Для кожного запиту типу “2 L R” виведіть у окремому рядку суму всіх цілих чисел у діапазоні від L до R.