Все любят Гипножабу! Её шоу — одно из самых популярных на телевидении. Правда, после его просмотра люди не могут вспомнить, о чём оно было и даже что они всё это время делали. И всё же многочисленным фанам Гипножабы это не мешает испытывать воистину положительные эмоции от любимого зрелища.

Профессор Фарнсворт для изучения интереснейших свойств Гипножабы сконструировал специальный прибор, улавливающий и сканирующий её волны. Ему удалось выяснить, что в каждый момент времени её глаза могут находиться в одном из n состояний. Для простоты профессор обозначил эти состояния числами 0, 1, …, n−1. Состояния глаз меняются по одному из линейных законов, для каждого из которых профессор смог вычислить формулу. Всего получилось m законов, каждый из них можно задать 5 целыми числами: s₀, t₀, Δs, Δt, k. Когда Гипножаба «работает» по такому закону, её левый глаз принимает состояние s_i, а правый — t_i последовательно для всех целых i от 0 до k−1, где

После нескольких недель исследований Фарнсворт понял, что с помощью волн Гипножабы можно узнать многие секреты устройства Вселенной. Например, Гипножаба способна видеть тёмную материю и получать информацию из чёрных дыр. Для того чтобы научиться видеть так же как Гипножаба, профессор собрал новый прибор, который эмулирует «гипнозрение»: каждый из четырёх его окуляров может принимать одно из n состояний, которые меняются по линейным законам. Фарнсворт провёл серию экспериментов и для каждого из них построил диаграмму, на которой для всех возможных состояний прибора отметил, могут ли глаза Гипножабы принимать состояния, похожие на состояния окуляров. Помогите профессору автоматизировать этот процесс.

Один эксперимент описывается 9 целыми числами: a₀, b₀, c₀, d₀, Δa, Δb, Δc, Δd, q. Для всех целых значений j от 0 до q−1 окуляры последовательно принимают состояния

Для каждого состояния прибора (a_j, b_j, c_j, d_j) требуется определить, могут ли глаза Гипножабы принимать такое состояние (s_i, t_i), что

В первой строке записаны целые числа n и m — количество состояний глаз Гипножабы и количество законов их поведения (1 ≤ n ≤ 5000, 1 ≤ m ≤ 1000). В каждой из следующих m строк записаны целые числа s₀, t₀, Δs, Δt, k, задающие закон изменения состояний глаз (0 ≤ s₀, t₀, |Δs|, |Δt| ≤ n−1; 1 ≤ k ≤ 567).

В следующей строке записано целое число p — количество экспериментов (1 ≤ p ≤ 345). В каждой из следующих p строк записаны целые числа a₀, b₀, c₀, d₀, Δa, Δb, Δc, Δd, q, описывающие эксперимент (0 ≤ a₀, b₀, c₀, d₀, |Δa|, |Δb|, |Δc|, |Δd| ≤ n−1; 1 ≤ q ≤ 345).

Выведите p строк: по одной на каждый эксперимент. Для одного эксперимента вычислите его результат — набор чисел x_j для j = 0, 1, …, q−1, где x_j = 1, если глаза Гипножабы могут принимать подходящее состояние для соответствующего состояния прибора, и x_j = 0 в противном случае. Если q ≤ 20, выведите все x_j подряд без пробелов. Если q > 20, выведите одно число, равное