Ремейки#1136
Деякі сучасні композитори люблять використовувати у своїх творах мотиви, які вже набули популярності. Щоб запобігти появі таких псевдо-нових пісень на сцені, було створено Комітет із Боротьби з Плагіатом і Ремейками в Сучасній Популярній Музиці. Сьогодні Комітет отримав новий твір, і голова Комітету підозрює, що в ньому може міститися мотив з відомої пісні. Однак, оскільки музичні твори та мотиви можуть бути досить великими, перевірити наявність плагіату без комп'ютера дуже складно. Завдання полягає у визначенні, чи містить заданий твір певний мотив як фрагмент, можливо, у транспонованій формі.
"Транспонований" означає, що до кожної ноти мотиву додається одна й та сама константа, позитивна або негативна. Наприклад, для мотиву (0, 5, 10, 6) транспонованими версіями є (5, 10, 15, 11) і (-2, 3, 8, 4).
У першому рядку вхідних даних вказується кількість тестів. Для кожного тесту у першому рядку дано довжину (кількість нот) мотиву (1 \leq M \leq 1000). У другому рядку подано послідовність з нот мотиву. Кожна нота — це ціле число в діапазоні від до , що вказує на висоту ноти (на скільки півтонів вона вище ноти "до першої октави"). У третьому рядку задано довжину музичного твору (0 \leq N \leq 1000000). У четвертому й останньому рядку тесту міститься послідовність нот твору.
Для кожного тесту виведіть число 0, якщо твір не містить мотив (навіть у транспонованій формі), або число 1, якщо твір містить мотив.
Приклад 1