Problems
Яйца Фаберже
Яйца Фаберже
Яйца Фаберже - известная серия ювелирных пасхальных яиц, изготовленных фирмой Карла Фаберже. Серия создавалась в период от 1885 до 1917 г. для российской императорской семьи и частных заказчиков.
Один из этих частных заказчиков, заказал у Карла Фаберже \textbf{n} ценных яиц. Каждое яйцо состояло из не более чем \textbf{m} полосок, где каждая полоска содержала драгоценные камни одного цвета. Но коллекция была похищена. К делу привлечены лучшие детективы: Шерлок Холмс и доктор Ватсон.
Поскольку, драгоценности могли попасть на черный рынок, то детективам для их распознавания, нужно знать, как они выглядели. Для экономии времени, владелец рассказывал, чем текущая драгоценность отличается от какой-то предыдущей, номер которой называл Шерлок Холмс.
Ваша задача заключается в написании эффективной структуры для хранения информации о драгоценностях, а чтобы убедиться в ее корректности, нужно еще и отвечать на вопросы, которые имеют вид: "\textit{Сколько разных цветов драгоценных камней находится на украшении, между }\textit{\textbf{l}}\textit{ и }\textit{\textbf{r}}\textit{ полоской включительно?}".
\InputFile
Первая строка содержит два числа \textbf{m }(\textbf{1 }≤ \textbf{m }≤ \textbf{100000}) и \textbf{n }(\textbf{1 }≤ \textbf{n }≤ \textbf{50000}), где \textbf{m }-- количество полосок драгоценных камней, \textbf{n }- количество изготовленных пасхальных яиц Фаберже.
В последующих \textbf{k }(\textbf{1 }≤ \textbf{k }≤ \textbf{200000}) строках заданы \textbf{n }групп. Каждая группа начинается с двух чисел \textbf{i }(\textbf{1 }≤ \textbf{i }≤ \textbf{n}) и \textbf{k}, где \textbf{i }- номер группы, \textbf{k} - количество запросов, которые указывают, чем именно текущий изделие отличается от изделия \textbf{x}, имеющих вид:
\textbf{l r c} - в текущей драгоценности, на промежутке \textbf{\[l, r\]} установить цвет \textbf{с} (\textbf{1} ≤ \textbf{с} ≤ \textbf{32}).
А также, каждая группа заканчивается запросом, который имеет вид:
\textbf{l r} - в текущей драгоценности, посчитать на промежутке \textbf{\[l, r\]} количество различных цветов.
Для расчета \textbf{x}, нужно использовать следующую формулу: \textbf{x} = \textbf{( i + v ) mod i}, где \textbf{v} - ответ на предыдущий запрос второго типа, \textbf{i} - номер текущей группы. Сначала \textbf{v} = \textbf{0}. Гарантируется, что \textbf{1 }≤ \textbf{l}, \textbf{r }≤ \textbf{m}. Изделие с номером \textbf{0}, является яйцо, которое не содержит полоски драгоценных камней. Некоторые изделия могут не содержать некоторых полосок.
\OutputFile
Для каждого запроса второго типа в отдельной строке вывести ответ.
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