3. Havo sem, havo tam

Julka má veľa psíkov. A ono je to veľmi super vec, až do momentu, keď s toľkými psíkmi musí ísť von. Tak si vymyslela takýto plán: Keďže býva v dome s veľkou záhradou, tak len skontroluje, či je poriadne zatvorená brána a vždy keď nejaký psík chce ísť von, tak ho pustí, nech si behá po dvore. Chvíľu to fungovalo fajn, ale potom zistila, že musí stále sledovať, či nejaký psík nechce ísť von alebo dnu. Dvierka pre psíky ešte nemá namontované. Po pár dňoch si však všimla, že každý psík ide von len jeden krát za deň a to vždy v rovnakom čase a na rovnako dlho. Julka si zapísala tento interval pre každého psíka a teraz by si chcela nakresliť rozvrh časov. Na to ale potrebuje vedieť, aké široké stĺpčeky môže kresliť. Bohužial má Julka veľmi veľa úloh a fakt veľa psíkov, tak nemá čas si to sama spočítať. Pomôžete jej?

Úloha

Rozvrh má jeden stĺpec pre celý deň, ktorý je rozdelený po milisekundách. V tomto rozvrhu budeme značiť intervaly jednotlivých psíkov. Ak sa však dva intervaly prekrývajú, musíme každý zaznačiť len na polovicu stĺpca, ak sú 3 tak na tretinu a tak ďalej (viď obrázok). Julka dáva veľký dôraz na konzistenciu, takže ak sa dva intervaly niekde prekrývajú, musia byť ich časti v rozvrhu rovnako široké. Stĺpček pre jeden interval navyše musí byť v každom úseku rovnako široký (nemôže niekde byť širší, lebo je tam viac intervalov a niekde užší, lebo je tam menej intervalov). Vašou úlohou je pre každý interval vypísať, akú časť stĺpčeka zaberie v rozvrhu.

Formát vstupu

Na prvom riadku vstupu sa nachádza celé číslo \(n\) – počet psíkov. Nasleduje \(n\) riadkov, kde každý z riadkov obsahuje dve celé čísla \(s_i\) a \(e_i\), pričom \(s_i\) je čas vypustenia \(i\)-teho psíka do záhrady a \(e_i\) je čas návratu \(i\)-teho psíka do domu, \(0 \leq s_i < e_i < 10^9\), psík je vonku počas intervalu \(\langle s_i, e_i )\).

Formát výstupu

Vypíšte \(n\) riadkov, na každom z nich jedno celé číslo \(a_i\) – \(i\)-ty psík zaberie v rozvrhu \(1/a_i\) stĺpčeka.

Hodnotenie

Sú 4 sady vstupov, v ktorých platia tieto obmedzenia:

Príklad

Input:

3
1 3
2 5
6 7

Output:

2
2
1

Input:

3
1 3
2 5
4 6

Output:

2
2
2

Keďže psíci 1 a 3 nie sú v záhrade naraz, vie ich Julka vyznačiť do rovnakého stĺpca.