Как вы уже знаете, Танос завладел всеми камнями бесконечности. Теперь он перешел к своему коварному плану. Изначально во вселенной было $n$ героев, пронумерованных от $1$ до $n$, некоторые из них были живыми, а некоторые уже погибли. Щелчок пальцами берет всех персонажей на четных позициях и либо оживляет мертвых, либо убивает живых.

Как многие фанаты знают, Стэн Ли является одним из богов вселенной. Он решил поиграть с Таносом и дал ему q запросов двух видов.

1. Щелкнуть пальцем на отрезке с $l$ по $r$. В ходе этого запроса, для всех героев с индексами вида $l + 2k \le r$ делается следующая операция: мертвые оживают, а живые умирают.
2. Найти количество все еще живых персонажей на отрезке с $l$ по $r$.

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

В первой строке даны два целых числа $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$) — тип запроса и его левая и правая границы.

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

Для каждого запроса второго типа выведите одно число — количество живых на отрезке с $l$ по $r$.