Яйца Фаберже
Яйца Фаберже - известная серия ювелирных пасхальных яиц, изготовленных фирмой Карла Фаберже. Серия создавалась в период от 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, является яйцо, которое не содержит полоски драгоценных камней. Некоторые изделия могут не содержать некоторых полосок.
Выходные данные
Для каждого запроса второго типа в отдельной строке вывести ответ.