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

if then return
else if then return
else return .

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 .
Na przykład dla ciągu mamy: Dla bardzo dużych danych program obliczający funkcję bezpośrednio z definicji jest zdecydowanie zbyt wolny. Twoim zadaniem jest jak największe przyspieszenie obliczania tej funkcji.

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.