Ultimul sezon rece a fost unul cu multa zăpadă căzută în zona montană, prin urmare magazinul de articole sportive din stațiunea de schi Semenic a avut vânzări mari, mai ales de clăpari (bocanci speciali pentru schiat). Acum fiind sfârșit de sezon, angajații magazinului constată că le-au rămas N cutii goale în care au fost ambalate perechile de clăpari vândute. Aceste cutii au forma unui paralelipiped dreptunghic la care fața superioară constituie capacul. Capacul și (evident) fața opusă capacului sunt de formă pătrată, iar înălțimea este una oarecare, ea depinzând de modelul de clăpari. La unele cutii capacul este prezent, la altele capacul a dispărut.

Aceste cutii trebuie predate unei firme de reciclare, dar până ajunge mașina pentru reciclat în Semenic, cutiile trebuie depozitate. Prin urmare unul dintre angajații magazinului primește sarcina să depoziteze cutiile punându-le una peste alta sub forma unui turn. Angajatul ia cutiile în ordinea în care le găsește în magazin și le pune una peste alta. Pentru a asigura o oarecare stabilitate a turnului, el le așează astfel încât axele care unesc centrul capacului cu centrul feței opuse capacului de la fiecare cutie să fie coliniare. Cutiile sunt astfel lăsate pe rând să cadă de la o înălțime suficient de mare, cu fețele laterale perpendiculare pe podea și paralele cu cele ale cutiilor deja plasate, până când întâlnesc una dintre aceste cutii sau podeaua. În ceea ce privește așezarea cutiilor care au capacul lipsă, angajatul le așează fie cu golul format prin lipsa capacului în sus, fie în jos.

Cerința

Cunoscând N (numărul de cutii din magazin), ordinea în care cutiile sunt așezate în turn, iar pentru fiecare cutie latura capacului, înălțimea cutiei și dacă are capac sau, în cazul în care capacul lipsește, dacă cutia este așezată cu golul în sus sau cu golul în jos determinați:

• înălțimea turnului astfel format;
• numărul de cutii ale căror fețe laterale sunt vizibile dacă se privește turnul din lateral.

Date de intrare

Pe prima linie a fișierului de intrare schi.in se află numărul C, număr care poate fi 1 sau 2 și reprezintă cerința care trebuie rezolvată.

Pe ce de-a doua linie se află numărul natural N, reprezentând numărul de cutii care sunt așezate în turn.

Pe fiecare dintre următoarele N linii se află câte trei valori L, H și M, separate prin câte un spațiu. Valorile de pe linia i + 2 (1 ≤ i ≤ N) reprezintă informații referitoare la cea de-a i-a cutie adăugată în turn, și anume:

• L – latura capacului cutiei;
• H – înălțimea cutiei;
• M – o valoare egală cu 0, 1 sau 2, având următoarea semnificație: M = 0 – cutia are capacul lipsă și este așezată cu golul în jos; M = 1 – cutia are capac; M = 2 – cutia are capacul lipsă și este așezată cu golul în sus.

Date de ieșire

Dacă C este 1, fișierul de ieșire schi.out va conține pe prima linie răspunsul pentru cerința 1 (înălțimea turnului format). Dacă C este 2, fișierul de ieșire schi.out va conține pe prima linie răspunsul pentru cerința 2 (numărul de cutii ale căror fețe laterale sunt vizibile dacă se privește turnul din lateral).

Restricții și precizări

• 1 ≤ N ≤ 200.000.
• Dimensiunile cutiilor sunt numere naturale din intervalul [1, 1.000.000.000].
• Laturile capacelor cutiilor sunt distincte două câte două.
• Grosimea pereților care formează fețele cutiilor (inclusiv capacul) este neglijabilă.
• Construcția turnului se realizează pe o podea plană de dimensiuni infinite.
• Pentru 12 puncte, C = 1 și N ≤ 2000
• Pentru 12 puncte, C = 2 și N ≤ 2000
• Pentru 8 puncte, C = 1 și nu avem nicio cutie așezată cu golul în sus
• Pentru 8 puncte, C = 2 și nu avem nicio cutie așezată cu golul în sus
• Pentru 8 puncte, C = 1 și nu avem nicio cutie așezată cu golul în jos
• Pentru 8 puncte, C = 2 și nu avem nicio cutie așezată cu golul în jos
• Pentru 22 puncte, C = 1
• Pentru 22 puncte, C = 2

Exemplul 1:

schi.in

1
5
20 3 2
3 7 1
9 1 1
11 5 1
12 6 0

schi.out

13

Explicație

Înălțimea turnului de cutii este 13.

Exemplul 2:

schi.in

2
5
20 3 2
3 7 1
9 1 1
11 5 1
12 6 0

schi.out

13

Explicație

Înălțimea turnului de cutii este 13. Privind din lateral sunt vizibile 3 cutii, și anume cele care au capacele cu laturile 20, 3 și 12.