Remakes#1136
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, a Committee for Combating Plagiarism and Remakes in Modern Popular Music was established. Today, the Committee received a new piece, and the head of the Committee suspects it may contain a motif from a famous song. However, because musical works and motifs can be quite large, 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).
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 (1 \leq M \leq 1000). The second line provides the sequence of notes of the motif. Each note is an integer in the range to , 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 (0 \leq N \leq 1000000). The fourth and last line of the test contains the sequence of notes of the piece.
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.
Example 1