Remakes
Some contemporary composers like to incorporate motifs in their works that have already gained popularity. To prevent such pseudo-new songs from appearing on stage, the Ministry of Culture has established a Committee for Combating Plagiarism and Remakes in Modern Popular Music. Today, the Committee received a new piece by Kirkor Filipov, and the head of the Committee suspects it may contain a motif from one of Orbina Kristikaite's famous songs. However, due to the potentially large size of musical works and motifs, checking for plagiarism without a computer is quite challenging. The task is to determine whether a given piece contains a specific motif as a fragment, possibly in a transposed form.
"Transposed" means that a constant, either positive or negative, is added to each note of the motif. For example, for the motif (0, 5, 10, 6), transposed versions include (5, 10, 15, 11) and (-2, 3, 8, 4).
Input
The first line of the input specifies the number of tests. For each test, the first line contains the length (number of notes) of the motif M (1 ≤ M ≤ 1000). The second line provides the sequence of M notes of the motif. Each note is an integer ranging from -100 to 100, indicating the pitch of the note (how many semitones it is above the note "C of the first octave"). The third line specifies the length of the musical piece N (0 ≤ N ≤ 1000000). The fourth and final line of the test contains the sequence of notes of the piece.
Output
For each test, output the number 0 if the piece does not contain the motif (even in a transposed form), or the number 1 if the piece does contain the motif.