English
Zadanie Przyspieszenie algorytmu (prz)
Algorithm Speedup
Memory limit: 64 MB
As a punishment for misbehaving, Byteasar is to calculate a certain mysterious and nasty
Boolean-valued function 
, which is defined for a pair of positive integer sequences
, 
as follows:
boolean 
then return 
else if
then return 
else return
.
Where:
-
denotes the set of members of the sequence 
(order and repetitions of elements are insignificant),
-
denotes the longest prefix (initial part of any length) of the sequence 
,
such that 
,
-
denotes the longest suffix (final part of any length) of the sequence 
,
such that 
,
-
denotes the logical conjunction, 
- true, 
- false,
and 
- cardinality of set 
.
we have:
For very large data a programme calculating values of the function 
directly from definition is too
slow by any standards.
Therefore you are to make these calculations as fast as possible.
Write a programme that
reads several pairs of sequences 
from the standard input and
prints out the values 
on the standard output for every input pair.
Input
The first line of the standard input contains one integer 
(
)
denoting the number of sequence pairs to analyse.
Next 
line hold descriptions of test cases.
The first line of each description contains two integers 
and 
(
) separated by a single space and denoting
the lengths of the first and second sequence, respectively.
The second line holds 
integers 
(
)
that form the sequence 
, separated by single spaces.
The third line holds 
integers 
(
),
that form the sequence 
, separated by single spaces.
Output
The output should consist of exactly 
lines; the 
-th line (for 
)
should contain a single integer - 0 or 1 -
the value of 
for 
-th test case.
Example
For the input data:
2 4 5 3 1 2 1 1 3 1 2 1 7 7 1 1 2 1 2 1 3 1 1 2 1 3 1 3
the correct result is:
0 1
Task authors: Jakub Radoszewski and Wojciech Rytter.