lupusor

Mielu de la bucătărie urmează să plece definitiv din întreprinderea unde lucrează. Tovarășul Lupușor de la Personal îi oferă o ultimă șansă: să îl învingă la un joc de cărți. Mielu acceptă, iar Lupușor îi prezintă regulile jocului, după cum urmează. Pe masă sunt așezate N cărți de joc numerotate de la 1 la N. Fiecare carte i, unde 1 ≤ i ≤ N, are înscrisă pe ea două numere întregi pozitive $a_i$ și $b_i$. Toate numerele înscrise pe cărți sunt distincte două câte două. La prima mutare a jocului Mielu alege o parte dintre cărți și le elimină din joc. El poate alege să nu elimine nicio carte, însă nu este permisă eliminarea tuturor cărților. La a doua mutare, Lupușor alege două cărți dintre cele rămase în joc, cu indicii inițiali i și j. Lupușor are voie inclusiv să aleagă aceeași carte de două ori (adică i = j). Dacă $a_i > b_j$ atunci Lupușor câștigă jocul, altfel câștigă Mielu. Lupușor este deosebit de viclean, așa că el întotdeauna va alege la a doua mutare valorile i și j astfel încât să câștige, dacă acest lucru este posibil.

Cerință

Mielu este acum pus în impas: pentru a-și păstra poziția, el va trebui să răspundă la două întrebări grele, date fiind N și valorile $a_1, ... a_N$ și $b_1, ... , b_N$ :

1. Care este numărul minim de cărți pe care le poate Mielu elimina la prima mutare astfel încât Lupușor să piardă jocul. Dacă acest lucru este imposibil, atunci răspunsul se consideră −1.
2. În câte feluri poate Mielu elimina cărți la prima mutare astfel încât Lupușor să piardă jocul. Răspunsul se cere modulo $10^9+7$.
   $\underline{\text{Atenție, în acest caz nu este necesară eliminarea unui număr minim de cărți!}}$

Se dă un număr C ∈ {1, 2}. Dacă C = 1 atunci Mielu va trebui să raspundă numai la întrebarea 1, altfel numai la întrebarea 2.

Mai grav! De M ori tovarășul director vine și schimbă valorile înscrise pe câte o carte din cele N. Mai exact, la a i-a modificare, pentru 1 ≤ i ≤ M, directorul schimbă valorile $a_{id_i}$ și $b_{id_i}$ înscrise pe cartea $id_i$ în $c_i$ și, respectiv, $d_i$. După fiecare astfel de modificare Mielu va trebui să raspundă din nou la întrebarea indicată de numărul C. Se garantează că după fiecare modificare valorile înscrise pe cărti rămân distincte două câte două.

Date de intrare

Pe prima linie a fișierului de intrare lupusor.in se află C. Pe a doua linie se află N. Pe a treia linie se găsesc numerele $a_1, ... , a_N$ , separate prin spații. Pe a patra linie se găsesc numerele $b_1, ... , b_N$ , separate prin spații. Pe a cincea linie se află M. Următoarele M linii descriu modificările dispuse de director: linia i conține numerele intregi pozitive $id_i, c_i, d_i$, separate prin spații, unde 1 ≤ i ≤ M.

Date de ieșire

În fișerul de ieșire lupusor.out se vor tipări M + 1 linii. Fiecare linie va conține un singur număr întreg, reprezentând răspunsul la prima, sau, respectiv, a doua cerință, în funcție de valoarea lui C. Prima linie va reprezenta răspunsul înainte de modificări, a doua linie răspunsul după prima modificare efectuată, și așa mai departe, linia i va reprezenta răspunsul după primele i − 1 modificări.

Restricții și precizări

• 1 ≤ N ≤ 100 000
• 0 ≤ M ≤ 100 000
• $1 ≤ a_i, b_i ≤ 2N + 2M$, oricare ar fi 1 ≤ i ≤ N.
• $1 ≤ c_i, d_i ≤ 2N + 2M$, oricare ar fi 1 ≤ i ≤ M.
• $1 ≤ id_i ≤ N$, oricare ar fi 1 ≤ i ≤ M.
• Fiecare număr 1 ≤ k ≤ 2N + 2M apare în exact unul dintre șirurile a, b, c sau d.

Subtask 1 (5 puncte)

• C = 1 și N, M ≤ 10

Subtask 2 (6 puncte)

• C = 1 și N, M ≤ 100

Subtask 3 (6 puncte)

• C = 1 și N, M ≤ 400

Subtask 4 (10 puncte)

• C = 1 și N, M ≤ 2 000

Subtask 5 (15 puncte)

• C = 1 și N, M ≤ 50 000

Subtask 6 (7 puncte)

• C = 1

Subtask 7 (5 puncte)

• C = 2 și N, M ≤ 10

Subtask 8 (7 puncte)

• C = 2 și N, M ≤ 100

Subtask 9 (7 puncte)

• C = 2 și N, M ≤ 400

Subtask 10 (13 puncte)

• C = 2 și N, M ≤ 2 000

Subtask 11 (13 puncte)

• C = 2 și N, M ≤ 50 000

Subtask 12 (6 puncte)

• C = 2

Exemple

lupusor.in

1
3
1 7 6
5 10 8
2
2 9 3
3 2 4

lupusor.out

1
2
1

lupusor.in

2
3
1 7 6
5 10 8
2
2 9 3
3 2 4

lupusor.out

4
2
3

lupusor.in

1
1
1
2
1
1 4 3

lupusor.out

0
-1

lupusor.in

2
1
1
2
1
1 4 3

lupusor.out

1
0

Explicații

În primul exemplu, cartea 1 are inițial înscrise pe ea numerele $a_1 = 1$ și $b_1 = 5$, pe care le vom scrie simplificat (1, 5), cartea 2 numerele (7, 10), iar cartea 3 numerele (6, 8). Avem C = 1, deci se răspunde numai la întrebarea 1. Observăm că dacă Mielu nu ar elimina nicio carte, atunci Lupușor ar câștiga alegând i = 2 și j = 1 deoarece $a_2 = 7 > 5 = b_1$. În schimb, dacă Mielu alege să elimine cartea 1, atunci în joc răman doar cărțile 2 și 3, cu valori (7, 10) și (6, 8). În acest caz Lupușor nu are cum să mai aleagă i și j dintre cărțile rămase astfel încât $a_i > b_j$ , deci câștigă Mielu.

După prima modificare, cartea 1 are înscrise pe ea numerele (1, 5), cartea 2 numerele (9, 3), iar cartea 3 numerele (6, 8). De acestă dată, este necesară eliminarea a două cărți: fie cărțile 1 și 2, fie cărțile 2 și 3.

După a doua modificare, cartea 1 are înscrise pe ea numerele (1, 5), cartea 2 numerele (9, 3), iar cartea 3 numerele (2, 4). De acestă dată, este suficientă doar eliminarea cărții 2.

Al doilea exemplu este identic cu primul, doar că se răspunde la întrebarea 2 (deoarece C = 2). Înainte de modificări există 4 moduri de a elimina o parte din cărți astfel încât Mielu să câștige:

1. Se elimină doar cartea 1;
2. Se elimină cărțile 1 și 2;
3. Se elimină cărțile 2 și 3;
4. Se elimină cărțile 1 și 3.

Observăm că eliminarea tuturor cărților se interzice prin regulile jocului.

După prima modificare există 2 moduri de a elimina o parte din cărți astfel încât Mielu să câștige:

1. Se elimină cărțile 1 și 2;
2. Se elimină cărțile 2 și 3.

După a doua modificare există 3 moduri de a elimina o parte din cărți astfel încât Mielu să câștige:

1. Se elimină doar cartea 2;
2. Se elimină cărțile 1 și 2;
3. Se elimină cărțile 2 și 3.

Observăm că numai primul dintre aceste 3 moduri elimină un număr minim de cărți, însă pe noi ne interesează numărul total de moduri, indiferent dacă acestea elimină un număr minim de cărți sau nu.