Everybody loves Hypnotoad! Its show is one of the most popular on TV! It is true that after the show nobody remembers what it was about and even what they have been doing during all that time. However, this does not prevent the numerous fans of Hypnotoad from enjoying their favorite show.

In order to study the amazing properties of Hypnotoad, Professor Farnsworth constructed a special device, which trapped and scanned its waves. He found out that at each time moment Hypnotoad's eyes could be in one of n states. Professor denoted those states by the numbers 0, 1, …, n−1 for simplicity. The states of the eyes changed according to one of several linear laws. There were m such laws and each of them could be specified by five integers: s₀, t₀, Δs, Δt, k. When Hypnotoad “worked” according to such a law, its left eye switched to the state s_i and its right eye switched to the state t_i successively for all integers i from 0 to k−1, where

After several weeks of research, Farnsworth understood that Hypnotoad's waves could be used to learn many secrets of the Universe. For example, Hypnotoad could see the dark matter and extract information from black holes. In order to see the same way Hypnotoad saw, Professor constructed another device that emulated “hypnosight”: each of its four oculars could stay in one of the n states changing according to linear laws. Farnsworth carried out a series of experiments and decided to draw a diagram in which he would mark for every possible state of the device whether Hypnotoad's eyes could be in states similar to the states of the oculars. Help Professor automate this process.

One experiment is described by nine integers: a₀, b₀, c₀, d₀, Δa, Δb, Δc, Δd, q. For all integer values of j from 0 to q−1, the oculars successively switch to the following states:

For every state of the device (a_j, b_j, c_j, d_j), it is required to determine whether Hypnotoad's eyes can be in a state (s_i, t_i) such that

In the first line you are given the number n of states of Hypnotoad's eyes and the number m of laws of their behavior (1 ≤ n ≤ 5000, 1 ≤ m ≤ 1000). Each of the following m lines contains the integers s₀, t₀, Δs, Δt, k, which specify the law according to which the states of the eyes are switched (0 ≤ s₀, t₀, |Δs|, |Δt| ≤ n−1; 1 ≤ k ≤ 567).

In the next line you are given the number p of experiments (1 ≤ p ≤ 345). Each of the following p lines contains the integers a₀, b₀, c₀, d₀, Δa, Δb, Δc, Δd, q, which describe the experiment (0 ≤ a₀, b₀, c₀, d₀, |Δa|, |Δb|, |Δc|, |Δd| ≤ n−1; 1 ≤ q ≤ 345).

Output p lines, one line per experiment. For each experiment, determine its result: the set of numbers x_j for j = 0, 1, …, q−1. In this set, x_j = 1 if Hypnotoad's eyes can be in a state complying with the corresponding state of the device and x_j = 0 otherwise. If q ≤ 20, output all x_j in a row without spaces. If q > 20, output one number equal to