Pentru că este un bun sportiv și poate alerga constant cu metri pe secundă, Gigel și-a propus să câștige competiția semarun. Această competiție începe la momentul și constă în parcurgerea unui traseu de metri, ce conține semafoare.
Pentru fiecare semafor se cunosc:
- Distanța la care este poziționat față de punctul de start, exprimată în metri - ;
- Numărul de secunde pentru care acesta indică culoarea roșu - ;
- Numărul de secunde pentru care acesta indică culoarea verde - .
La începutul competiției toate semafoarele indică culoarea roșu, apoi alternează între roșu și verde.
La întâlnirea unui semafor, participanții trebuie să aștepte dacă acesta este roșu sau își schimbă culoarea din verde în roșu, și pot trece dacă acesta este verde sau își schimbă culoarea din roșu în verde. Este desemnat câștigător cel care parcurge distanța de la linia de start pană la final în cel mai scurt timp și fără a depăși secunde de la începutul competiției.
Este important de știut faptul că înainte de începerea competiției, fiecare participant trebuie să-și aleagă momentul (exprimat în secunde trecute de la începerea competiției) la care va începe parcurgerea traseului astfel încât să ajungă la final într-un interval de timp cat mai scurt.
Cerință
Deoarece Gigel știe că nu este important să ajungă primul la final, ci să parcurgă traseul într-un timp cat mai scurt, vă roagă să îl ajutați cu următoarea cerință: determinați momentele de timp pe care Gigel ar putea sa le aleagă pentru a începe parcurgerea traseului astfel încât să nu se oprească la niciun semafor și atunci când ajunge la final să nu fi trecut mai mult de secunde de la începutul competiției (momentul ).
Date de intrare
Pe prima linie a fișierului de intrare semarun.in se află numerele naturale , și . Pe a doua linie se află numărul natural , iar pe următoarele linii se specifică pentru fiecare semafor numerele naturale , și .
Date de ieșire
Pe prima linie a fișierului de ieșire semarun.out se va scrie numărul de soluții pentru cerința lui Gigel, iar pe a doua linie se vor scrie soluțiile separate printr-un spațiu, ordonate crescător.
Restricții și precizări
- ;
- ;
- ;
- ;
- ;
- Se garantează că pentru datele din fișierul de intrare există cel puțin o soluție;
- Toate soluțiile din fișierul de ieșire trebuie să fie numere naturale pozitive.
Exemplu
semarun.in
400 10 60
3
30 2 2
60 3 3
90 4 4
semarun.out
3
3 4 11
Explicație
Momentele de timp pe care Gigel le poate alege astfel încât să respecte cerința sunt: , sau secunde de la începerea competiției.
Dacă Gigel începe parcurgerea traseului după secunde de la start, acesta o să ajungă la cele trei semafoare în secundele , și , fix când acestea își schimbă culoarea din roșu în verde. La final acesta o sa ajungă în secunda , încadrându-se în limita a de secunde.
Pentru orice altă alegere față de cele menționate mai sus, Gigel ar întâlni cel puțin un semafor care ar indica culoarea roșu sau și-ar schimba culoarea din verde în roșu la întâlnirea acestuia, ori nu s-ar încadra în limita de timp.