🥵index

Врачара Миљана позната је по својим предсказањима о такмичењима из програмирања. Њена стручна област је погађање да ли ће Тајна Комисија прихватити неку такмичарску жалбу.

Миљана има своју луду теорију: да постоји природан број $X$ који не зна, такав да Комисија прихвата жалбе сваких $X$ година, тј. ако је Комисија прихватила жалбу у години $A$ прва следећа година када ће прихватити жалбу је $A+X$, а такође значи да је Комисија прихватила жалбу у години $A-X$.

Тачно $T$ такмичара је дошло да се посаветује са Миљаном. Она је од сваког појединачно тражила да прикупи информације о ранијим жалбама како би јој помогли да нађе $X$. Сваки такмичар је изнео неке гласине које је чуо на Алгори. За $N$ различитих година $A_1, A_2, ..., A_N$ такмичар тврди да је Тајна Комисија прихватала жалбе. За $M$ различитих година $B_1, B_2, ..., B_M$ тачмичар тврди да Тајна Комисија није прихватала жалбе.

Како не би губила време, Врачара Миљана је питала вас, такмичара који се неће жалити, да за сваког од $T$ такмичара одредите да ли постоји $X$ тако да су све гласине које је чуо тачне, односно да су жалбе прихваћене у годинама $A_1, A_2, ..., A_N$, а нису у годинама $B_1, B_2, ..., B_M$, пратећи Миљанину теорију да се жалбе прихватају сваких $X$ година.

Опис улаза

У првој линији улаза налази се број $T$ -- број такмичара који су се јавили Врачари Миљани.

За сваког такмичара уносе се по још три линије: у првој линији се налазе $N$ и $M$ -- број гласина у којима су жалбе прихваћене и број гласина у којима су жалбе одбијене; у другој линији налази се $N$ целих бројева, низ $A_1, A_2, ..., A_N$ -- године у којима су, по гласинама, прихваћене жалбе; у трећој линији налази се $M$ целих бројева, низ $B_1, B_2, ..., B_M$ -- године у којима су, по гласинама, одбијене жалбе.

Опис излаза

На стандардни излаз испишите $T$ бројева -- за сваког такмичара, у новом реду, исписати $1$ ако постоји $X$ које је у складу са његовим гласинама, односно исписати 0 у супротном.

Ограничења

• $1 \leq T \leq 5$

За сваког од $T$ такмичара важи:

• $2 \leq N, M \leq 75000$

• $1 \leq A_i, B_i \leq 10^{18}$

• $A_i \neq A_j$, за $i \neq j$

• $B_i \neq B_j$, за $i \neq j$

• $A_i \neq B_j$, за свако $i, j$

Тест примери су подељени у 4 дисјунктних група:

• У тест примерима вредним $10$ поена: $A_i, B_i, N, M \leq 3000$

• У тест примерима вредним $10$ поена: $N = 2$

• У тест примерима вредним $30$ поена: $A_i, B_i \leq 10^6$

• У тест примерима вредним $50$ поена: Без додатних ограничења

Примери

Пример 1

Улаз

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

Излаз

1
0
1
1

Објашњење

За првог такмичара могуће је узети $X = 3$ тако да задовољи све гласине. За другог такмичара немогуће је наћи $X$. За трећег такмичара могуће је узети $X = 12$.