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.

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⁵). The second line contains integers a₁, …, a_n that are planned activities in each of the days of Nastya’s plan (1 ≤ a_i ≤ 10⁹). Then there are m blocks, which describe Nastya’s friends. The first line of the i-th block contains an integer q_i that is the number of questions asked by the i-th friend before choosing his own plan (0 ≤ q_i ≤ 10⁵). The j-th 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⁹). 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⁵, the sum of all k_ij does not exceed 5 · 10⁶, the sum of all c_i does not exceed 10⁵.

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