Problem description

W tym zadaniu celem jest odgadnąć wzór tajemniczej funkcji π.

O funkcji π wiadomo, że:

• przyjmuje tylko jeden parametr x: liczbę naturalną od 1 do N włącznie,
• zwraca jako wynik liczbę naturalną od 1 do N włącznie,
• dla każdych dwóch różnych parametrów, funkcja zwraca różne wartości (dla każdego 1 ≤ x₁ ≠ x₂ ≤ N zachodzi π(x₁) ≠ π(x₂)),
• dla każdej liczby naturalnej y od 1 do N włącznie, istnieje parametr x, że funkcja zwraca wynik y dla tego parametru (dla każdego 1 ≤ y ≤ N istnieje 1 ≤ x ≤ N, że π(x) = y).

Innymi słowy, funkcja π jest permutacją zbioru {1, 2, …, N}.

Otrzymujesz na wejściu liczbę naturalną N, wartości k oraz ℓ oraz dla każdej liczby naturalnej od 1 do N włącznie otrzymujesz dwie wartości: π^k(x) oraz π^ℓ(x). Dla przypomnienia: $f^n(x) = \underbrace{f(f(f(\ldots(f(}_n x))\ldots)))$.

Twoim celem jest obliczyć dla każdej liczby naturalnej x od 1 do N włącznie wartość π(x), czyli ustalić jawny wzór permutacji π.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N. W drugim wierszu wejścia znajdują się dwie liczby naturalne k oraz ℓ oddzielone pojedynczym odstępem. W kolejnych N wierszach znajdują się pary liczb naturalnych oddzielone pojedynczym odstępem. Liczby zapisane w (x+2)-gim wierszu określają kolejno wartości π^k(x) oraz π^ℓ(x).

Możesz założyć, że dane są tak dobrane, że rozwiązanie zadania istnieje.

Wyjście

Twój program powinien wypisać na wyjście ciąg N liczb naturalnych pooddzielanych pojedynczymi odstępami: x-ta liczba ma określać wartość π(x). Jeżeli istnieje wiele możliwych rozwiązań, Twój program może wypisać dowolne z nich.

Ograniczenia

1 ≤ N ≤ 500 000, 2 ≤ k, ℓ ≤ 10⁹.

Przykład

9
2 3
4 2
1 5
6 9
8 1
2 8
3 7
9 3
5 4
7 6

5 8 7 2 4 9 6 1 3