Підприємство
Обмеження: 2 сек., 256 МіБ
Недавно Петрик відкрив свою фірму, яка надавала web-послуги: створення сайтів, оптимізацію та просування їх в пошукових системах (SEO).
У Петрика працює \(n\) працівників. Усі вони за комп’ютерами вишиковані в ряд і мають свій порядковий номер від 1 до \(n\). Також кожен працівник має коефіцієнт якості виконання своєї роботи — число від 0 до 1000. Час від часу Петрик провіряє якість роботи працівників з номерами від \(x\) до \(y\) включно. Сумарною якістю роботи тих працівників будемо називати суму якостей кожного працівника від \(x\) до \(y\). Якщо сумарна якість ділиться на 3, то робота працівників на відрізку від \(x\) до \(y\) задовільяє Петрика, інакше він буде змушений приймати якісь міри щодо цих робітників :) Проте інколи Петрик відсилає деяких робітників на спеціальні курси, де вони збільшують свій коефіцієнт якості на \(z\).
Петрик дуже часто робить такі провірки, тому він просить dас написати програму, яка б робила за нього цю важку роботу...
Вхідні дані
У першому рядку задано два цілих числа \(n\), \(m\) — кількість робітників та сума кількостей провірянь Петрика та відсилань на курси, відповідно.
У другому рядку задано \(n\) цілих чисел \(a_i\) — коефіцієнт якості роботи \(і\)-того робітника.
У наступних \(m\) рядках задано самі події в форматі 1 \(x\) \(y\) або 0 \(x\) \(z\).
У першому випадку Петрик провіряє якість працівників на відрізку \([x; y]\) включно, в другому випадку збільшує коефіцієнт якості роботи працівника з номером \(x\) на \(z\).
Вихідні дані
Для кожної провірки Петрика на якість працівників виведіть 1 якщо він задовільний, інакше 0.
Обмеження
\(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\).
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
5 4 1 2 3 5 2 1 1 3 1 1 5 0 1 2 1 1 5 | 1 0 1 |
Надіслати розв'язок
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|