Verseny
A csillagközi ürhajóversenyen N ürhajó indul. Az i-edik ürhajó folyamatosan Vi sebességgel halad. Mindegyik ürhajó adott, a startvonaltól jobbra mért Xi távolságról indul. A verseny a végtelenségig tart, azaz a gyorsabb ürhajók megelözik az elöttük indult lassabbakat. Az elözés abban az idöpontban történik, amikor a startvonaltól azonos távolságban vannak.
Azt szeretnénk tudni, hogy hány esetben fordul elö, hogy egy ürhajó megelöz egy másikat és meg kell adni idörendben az elsö legfeljebb 10000 elözést. Az ürhajók kezdetben a startvonaltól különbözö távolságra vannak. Sohasem fordulhat elö, hogy kettönél több ürhajó van ugyanabban a pozicióban.
Példa
Bemenet
A therace.in állomány elsö sorában az ürhajók N száma van (0<N<=250000). A következö N sor mindegyike két számot tartalmaz, egy ürhajó X kezdeti távolságát a startvonaltól és a V sebességét (0<=X<=1000000, 0<V<100). Az ürhajók a kezdöpozició szerinti sorrendben vannak, azaz X1<X2<...<XN.
Kimenet
A therace.out állomány elsö sora az elözések száma modulo 1000000 (1 millió) értéket tartalmazza. A következö sorok egy-egy elözést irnak le. Minden sor két egész számot tartalmazzon, az elsö annak az ürhajónak a sorszáma, amelyik elöz, a második pedig azé, amelyiket megelözi. Ha több elözés is van ugyanabban az idöpontban, akkor az elözést végzö ürhajó sorszáma szerinti sorrendben kell kiirni öket. Ha 10000-nél több elözés lenne, akkor csak az idörendben elsö 10000-et kell kiirni.
Megjegyzés
Ha az elözések száma helye, akkor 40 pontot kapsz. Ha az elözések is helyesek, akkor további 60 pontot kapsz.
Példa
therace.in	therace.out	
4
0 2
2 1
3 8
6 3	2
3 4
1 2