Problem description

Dane jest N przedziałów [l_i,r_i]. Dla każdego z nich stwierdź ile innych przedziałów zawiera oraz w ilu innych przedziałach się zawiera. Przedział [a,b] zawiera przedział [c,d] wtedy i tylko wtedy, gdy a ≤ c oraz b ≥ d.

Wejście

W pierwszym wierszu wejścia znajduje się jenda liczba naturalna N oznaczająca liczbę przedziałów. W następnych N wierszach znajdują się opisy kolejnych przedziałów. i-ty opis składa się z dwóch liczb całkowitych l_i, r_i oznaczającyh końce i-tego przedziału.

Wyjście

Należy wypisać dwa wiersze. W pierwszym wierszu należy wypisać N liczb, i-ta z nich powinna oznaczać liczbę przedziałów, które zawiera i-ty przedział. W drugim wierszu należy wypisać kolejne N liczb, i-ta z nich powinna oznaczać liczbę przedziałów, które zawierają i-ty przedział.

Ograniczenia

1 ≤ N ≤ 200 000, 1 ≤ l_i ≤ r_i ≤ 10⁹. Można założyć, że na wejściu każdy przedział pojawia się niewięcej niż raz, tzn. nie ma takich i ≠ j, że l_i = l_j oraz r_i = r_j.

Podzadania

Przykład

4
1 6
2 4
4 8
3 6

2 0 0 0 
0 1 0 1