Підприємство

Limits: 2 sec., 256 MiB

Недавно Петрик відкрив свою фірму, яка надавала web-послуги: створення сайтів, оптимізацію та просування їх в пошукових системах (SEO).

У Петрика працює \(n\) працівників. Усі вони за комп’ютерами вишиковані в ряд і мають свій порядковий номер від 1 до \(n\). Також кожен працівник має коефіцієнт якості виконання своєї роботи — число від 0 до 1000. Час від часу Петрик провіряє якість роботи працівників з номерами від \(x\) до \(y\) включно. Сумарною якістю роботи тих працівників будемо називати суму якостей кожного працівника від \(x\) до \(y\). Якщо сумарна якість ділиться на 3, то робота працівників на відрізку від \(x\) до \(y\) задовільяє Петрика, інакше він буде змушений приймати якісь міри щодо цих робітників :) Проте інколи Петрик відсилає деяких робітників на спеціальні курси, де вони збільшують свій коефіцієнт якості на \(z\).

Петрик дуже часто робить такі провірки, тому він просить dас написати програму, яка б робила за нього цю важку роботу...

Input

У першому рядку задано два цілих числа \(n\), \(m\) — кількість робітників та сума кількостей провірянь Петрика та відсилань на курси, відповідно.

У другому рядку задано \(n\) цілих чисел \(a_i\) — коефіцієнт якості роботи \(і\)-того робітника.

У наступних \(m\) рядках задано самі події в форматі 1 \(x\) \(y\) або 0 \(x\) \(z\).

У першому випадку Петрик провіряє якість працівників на відрізку \([x; y]\) включно, в другому випадку збільшує коефіцієнт якості роботи працівника з номером \(x\) на \(z\).

Output

Для кожної провірки Петрика на якість працівників виведіть 1 якщо він задовільний, інакше 0.

Constraints

\(0 \le n \le 10^5\),

\(1 \le a_i \le 1000\),

\(0 \le m \le 10^5\),

\(1 \le x \le y \le n\),

\(0 \le z \le 10\).

Samples