Имеется n чисел a0, a1, ..., an-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**" вывести соответствующий ответ.