Enrica la formica si muove seguendo le linee di una griglia.
Ogni punto della griglia è identificato da una coppia di interi non negativi (x,y), dove il primo indica la coordinata X e il secondo indica la coordinata Y.
Il punto (0,0) è quello in basso a sinistra (vedi figura).

Enrica inizia il suo cammino da un certo punto di coordinate (0,Yin) e normalmente si sposta in orizzontale, da sinistra verso destra.
Lungo il suo percorso, però, può trovare degli ostacoli.
Gli ostacoli sono costituiti da segmenti verticali che si trovano sparsi sul percorso.

Quando Enrica arriva a un ostacolo, inizia a spostarsi verticalmente lungo l’ostacolo verso l’estremità più vicina dell’ostacolo stesso; se le estremità sono egualmente distanti, si muove sempre verso l’alto.
Raggiunta l’estremità dell’ostacolo, Enrica riprende a camminare orizzontalmente verso destra.

Una linea verticale delimita il campo da gioco: quando Enrica arriva alla linea verticale, si ferma.
Dovete trovare quanto è lungo il percorso compiuto da Enrica, e a quale altezza (coordinata Y) si trova Enrica alla fine del percorso.

File di input

Il file di input, di nome input.txt, è costituito da varie righe:

• sulla prima riga si trovano due numeri interi (separati da uno spazio) Yin e Xfin: il primo indica da quale coordinata Y parte Enrica, mentre il secondo indica a quale coordinata X si trova la linea verticale che delimita il campo di gioco; in altre parole, Enrica inizierà il suo cammino dal punto (0,Yin) e si fermerà in un qualche punto della forma (Xfin,Yfin) (dove Yfin è uno dei valori da determinare);
• sulla seconda riga si trova il numero intero N che rappresenta quanti sono gli ostacoli;
• su ciascuna delle successive N righe si trova la descrizione di un ostacolo; l’i-esimo ostacolo è descritto da tre interi Xi Yi Y'i, separati fra loro da uno spazio; Xi è la coordinata X a cui si trova l’ostacolo, mentre Yi e Y'i sono le due coordinate Y delle sue estremità.

File di output

Il file di output, di nome output.txt, è costituito da una singola riga, contenente due numeri interi, separati da uno spazio.
Il primo numero intero è la lunghezza L del percorso compiuto da Enrica; il secondo numero intero Yfin è la coordinata Y a cui si trova Enrica alla fine del suo percorso.

Assunzioni

Si fanno le seguenti assunzioni:

• 0 < Yin;
• 0 < X1 < X2 < ... < XN < Xfin;
• per ogni i vale che 0 < Yi < Y'i;
• 0 ≤ N ≤ 1000;
• nessuna delle variabili coinvolte in input o output avrà valore maggiore di 32000;

Esempio

Questo esempio corrisponde a quello mostrato in figura