Problem description
Dane jest N przedziałów [li,ri]. 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 li, ri 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 ≤ li ≤ ri ≤ 109. 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 li = lj oraz ri = rj.
Podzadania
| Podzadanie | Warunki | Punkty |
|---|---|---|
| 1 | N ≤ 4 000 | 20 |
| 2 | 1 ≤ li ≤ ri ≤ 1 000 000 | 50 |
| 3 | brak dodatkowych ograniczeń | 30 |
Przykład
| Wejście | Wyjście | |
|
|