Farmer John trouve que le trafic sur l’autoroute près de sa ferme a fortement augmenté. Pour vérifier, il veut installer des capteurs mesurant le débit sur un tronçon.

Mais en traversant la grange il trébuche et fait tomber sa boîte de capteurs dans une grande cuve de lait. Depuis ils donnent un intervalle au lieu d’une valeur exacte : $[7,13]$ signifie un débit au moins 7, au plus 13.

L’autoroute longe la ferme sur $N$ miles, dans un seul sens de 1 vers $N$. Il veut $N$ capteurs, un par mile. Sur une entrée, le capteur mesure approximativement le trafic entrant ; sur une sortie, le trafic sortant. Chaque tronçon a au plus une bretelle. Sans bretelle, il mesure la voie principale.

À partir des $N$ mesures, trouvez les intervalles possibles les plus précis avant le mile 1 et après le mile $N$, compatibles avec toutes les mesures.

Entrée

D’abord $N$ ($1\le N\le100$), puis $N$ lignes décrivant les tronçons dans l’ordre $1\ldots N$. Chaque ligne : on (entrée), off (sortie) ou none (aucune), puis deux entiers $0\ldots1000$ indiquant borne inférieure et supérieure. La mesure vient de la bretelle s’il y en a une, sinon de l’autoroute. Au moins un tronçon none.

Sortie

Première ligne : deux entiers de l’intervalle le plus précis avant le mile 1. Deuxième : après le mile $N$. Une solution existe toujours.

Exemples

Entrée 1

4
on 1 1
none 10 14
none 11 15
off 2 3

Sortie 1

10 13
8 12

Remarque

Les mesures $[10,14]$ et $[11,15]$ des tronçons 2 et 3 donnent $[11,14]$. Au mile 1 entre exactement 1 unité, donc avant $[10,13]$. Au mile 4 sortent 2 à 3 unités, donc après $[8,12]$.

Auteur du problème : Brian Dean