Program

Mihăiță, elevul talentat al exigentului profesor de muzică Jean Carapace, primește un program de studiu special, care constă în studierea în ordine a $N$ capitole, numerotate de la $1$ la $N$. Capitolul $i$ ($1 \leq i \leq N$) trebuie să fie studiat exact $z_i$ zile consecutive. Studiul capitolului $i$ ($1 \leq i \leq N$) trebuie să se termine cel târziu în ziua $t_i$. Pentru a finaliza cu succes programul de studiu, Mihăiță trebuie să studieze toate capitolele (se garantează că acest lucru este posibil).

Pe lângă muzică, Mihăiță iubește expedițiile montane. Prietenii îi fac $P$ propuneri, fiecare propunere conținând una sau mai multe expediții. Pentru fiecare expediție se cunoaște intervalul de timp [$a$, $b$] în care se desfășoară (începe în ziua $a$ și se termină în ziua $b$, inclusiv). O propunere se numeşte acceptabilă dacă Mihăiță poate să meargă în toate expediţiile din propunerea respectivă şi să finalizeze cu succes programul de studiu.

Cerință

Se cunosc programul de studiu, precum şi propunerile primite:

1. Determinați ziua numerotată cu valoarea maximă în care Mihăiță poate începe programul de studiu astfel încât să-l finalizeze cu succes, în cazul în care nu merge în nicio expediție.
2. Pentru fiecare propunere, determinați numărul maxim de expediţii care se suprapun în aceeaşi zi.
3. Pentru fiecare propunere, verificați dacă este acceptabilă, știind că nicio propunere nu conţine expediţii care se suprapun.

Date de intrare

Fişierul de intrare program.in conţine pe prima linie numărul natural $C$, reprezentând cerința care trebuie rezolvată ($1$, $2$ sau $3$). Pe a doua linie se află numărul natural $N$. Pe a treia linie se află $N$ numere naturale $z_1$ $z_2 \dots z_N$. Pe a patra linie se află $N$ numere naturale $t_1$ $t_2 \dots t_N$. Pe a cincea linie se află numărul natural $P$. Toate aceste valori au semnificația din enunț. Urmează descrierea celor $P$ propuneri, fiecare fiind descrisă pe câte 3 linii:

• pe prima linie numărul natural $M$, reprezentând numărul de expediții din propunere;
• pe a doua linie $M$ numere naturale $a_1$ $a_2 \dots a_M$, unde $a_i$ reprezintă ziua de începere a expediției $i$ ($1 \leq i \leq M$);
• pe a treia linie $M$ numere naturale $b_1$ $b_2 \dots b_M$, unde $b_i$ reprezintă ultima zi a expediției $i$ ($1 \leq i \leq M$).

Valorile scrise pe aceeaşi linie în fişierul de intrare, sunt separate prin câte un singur spaţiu.

Date de ieșire

Fişierul de ieşire program.out conţine o singură linie, pe care se afişează:

• dacă $C = 1$: un număr natural reprezentând ziua reprezentând răspunsul la cerința 1;
• dacă $C = 2$: $P$ numere naturale separate prin câte un spațiu, unde al $i$-lea număr reprezintă numărul maxim de expediții din propunerea $i$ ($1 \leq i \leq P$) care se suprapun în aceeaşi zi;
• dacă $C = 3$: $P$ numere naturale separate prin câte un spațiu, unde al $i$-lea număr este 1 dacă propunerea $i$ este acceptabilă sau $0$ în caz contrar ($1 \leq i \leq P$).

Restricții și precizări

• $1 \leq N, P, M \leq 200 \ 000$
• $1 \leq z_i, t_i\leq 10^9$, pentru $1 \leq i \leq N$
• $1 \leq a \leq b \leq 10^9$ pentru fiecare expediție din oricare propunere
• $1 \leq Vmax \leq 10^9$, unde $Vmax$ este maximul dintre $z_i$, $t_i$, $a$, $b$ pentru $1 \leq i \leq N$ şi $a$, $b$ din toate expedițiile.
• $1 \leq S \leq 200 \ 000$, unde $S$ este numărul total de expediții din toate cele $P$ propuneri
• Zilele sunt numerotate începând cu 1.

Exemplul 1

program.in

1
5
2 3 1 4 3 
5 7 10 14 20
1
1
1
1

program.out

3

Explicație

Cerința este $1$.
Ziua numerotată cu valoarea maximă în care poate fi început programul de studiu astfel încât să se finalizeze cu succes este $3$. Capitolul $1$ este studiat în zilele $3$, $4$. Capitolul $2$ este studiat în zilele $5$, $6$, $7$.

Exemplul 2

program.in

2
1
1 
1
2
3
3 16 9 
4 17 9
6
3 2 10 7 1 6  
8 10 16 12 3 14

program.out

1 4

Explicație

Cerința este $2$.
Pentru prima propunere, numărul maxim de expediții care au loc în aceeași zi este $1$, deoarece perioadele nu se suprapun.
Pentru a doua propunere răspunsul este $4$, deoarece expedițiile $2$, $3$, $4$ și $6$ se desfăşoară simultan în ziua $10$.

Exemplul 3

program.in

3
5
2 3 1 4 3 
5 7 10 14 20
2
3
3 16 9
4 17 9
3
16 10 1
18 11 2

program.out

1 0

Explicație

Cerința este $3$.
Prima propunere îi permite lui Mihăiță să parcurgă toate capitolele la timp:

A doua propunere nu îi permite lui Mihăiță să parcurgă toate capitolele la timp: