2196: Клацання пальцями
Перегляд у форматі PDFЯк ви вже знаєте, Танос заволодів усім камінням нескінченності. Тепер він перейшов до свого підступного плану. Спочатку у всесвіті було ~n~ героїв, пронумерованих від 1 до ~n~, деякі з них були живими, а деякі вже загинули. Клацання пальцями бере всіх персонажів на парних позиціях і або оживляє мертвих, або вбиває живих. Як багато хто з фанатів знає, Стен Лі є одним з богів всесвіту, і він вирішив погратися з Таносом і дав йому ~q~ запитів двох видів.
1. Клацнути пальцем на відрізку з ~l~ по ~r~. В ході цього запиту для всіх героїв з індексами виду ~l + 2k \le r~ виконується наступна операція: мертві оживають, а живі вмирають.
2. Знайти кількість все ще живих персонажів на відрізку з ~l~ по ~r~.
Input
У першому рядку дано два цілих числа ~n~ і ~m~ (~1 \le n, m \le 300000~) - кількість героїв і кількість запитів Стена Лі.
У наступному рядку дано ~n~ цілих чисел ~a_i~. ~a_i~ = 1, якщо персонаж живий, і 0, якщо мертвий.
У наступних ~m~ рядках дано три цілих числа ~t~, ~l~, і ~r~ (~1 \le t \le 2~, ~1 \le l \le r \le n~) - тип запиту і його ліва та права межі.
Output
Для кожного запиту другого типу виведіть одне число - кількість живих на відрізку з ~l~ по ~r~.
Sample Input 1
3 4
1 0 1
1 1 3
2 1 3
1 1 3
2 1 3
Sample Output 1
0
2
Коментарі
в прикладі немає помилки? після першої операції масив стає [0, 1, 0], тобто 1 живий, у відповіді пише 0
вибачте, просто не дочитав умову)