Ron

Ron Weasley dorește să-l ajute pe Harry Potter să construiască baghete magice. Hermione este plecată, așa că Ron trebuie să se descurce singur și știm cum ies vrăjile lui... Din acest motiv, are nevoie de ajutorul tău. Ron are crengi de soc de diferite lungimi și o riglă magică marcată, în dreptul fiecărui centimetru, cu numere naturale consecutive, începând cu $1$. Un număr natural aflat pe rigla magică este fermecat dacă are proprietatea că este obținut prin ridicarea la puterea a doua a unui număr prim. Puterea unei crengi este egală cu numărul de numere fermecate acoperite de aceasta pe rigla magică. Pentru a crea o baghetă, Ron așază crengile pe riglă cu capătul din stânga al fiecărei crengi exact în dreptul numărului natural marcat pe riglă. În cazul în care două sau mai multe crengi se suprapun sau se ating se formează o singură baghetă. Dacă două sau mai multe crengi de soc așezate pe riglă nu se suprapun și nu se ating, se obțin baghete diferite. De exemplu, dacă Ron așază pe riglă o creangă de soc de lungime $7$ centimetri, cu capătul din stânga la poziția marcată cu numărul $4$, creanga va avea puterea $2$ (fiindcă va acoperi numerele fermecate $4$ și $9$). Dacă mai așază pe riglă o altă creangă de lungime $2$ centimetri, cu capătul din stânga la poziția marcată cu numărul $11$, această creangă va avea puterea $0$ și cele două crengi așezate vor forma împreună o baghetă pentru că se ating. Dacă mai așază pe riglă o altă creangă, de lungime $1$ centimetru, cu capătul din stânga la poziția marcată cu numărul $14$, această creangă va avea puterea $0$ și va forma singură o baghetă pentru că nu se suprapune și nu se atinge de alte crengi.

Cerință

Scrieţi un program care, cunoscând numărul de crengi de soc și pentru fiecare dintre acestea poziția pe riglă la care se plasează capătul din stânga și lungimea crengii măsurată în centimetri, rezolvă următoarele două cerințe:

1. să se determine puterea cea mai mare pe care o are una dintre crengile folosite de Ron;
2. să se determine numărul de baghete magice realizate de Ron.

Date de intrare

Fişierul de intrare ron.in conţine pe prima linie numerele $c$ și $n$ reprezentând cerința care trebuie rezolvată ($1$ sau $2$), respectiv numărul de crengi de soc. Pe următoarele $n$ linii sunt descrise crengile de soc, câte o creangă pe o linie, sub forma a două numere naturale $poz$ și $l \ g$ reprezentând, în această ordine, numărul natural aflat pe rigla magică în dreptul căruia a fost așezat capătul din stânga al crengii, respectiv lungimea în centimetri a acesteia. Numerele scrise pe aceeaşi linie sunt separate prin câte un spaţiu.

Date de ieșire

Fișierul de ieșire ron.out va conţine o singură linie pe care va fi scris un număr natural reprezentând rezultatul la cerința $c$ din fişierul de intrare.

Restricții

• $2 \le n \le 50 \ 000$
• $1 \le poz, l \ g \le 10^{9}$

Exemple

ron.in

1 4
19 9
6 1
9 17
8 1

ron.out

2

ron.in

2 4
19 9
6 1
9 17
8 1

ron.out

2

Explicație

Prima creangă are puterea $1$ (acoperă numărul fermecat $25$), a doua creangă are puterea $0$, a treia creangă are puterea $2$ (acoperă numerele fermecate $9$ și $25$), iar a patra creangă are puterea $0$. Pentru primul exemplu ($c = 1$), puterea maximă a uneia dintre crengile folosite de Ron este $2$. Pentru al doilea exemplu ($c = 2$), se obțin două baghete: prima, a treia și a patra creangă realizează împreună o baghetă pentru că se suprapun sau se ating. A doua creangă realizează singură o baghetă.