Множители 3

Имеется n чисел a[0], a[1], ..., a[n-1]. Изначально все они равны 0. Вы можете производить два типа операций:

1. Увеличить все числа между индексами a и b (включительно) на 1. Операция задается командой "0 a b"

2. Вывести количество чисел между индексами a и b (включительно), которые делятся на 3. Операция задается командой "1 a b".

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

Первая строка содержит два целых числа n и q (1 ≤ n, q ≤ 100000). Каждая из следующих q строк имеет вид "0 a b" или "1 a b", как описано выше. Известно, что 0 ≤ a ≤ b ≤ n - 1.

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

Для каждого запроса вида "1 a b" вывести соответствующий ответ.

Примеры