ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

2096. Всё включено

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
Зима в Екатеринбурге — самое длинное время года. И каждый коротает долгие зимние вечера по-своему. Настя не любит зиму. Она любит яркое солнце и тёплое море. Поэтому она каждый год посреди зимы вместе со своими друзьями летит на пару-тройку недель в одну из тропических стран поваляться на пляже и посмотреть местные достопримечательности. И каждый год она сталкивается с проблемой планирования поездки. Сама она точно знает, в какой день что будет делать. А вот с её друзьями всё намного сложнее. Никто из них сам не в состоянии составить план поездки, поэтому, договариваясь с Настей, сначала расспрашивает её о том, кто в какой из дней чем планирует заняться, после чего выбирает один из планов и, возможно, меняет в нём несколько дней под себя. А Настя вынуждена отслеживать, кто на какой день что для себя запланировал. И ладно бы, если бы каждый под себя менял только день-два, но многие говорят так: «Хочу с пятого по одиннадцатый день через день проводить на пляже. И ещё три раза хочу съездить на экскурсию — начиная с седьмого дня раз в неделю». Настя понимает, что пятый, девятый и одиннадцатый день её друг хочет провести на пляже, а в седьмой, четырнадцатый и двадцать первый — поехать на экскурсию. Если друг желает заняться несколькими делами в один и тот же день, то в итоге он будет заниматься тем, о чём сказал Насте позже всего.
За предыдущие годы Насте так надоели прихоти её друзей, что она решила в этом году автоматизировать процесс.

Исходные данные

В первой строке даны целые числа n и m — количество дней поездки и количество друзей Насти (1 ≤ n, m ≤ 105). Во второй строке даны целые числа a1, …, an — планируемые виды деятельности в каждый из дней по плану Насти (1 ≤ ai ≤ 109). Далее следуют m блоков, описывающих друзей Насти. Первая строка i-го блока содержит целое число qi — количество вопросов, которые задаёт i-й друг перед выбором своего плана (0 ≤ qi ≤ 105). В j-й из следующих qi строк записаны целые числа fij и xij, означающие вопрос о том, какая активность запланирована на xij-й день fij-го плана (0 ≤ fij < i; 1 ≤ xijn). В следующей строке даны целые числа pi и ci — номер плана, который взят за основу, и количество изменений в нём (0 ≤ pi < i; 0 ≤ cin). В следующих ci строках записаны по четыре целых числа dij, kij, pij и tij — номер первого дня, в который нужно поменять активность, общее количество дней, в которые нужно поменять активность, период между днями и новый вид активности (1 ≤ dij, kij, pijn; dij + (kij − 1) · pijn; 1 ≤ tij ≤ 109). План Насти имеет номер 0, планы друзей пронумерованы целыми числами от 1 до m в том порядке, в котором друзья описаны во входных данных. Сумма всех qi не превосходит 105, сумма всех kij не превосходит 5 · 106, сумма всех ci не превосходит 105.

Результат

Выведите m строк, i-я из них должна содержать qi чисел через пробел — ответы на вопросы i-го друга.

Пример

исходные данныерезультат
3 2
1 2 3
1
0 3
0 2
1 2 2 4
2 2 1 5
3
1 1
1 2
1 3
0 0
3
4 5 5
Автор задачи: Егор Щелконогов
Источник задачи: Открытое личное первенство УрФУ по программированию 2014