Множники 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" вивести відповідну відповідь.

Приклади