autobuz

"Deja nu se mai poate cu copiii din generația $α$! Nu mai cedează nimeni locul în autobuz, prea multe plângeri!", afirmă primarul. Totuși, Dorel, președintele elevilor din generația $α$ s-a hotărât să îi demonstreze primarului că se înșeală, așa că a propus o nouă regulă pentru așezarea persoanelor în autobuz. Se vor așeza mai întâi persoanele speciale (cu disabilități sau care sunt însărcinate). Apoi, dacă mai rămân locuri, se vor așeza persoane în ordinea descrescătoare a vârstei lor. Dacă două persoane au aceiași vârstă, se va așeza oricare dintre ele. În fiecare autobuz se vor urca mai multe grupuri caracterizate prin: numărul de persoane, vârsta lor, respectiv dacă persoanele sunt speciale sau nu. În primă faza, Dorel este interesat de câte vârste distincte există în toate grupurile. Apoi, pentru mai multe autobuze caracterizate prin numărul de locuri, Dorel este interesat dacă toate persoanele speciale vor avea loc pe scaun sau nu. În cele din urmă îl intersează care este vârsta maximă a unei persoane care nu va lua loc pe scaun. Se garantează că cea mai în vârstă persoană NU este specială.

Cerință

• Determinați numărul de vârste distincte din toate grupurile.
• Determinați pentru mai multe autobuze dacă toate persoanele speciale vor avea loc pe scaun sau nu.
• Determinați pentru mai multe autobuze vârsta maximă a unei persoane care NU va lua loc pe scaun.

Date de intrare

Pe prima linie a fișierului de intrare autobuz.in se găsește $C$ reprezentând cerința, apoi $N$ reprezentând numărul de grupuri. Pe următoarele $N$ linii se regăsesc $3$ numere naturale separate prin câte un spațiu reprezentând numărul de persoane, vârsta, respectiv dacă persoanele sunt speciale sau nu. Dacă $C=2$ sau $C=3$, pe următoarea linie se va afla $Q$ reprezentând cele $Q$ autobuze. Apoi, pe următoarele $Q$ linii se va afla câte un număr, reprezentând numărul de locuri din fiecare autobuz.

Date de ieșire

Pe prima linie a fișierului de ieșire autobuz.out se va găsi un singur număr, reprezentând răspunsul la cerința dată. Dacă $C=1$ se va afișa numărul de vârste distincte din toate grupurile. Dacă $C=2$ se vor afișa $Q$ numere separate printr-un spațiu, cel cu indicele $i$ reprezentând dacă toate persoanele speciale pot lua loc pe scaun în autobuzul cu indicele $i$ ($1$ dacă se poate, iar $0$ în caz contrar). Dacă $C=3$ se vor afișa $Q$ numere separate printr-un spațiu, cel cu indicele $i$ reprezentând vârsta maximă a unei persoane care nu va lua loc pe scaun în autobuzul cu indicele $i$ (Se garanteză că în orice autobuz va exista o perosană care rămâne în picioare).

Restricții și precizări

• Un grup este caracterizat de 3 valori: $nr_i,$ $v_i,$ $s_i$
• $1 \leq nr_i \leq 1 \ 000 \ 000 \ 000 , 1\leq v_i \leq 150, 0 \leq s_i \leq 1$
• Dacă $s_i$ are valoarea $0$, toate persoanele din acel grup nu sunt speciale.
• Dacă $s_i$ are valoarea $1$, toate persoanele din acel grup sunt speciale
• Un autobuz este caracterizat de numărul de locuri pe scaun. Fie acesta $a_i$
• $1 \leq a_i \leq 1 \ 000 \ 000 \ 000$
• $2 \leq N \leq 5 \ 000$
• $1 \leq Q \leq 400 \ 000$
• Se garanteză că în orice autobuz va exista o perosană care rămâne în picioare

  #	Punctaj	Restricții
  1	5	$C=1, 1 \leq N \leq 500$
  2	10	$C=1$
  3	10	$C=2, 1\leq N,Q \leq 5 \ 000$
  4	10	$C=2$
  5	15	$C=3, nr_i=1, 1 \leq i \leq N$
  6	15	$C=3, 1\leq Q \leq 80 \ 000$
  7	15	$C=3, 1\leq Q \leq 150 \ 000$
  8	20	$C=3$

Exemplul 1

autobuz.in

1 4
2 20 0
2 60 1
1 75 0
3 60 0

autobuz.out

3

Explicație

Există în total $3$ vârste distincte: $20$, $60$, $75$.

Exemplul 2

autobuz.in

2 4
2 20 0
1 60 1
1 75 0
1 60 1
2
1 
2

autobuz.out

0 1

Explicație

În total sunt 2 persoane speciale. Pentru autobuzul cu un singur scaun, nu ar avea loc ambele jos, deci se afișează 0.

Exemplul 3

autobuz.in

3 7
2 20 0
1 60 1
1 75 0
1 60 1
3 30 0
1 45 1
4 55 0
3
2 
4 
9

autobuz.out

75 55 30

Explicație

Pentru primul autobuz, se așează două din cele $3$ persoane speciale, iar cea mai în vârstă persoană care rămâne în picioare are $75$ de ani (mereu printre persoanele cu cea mai înaintată vârstă se află o persoană care să nu fie specială). Pentru al treilea autobuz se vor așeza cele $3$ persoane speciale, cea de $75$ de ani, cele $4$ de $55$ de ani și o parte din cele de $30$ de ani. Prin urmare răspunsul este $30$.