Fişierul intrare/ieşire:	mario2.in, mario2.out	Sursă	Lot Juniori Deva 2013, baraj 1
Autor	Cristina Iordaiche	Adăugată de	Amalia Rebegea •amaliareb
Timp execuţie pe test	0.1 sec	Limită de memorie	8192 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Mario2

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. Se considera ca ajunge pe o platforma daca o intalneste in macar un punct, chiar si extremitate.
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 mario2.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 paltforme;
- de pe următoarele N linii câte trei numere naturale (h_p, x1, x2) cu semnificaţia: la înălţimea hp faţă de sol se află o platformă orizontală cu extremitatea stângă în x1 şi extremitatea dreaptă în x2.

Date de ieşire

În fişierul mario2.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

• 1 ≤ N ≤ 10 000
• 0 < H, h_p, h_M ≤ 20 000 (h_M > h_p)
• 0 < x_M, x1, x2 ≤ 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⁶³
• x1 < x2

Exemplu

Cum se trimit solutii?