eolymp
bolt
Try our new interface for solving problems
Problems

Ремейки

Ремейки

Time limit 2 seconds
Memory limit 122 MiB

Некоторые современные композиторы любят использовать в своих произведениях ставшие уже популярными мотивы. Чтобы пресечь появление на эстраде таких псевдоновых песен, при Министерстве Культуры был создан Комитет по борьбе с плагиатом и ремейками в современной популярной музыке. Как раз сегодня в Комитет поступило новое произведение Киркора Филиппова, в котором, как подозревает председатель Комитета, встречается мотив из одной известной песни Орбины Кристикайте. Однако поскольку музыкальные произведения и мотивы могут быть довольно большими, без компьютера проверить песню на плагиат достаточно трудно. Требуется проверить, встречается ли в заданном произведении как фрагмент определенный мотив (возможно транспонированный).

"Транспонированный"' означает, что некоторая положительная или отрицательная постоянная добавляется к каждой ноте мотива. Например, для мотива (0,5,10,6) транспонированным является (5,10,15,11), а также (-2,3,8,4).

Input data

В первой строке входного файла записано количество тестов. Первая строка каждого теста содержит длину (количество нот) искомого мотива M (1M1000). В следующей строке записана последовательность M нот мотива. Каждая нота представляет собой целое число из диапазона -100..100, и определяет высоту ноты (на сколько полутонов она выше, чем нота "до первой октавы"). В третьей строке задана длина музыкального произведения N (0N1000000). И, наконец, последняя (четвертая) строка теста представляет собой последовательность нот произведения.

Output data

В выходной файл нужно вывести для каждого теста число 0, если в произведении не встречается искомый мотив (даже транспонированный), или число 1, если произведение содержит мотив.

Examples

Input example #1
3
5
1 2 3 4 5
10
1 -1 1 2 3 4 5 0 1 2
3
4 5 7
7
-1 -2 -1 1 4 5 8
2
1 6
4
4 3 2 1
Output example #1
1
1
0