Дан массив целых чисел, изначально заполненный нулями. С ним необходимо производить два типа операций:

• ! i x - присвоить ячейке i значение x;
• ? l r - узнать сумму значений на отрезке [l, r].

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

Первая строка содержит размер массива n и количество запросов m (1 ≤ n ≤ (109 + 7), 1 ≤ m ≤ 2 * 105). За ним следуют m запросов по одному в строке.

В процессе работы программы необходимо поддерживать два числа P и Q. Изначально P = 91, Q = 47.

Запрос вида "**! A B**" обозначает, что в ячейку (A + P) mod n необходимо записать число (B + Q) mod (109 + 7).

Запрос вида "**? A B**" обозначает, что необходимо посчитать сумму между элементами (A + P) mod n, (B + Q) mod n включительно. Пусть ответ равен Z. Тогда необходимо изменить числа P и Q следующим образом:

P = (P * 31) + Z mod (109 + 7),

Q = (Q * 29) + Z mod (109 + 7).

Нумерация элементов начинается с нуля.

Все входные числа не превосходят 109 + 7.

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

Для каждого запроса на сумму нужно вывести ответ на него в отдельной строке.