ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural FU Open Personal Contest 2014

About     Problems     Submit solution     Judge status     Standings
Contest is over

G. All Inclusive

Time limit: 2.0 second
Memory limit: 64 MB
Winter in Yekaterinburg is the longest time of the year. And everyone spends long winter evenings in his own way. Nastya does not like winter. She loves the bright sun and warm sea. Therefore, every year in the middle of winter she flies with her friends for a couple of weeks to some tropical country to lie on a beach and go sightseeing. Every year she faces the problem of trip planning. She knows exactly what she will do each day. However, with her friends it is much more complicated. Each friend is unable to make the plan of his trip, therefore, at first he asks Nastya about who what planning to do in any of days, then chooses one of the plans, and sometimes changes a few days in it for himself. Moreover, Nastya has to keep track of who in which day is planning for himself. It is fine, if each friend just changes a day or two for himself, but many say, “I want to hang out on a beach from the fifth to the eleventh day after day. And I want to go on a tour three times starting from the seventh day once a week.” Nastya understands that her friend wants to spend the fifth, ninth and eleventh day on a beach and the seventh, fourteenth and twenty-first — on a tour. If a friend wants to do several things at the same day, in fact he will do what he says Nastya after all.
Nastya is so tired of that whims of her friends that she decided this year to automate the process.

Input

The first line contains integers n and m that are the number of days in the trip and the number of Nastya’s friends (1 ≤ n, m ≤ 105). The second line contains integers a1, …, an that are planned activities in each of the days of Nastya’s plan (1 ≤ ai ≤ 109). Then there are m blocks, which describe Nastya’s friends. The first line of the i-th block contains an integer qi that is the number of questions asked by the i-th friend before choosing his own plan (0 ≤ qi ≤ 105). The j-th of the following qi lines contains integers fij and xij, meaning the question of what activity is scheduled for xij day of fij plan (0 ≤ fij < i; 1 ≤ xijn). The next line contains integers pi and ci that are the number of the plan taken as a basis, and the amount of changes in it (0 ≤ pi < i; 0 ≤ cin). The following ci lines contain four integers dij, kij, pij and tij that are the number of the first day in which it is needed to change the activity, the total number of days in which it is needed to change the activity, the period between these days and a new kind of activity (1 ≤ dij, kij, pijn; dij + (kij − 1) · pijn; 1 ≤ tij ≤ 109). Nastya’s plan has the number 0, plans of her friends are numbered by integers from 1 to m in the order in which the friends are described in the input. The sum of all qi does not exceed 105, the sum of all kij does not exceed 5 · 106, the sum of all ci does not exceed 105.

Output

Output m lines, the i-th of them should contain qi integers — the answers to the questions of the i-th friend.

Sample

inputoutput
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
Problem Author: Egor Shchelkonogov
Problem Source: Open Ural FU Personal Contest 2014
To submit the solution for this problem go to the Problem set: 2096. All Inclusive