Miljana jósnő ismert a programozás versenyekkel kapcsolatos jóslatairól. Szakterülete az, hogy eltalálja vajon a Titkos Bizottság elfogad-e egy adott versenyzői panaszt.

Miljanának van egy őrült elmélete: létezik egy (számára ismeretlen) \(X\) természetes szám, amelyre érvényes, hogy a Bizottság elfogadja a panaszokat minden \(X\) évben. Ez azt jelenti, hogy ha a Bizottság elfogadta a panaszt \(A\) évben, akkor az első következő év, amikor elfogadja a panaszt az \(A+X\) év lesz.

Pontosan \(T\) versenyző jött el Miljanához, hogy tanácsot kérjen tőle. Ő egyenként mindegyiket megkérte, hogy gyűjtsön információkat a korábbi panaszokról, hogy megtalálja az \(X\) értékét. Minden versenyző átadott neki egy sor információt azokból a híresztelésekből, amelyeket az Algorán hallottak. \(N\) különböző évre, \(A_1, A_2, ..., A_N\) évekre az adott versenyző azt állította, hogy a Titkos Bizottság elfogadta a panaszokat. \(M\) különböző évre, \(B_1, B_2, ..., B_M\) évekre pedig az adott versenyző azt állította, hogy a Titkos Bizottság nem fogadta el a panaszokat.

Hogy ne vesztegesse az időt, Miljana jósnő titeket kérdez (akik nem fognak panaszt benyújtani), hogy eldöntsétek minden \(T\) versenyzőre található-e \(X\) úgy, hogy a híresztelések, amelyeket hallottak igazak, vagyis, hogy a panaszokat \(A_1, A_2, ..., A_N\) években elfogadták, és \(B_1, B_2, ..., B_M\) években nem fogadták el, követve természetesen Miljana elméletét, hogy a panaszokat minden \(X\) évben fogadják el.

Bemenet

A bemenet első sorában a \(T\) szám, vagyis azoknak a versenyzőknek a száma áll, akik jelentkeztek Miljanának.

Minden egyes versenyző esetében még három sort viszünk be. Az első sorban az \(N\) és \(M\) számok állnak. Ezek a számok az adott versenyző által közölt híresztelések számát jelölik, amelyekben a panaszok elfogadásra, illetve elutasításra találtak. A második sorban \(N\) egész szám az \(A_1, A_2, ..., A_N\) évek állnak, amelyekben a híresztelések szerint a panaszokat elfogadták, míg a harmadik sorban \(M\) egész szám a \(B_1, B_2, ..., B_M\) évek állnak, amelyekben a híresztelések szerint a panaszokat elutasították.

Kimenet

A szabványos kimeneten kiíratni \(T\) számot, minden egyes versenyzőre új sorban, mégpedig \(1\) - et, ha létezik \(X\) összhangban az ő híreszteléseivel, vagy 0 - át ellenkező esetben.

Korlátozások

• \(1 \leq T \leq 5\)

Minden ( \(T\) ) versenyzőre érvényes:

• \(2 \leq N, M \leq 75000\)
• \(1 \leq A_i, B_i \leq 10^{18}\)
• \(A_i \neq A_j\), ha \(i \neq j\)
• \(B_i \neq B_j\), ha \(i \neq j\)
• \(A_i \neq B_j\), minden \(i, j\) értékre

A tesztpéldák 4 független csoportba oszthatók:

• Tesztpéldák, melyek \(10\) pontot érnek: \(A_i, B_i, N, M \leq 3000\)
• Tesztpéldák, melyek \(10\) pontot érnek: \(N = 2\)
• Tesztpéldák, melyek \(30\) pontot érnek: \(A_i, B_i \leq 10^6\)
• Tesztpéldák, melyek \(50\) pontot érnek: nincs külön korlátozás.

Példák

1. példa

Bemenet

4
4 3
1 7 4 13
3 11 9
3 2
9 5 3
7 11
2 3
3 15
1 7 2
2 2
5643634654354 12346544323565
22341124534 7655867344

Kimenet

1
0
1
1

Magyarázat

Az első versenyző esetében az \(X = 3\) értékre a híresztelések igazak lesznek.

A második versenyzőre esetében nem létezik \(X\).

A harmadik versenyző esetében \(X = 12\).