eolymp
Competitions

Пятёрка за неделю 23 (2013-2014)

Яйца Фаберже

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

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

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

Time limit 1 second
Memory limit 256 MiB
Input example #1
5 2
1 3
1 2 1
3 4 2
5 5 3
1 5
2 1
1 4 4
1 5
Output example #1
3
2
Author Александ Цицюра, Виталий Цицюра