Ремейки
Некоторые современные композиторы любят использовать в своих произведениях ставшие уже популярными мотивы. Чтобы пресечь появление на эстраде таких псевдоновых песен, при Министерстве Культуры был создан Комитет по борьбе с плагиатом и ремейками в современной популярной музыке. Как раз сегодня в Комитет поступило новое произведение Киркора Филиппова, в котором, как подозревает председатель Комитета, встречается мотив из одной известной песни Орбины Кристикайте. Однако поскольку музыкальные произведения и мотивы могут быть довольно большими, без компьютера проверить песню на плагиат достаточно трудно. Требуется проверить, встречается ли в заданном произведении как фрагмент определенный мотив (возможно транспонированный).
"Транспонированный"' означает, что некоторая положительная или отрицательная постоянная добавляется к каждой ноте мотива. Например, для мотива (0,5,10,6) транспонированным является (5,10,15,11), а также (-2,3,8,4).
Входные данные
В первой строке входного файла записано количество тестов. Первая строка каждого теста содержит длину (количество нот) искомого мотива M (1 ≤ M ≤ 1000). В следующей строке записана последовательность M нот мотива. Каждая нота представляет собой целое число из диапазона -100..100, и определяет высоту ноты (на сколько полутонов она выше, чем нота "до первой октавы"). В третьей строке задана длина музыкального произведения N (0 ≤ N ≤ 1000000). И, наконец, последняя (четвертая) строка теста представляет собой последовательность нот произведения.
Выходные данные
В выходной файл нужно вывести для каждого теста число 0, если в произведении не встречается искомый мотив (даже транспонированный), или число 1, если произведение содержит мотив.