Jako początkujący entuzjasta algorytmów, Mike nie radzi sobie najlepiej ze zbyt złożonymi systemami. Niestety, okazało się to dużym problemem w firmie, w której odbywa obecnie staż.

Projekt Mike'a polega na pracy przy firmowym Inteligentnym Klastrze Obliczeń Równoległych. To tylko wymyślna nazwa; w rzeczywistości system jest prostym harmonogramem zadań, obsługującym łącznie $n$ zadań. Niektóre zadania mogą zależeć od pomyślnego wykonania innych zadań, zanim będą mogły zostać uruchomione. Łącznie istnieje $m$ takich zależności.

Gwarantuje się, że nie ma żadnych (bezpośrednich ani pośrednich) zależności cyklicznych między zadaniami.

Po uruchomieniu systemu, wybiera on w inteligentny sposób kolejność wykonywania zadań tak, aby wszystkie zależności zostały spełnione (kolejność może się różnić między poszczególnymi uruchomieniami). Po wybraniu poprawnej kolejności, system rozpoczyna wykonywanie każdego z $n$ zadań w tej kolejności. Gdy system rozpoczyna wykonywanie zadania, wypisuje identyfikator zadania do pliku dziennika.

Niestety, dzisiaj był pierwszy dzień stażu Mike'a i nie był on zbyt ostrożny. W rezultacie przypadkowo uruchomił system $k$ razy równolegle. System zaczął chaotycznie uruchamiać zadania i wypisywać je do pliku dziennika. Teraz plik dziennika zawiera $n \cdot k$ identyfikatorów wszystkich wykonanych zadań. Identyfikatory zadań z tego samego uruchomienia zostały wypisane w kolejności ich wykonywania, ale dane wyjściowe z różnych uruchomień mogą być dowolnie przemieszane.

Twoim zadaniem jest ustalenie, które zadania zostały wykonane w każdym z $k$ uruchomień na podstawie informacji zawartych w pliku dziennika.

Wejście

Pierwsza linia wejścia zawiera trzy liczby całkowite $n, k, m$ ($1 \le n, k \le 500\,000$, $0 \le m \le 250\,000$, $n \cdot k \le 500\,000$), oznaczające liczbę zadań w systemie, liczbę uruchomień wywołanych przez Mike'a oraz liczbę zależności.

Kolejne $m$ linii zawiera parę liczb $a_i, b_i$ ($1 \le a_i, b_i \le n$, $a_i \neq b_i$, dla wszystkich $1 \le i \le m$) opisujących zależność typu: „zadanie $a_i$ musi zostać wykonane przed zadaniem $b_i$”.

Na końcu, ostatnia linia wejścia zawiera $n \cdot k$ liczb całkowitych $c_i$ ($1 \le c_i \le n$, dla wszystkich $1 \le i \le n \cdot k$), czyli identyfikatory zadań, które zostały wypisane w pliku dziennika, w kolejności ich wystąpienia.

Wyjście

Wypisz pojedynczą linię składającą się z $n \cdot k$ liczb całkowitych $r_i$ ($1 \le r_i \le k$, dla wszystkich $1 \le i \le n \cdot k$), oznaczających identyfikator uruchomienia odpowiadający każdemu z zadań w pliku dziennika. Mówiąc dokładniej, $r_i$ powinno być identyfikatorem uruchomienia odpowiadającym $i$-temu zadaniu, tak jak pojawia się ono w pliku dziennika.

Jeśli możliwe jest wiele rozwiązań, każde z nich jest akceptowane. Gwarantuje się, że dane wejściowe są poprawne i że rozwiązanie zawsze istnieje.

Przykład

Wejście 1

3 3 2
1 2
1 3
1 1 2 3 3 2 1 2 3

Wyjście 1

1 2 2 1 2 1 3 3 3