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

За предыдущие годы Насте так надоели прихоти её друзей, что она решила в этом году автоматизировать процесс.

В первой строке даны целые числа n и m — количество дней поездки и количество друзей Насти (1 ≤ n, m ≤ 10⁵). Во второй строке даны целые числа a₁, …, a_n — планируемые виды деятельности в каждый из дней по плану Насти (1 ≤ a_i ≤ 10⁹). Далее следуют m блоков, описывающих друзей Насти. Первая строка i-го блока содержит целое число q_i — количество вопросов, которые задаёт i-й друг перед выбором своего плана (0 ≤ q_i ≤ 10⁵). В j-й из следующих q_i строк записаны целые числа f_ij и x_ij, означающие вопрос о том, какая активность запланирована на x_ij-й день f_ij-го плана (0 ≤ f_ij < i; 1 ≤ x_ij ≤ n). В следующей строке даны целые числа p_i и c_i — номер плана, который взят за основу, и количество изменений в нём (0 ≤ p_i < i; 0 ≤ c_i ≤ n). В следующих c_i строках записаны по четыре целых числа d_ij, k_ij, p_ij и t_ij — номер первого дня, в который нужно поменять активность, общее количество дней, в которые нужно поменять активность, период между днями и новый вид активности (1 ≤ d_ij, k_ij, p_ij ≤ n; d_ij + (k_ij − 1) · p_ij ≤ n; 1 ≤ t_ij ≤ 10⁹). План Насти имеет номер 0, планы друзей пронумерованы целыми числами от 1 до m в том порядке, в котором друзья описаны во входных данных. Сумма всех q_i не превосходит 10⁵, сумма всех k_ij не превосходит 5 · 10⁶, сумма всех c_i не превосходит 10⁵.

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