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 twentyfirst — 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
≤ 10^{5}). The second line contains integers a_{1}, …, a_{n}
that are planned activities in each of the days of Nastya’s plan (1
≤ a_{i} ≤ 10^{9}). Then there are m blocks, which describe
Nastya’s friends. The first line of the ith block contains an integer
q_{i} that is the number of questions asked by the ith friend before
choosing his own plan (0 ≤ q_{i} ≤ 10^{5}). The jth of
the following q_{i} lines contains integers f_{ij} and x_{ij}, meaning
the question of what activity is scheduled for x_{ij} day of f_{ij}
plan (0 ≤ f_{ij} < i; 1 ≤ x_{ij} ≤ n).
The next line contains integers p_{i} and c_{i} that are the number of
the plan taken as a basis, and the amount of changes in it (0 ≤
p_{i} < i; 0 ≤ c_{i} ≤ n). The following c_{i} lines
contain four integers d_{ij}, k_{ij}, p_{ij} and t_{ij} 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 ≤ d_{ij},
k_{ij}, p_{ij} ≤ n; d_{ij} + (k_{ij} − 1) · p_{ij} ≤
n; 1 ≤ t_{ij} ≤ 10^{9}).
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 q_{i} does not exceed 10^{5}, the sum of all
k_{ij} does not exceed 5 · 10^{6}, the sum of all c_{i} does not
exceed 10^{5}.
Output
Output m lines, the ith of them should contain q_{i}
integers — the answers to the questions of the ith friend.
Sample
input  output 

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