mario

Jocurile cu Mario sunt jocuri on-line pentru copii de toate vârstele. Acum, Mario-personajul din joc, are nevoie de ajutorul vostru pentru a ajunge din turnul castelului unde se află, la sol, unde îl așteaptă cu nerăbdare prințesa Peach. Coborârea din turn se face cu ajutorul unor platforme orizontale, de diferite lungimi, fiecare dintre ele aflându-se la o anumită înălțime față de sol. Deplasarea din turn spre sol se va face astfel:

• Mario își dă drumul în cădere liberă din turn și cade sub efectul greutății sale;
• dacă în cădere, el ajunge pe o platformă, se va deplasa pe suprafața acesteia spre unul din capetele din stânga sau din dreapta ale acesteia, urmând ca de acolo să procedeze la fel, lăsându-se din nou în cădere liberă spre sol.

Dacă Mario cade pe o distanță mai mare decât $H$, atunci își pierde toată energia și nu mai poate continua jocul.

Cerinţă

Cunoscând poziția în care se află Mario și modul de așezare al platformelor (date în coordonate carteziene), determinați numărul drumurilor distincte pe care le poate parcurge Mario pentru a ajunge la prințesă.

Date de intrare

Din fişierul mario.in se va citi:

• de pe prima linie trei numere naturale $h_M$, $x_M$ și $H$ reprezentând în ordine: înălțimea la care se află Mario față de sol, abscisa poziției sale și înălțimea maximă pe care o poate parcurge în cădere;
• de pe cea de-a doua linie un număr natural $N$ ce reprezintă numărul de platforme;
• de pe următoarele $N$ linii câte trei numere naturale $(h_p, x_1, x_2)$ cu semnificația: la înălțimea $h_p$ față de sol se află o platformă orizontală cu extremitatea stângă în $x_1$ și extremitatea dreaptă în $x_2$.

Date de ieșire

În fişierul mario.out se va scrie pe prima linie un singur număr natural reprezentând numărul drumurilor distincte pe care le poate parcurge Mario până la prințesă.

Restricții și precizări

• $1 \leq N \leq 10 \ 000$
• $0 < H, h_p, h_M \leq 20 \ 000$, $h_M > h_p$
• $0 < x_M, x_1, x_2 \leq 200 \ 000$
• Dacă există mai multe platforme la aceeași înălțime se garantează că ele nu se suprapun în niciun punct.
• Numărul drumurilor este întotdeauna mai mare decât $0$ și mai mic decât $2^{63}$.

Exemplu

mario.in

14 8 7
4
9 8 15
2 10 13
12 6 11
4 2 10

mario.out

3

Explicație

Turnul se află la înălțimea $14$ față de sol și are abscisa $8$. Mario poate coborî liber cel mult $7$ unități.

Există $4$ platforme: o platformă e situată la înălțimea $9$ față de sol și are extremitățile în $8$ și $15$. Altă platformă se află la înălțimea $2$ față de sol și are extremițățile în $10$ și $13$. Următoarea platformă se află la o înălțime de $12$ și are extremitatea stângă în $6$ iar cea dreaptă în $11$. Ultima platformă se află la $4$ unități față de sol și are extremitățile în $2$ și $10$.

Sunt $3$ drumuri distincte pe care Mario poate coborî din turn până la sol.