Przyspieszenie algorytmu

Limit pamięci: 64 MB

Bajtazar musi za karę obliczyć pewną paskudną i tajemniczą funkcję logiczną , która dla dwóch ciągów liczb naturalnych ,\ jest zdefiniowana w następujący sposób:

boolean

W powyższym zapisie:

• oznacza zbiór złożony ze wszystkich liczb ciągu (ignorujemy powtórzenia i kolejność liczb),
• jest najdłuższym prefiksem (początkowym fragmentem) ciągu , dla którego ,
• jest najdłuższym sufiksem (końcowym fragmentem) ciągu , dla którego ,
• oznacza koniunkcję logiczną, - prawdę, - fałsz, a - liczność zbioru .

Napisz program, który wczyta ze standardowego wejścia kilka par ciągów i wypisze na standardowe wyjście wartości dla każdej pary wczytanych ciągów.

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą (), oznaczającą liczbę par ciągów do przeanalizowania. Kolejne wierszy zawiera opisy przypadków testowych. Pierwszy wiersz każdego opisu zawiera dwie liczby całkowite oraz (), oddzielone pojedynczym odstępem i oznaczające długości pierwszego i drugiego ciągu. Drugi wiersz zawiera liczb całkowitych (), pooddzielanych pojedynczymi odstępami i opisujących ciąg . Trzeci wiersz zawiera liczb całkowitych (), pooddzielanych pojedynczymi odstępami i opisujących ciąg .

Wyjście

Wyjście powinno się składać z wierszy; -ty wiersz (dla ) powinien zawierać jedną liczbę całkowitą - 0 lub 1 - oznaczającą wartość wyrażenia dla -tego przypadku testowego.

Przykład

Dla danych wejściowych:

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

poprawną odpowiedzią jest:

0
1

Autorzy zadania: Jakub Radoszewski, Wojciech Rytter.