Яйця Фаберже
Яйця Фаберже — це відома серія ювелірних великодніх яєць, створених фірмою Карла Фаберже. Вони виготовлялися з 1885 по 1917 рік для російської імператорської родини та приватних замовників.
Один з таких приватних замовників замовив у Карла Фаберже n цінних яєць. Кожне яйце складалося з не більше ніж m рядків, де кожен рядок містив дорогоцінні камені одного кольору. Проте колекцію викрали. До розслідування залучено найкращих детективів: Шерлока Холмса і доктора Ватсона.
Оскільки коштовності могли потрапити на чорний ринок, детективам потрібно знати, як вони виглядали, щоб їх розпізнати. Для економії часу власник розповідав, чим поточна коштовність відрізняється від якоїсь попередньої, номер якої називав Шерлок Холмс.
Ваше завдання — розробити ефективну структуру для зберігання інформації про коштовності, а також відповідати на запитання, які мають вигляд: "Скільки різних кольорів дорогоцінних каменів знаходиться на прикрасі між l і r рядком включно?".
Вхідні дані
Перша строка містить два числа m (1 ≤ m ≤ 100000) і n (1 ≤ n ≤ 50000), де m — кількість рядків дорогоцінних каменів, n — кількість виготовлених великодніх яєць Фаберже.
У наступних k (1 ≤ k ≤ 200000) рядках задані n груп. Кожна група починається з двох чисел i (1 ≤ i ≤ n) і k, де i — номер групи, k — кількість запитів, які вказують, чим саме поточний виріб відрізняється від виробу x, мають вигляд:
l r c — у поточній коштовності, на проміжку [l, r] встановити колір с (1 ≤ с ≤ 32).
Також кожна група закінчується запитом, який має вигляд:
l r — у поточній коштовності, порахувати на проміжку [l, r] кількість різних кольорів.
Для розрахунку x потрібно використовувати наступну формулу: x = (i + v) mod i, де v — відповідь на попередній запит другого типу, i — номер поточної групи. Спочатку v = 0. Гарантується, що 1 ≤ l, r ≤ m. Виріб з номером 0 — це яйце, яке не містить рядків дорогоцінних каменів. Деякі вироби можуть не містити деяких рядків.
Вихідні дані
Для кожного запиту другого типу в окремому рядку вивести відповідь.