Là một người đam mê thuật toán tập sự, không có gì ngạc nhiên khi Mike gặp khó khăn trong việc xử lý các hệ thống quá phức tạp. Thật không may, điều này đã trở thành một vấn đề lớn tại công ty nơi cậu đang thực tập.

Dự án được giao cho Mike liên quan đến việc mày mò với Cụm máy tính thông minh (Intelligent Cluster) phục vụ tính toán song song của công ty. Đây chỉ là một cái tên hoa mỹ; trên thực tế, hệ thống chỉ là một bộ lập lịch công việc đơn giản, xử lý tổng cộng $n$ công việc. Một số công việc có thể phụ thuộc vào việc thực hiện thành công các công việc khác trước khi có thể được thực hiện. Có tổng cộng $m$ phụ thuộc như vậy.

Đảm bảo rằng không có phụ thuộc vòng (trực tiếp hoặc gián tiếp) giữa các công việc.

Khi một lượt chạy được bắt đầu, hệ thống sẽ chọn một thứ tự để thực hiện các công việc này sao cho tất cả các phụ thuộc đều được thỏa mãn (thứ tự có thể thay đổi giữa các lượt chạy khác nhau). Sau khi chọn một thứ tự hợp lệ, hệ thống bắt đầu thực hiện từng công việc trong số $n$ công việc theo thứ tự đó. Khi hệ thống bắt đầu thực hiện một công việc, nó sẽ in ID của công việc đó vào một tệp nhật ký (log file).

Thật không may, hôm nay là ngày đầu tiên Mike thực tập tại công ty và cậu ấy đã không cẩn thận. Kết quả là, cậu ấy đã vô tình chạy hệ thống $k$ lần song song. Hệ thống bắt đầu khởi chạy các công việc một cách thất thường và in vào tệp nhật ký. Hiện tại, tệp nhật ký chứa $n \cdot k$ ID của tất cả các công việc đã được thực hiện. Các ID công việc từ cùng một lượt chạy đã được in theo thứ tự chúng được thực hiện, nhưng kết quả đầu ra từ các lượt chạy khác nhau có thể xuất hiện xen kẽ một cách tùy ý.

Nhiệm vụ của bạn là tìm ra những công việc nào đã được thực hiện trong mỗi lượt chạy trong số $k$ lượt chạy từ thông tin bên trong tệp nhật ký.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa ba số nguyên $n, k, m$ ($1 \le n, k \le 500\,000$, $0 \le m \le 250\,000$, $n \cdot k \le 500\,000$), là số lượng công việc trong hệ thống, số lượng lượt chạy mà Mike đã kích hoạt, và số lượng phụ thuộc.

$m$ dòng tiếp theo chứa một cặp số nguyên $a_i, b_i$ ($1 \le a_i, b_i \le n$, $a_i \neq b_i$, với mọi $1 \le i \le m$) mô tả một phụ thuộc dạng: “công việc $a_i$ phải được thực hiện trước công việc $b_i$”.

Cuối cùng, dòng cuối cùng của dữ liệu vào chứa $n \cdot k$ số nguyên $c_i$ ($1 \le c_i \le n$, với mọi $1 \le i \le n \cdot k$), là các ID công việc đã được in trong tệp nhật ký, theo thứ tự.

Dữ liệu ra

Xuất ra một dòng duy nhất gồm $n \cdot k$ số nguyên $r_i$ ($1 \le r_i \le k$, với mọi $1 \le i \le n \cdot k$), là ID lượt chạy tương ứng với mỗi công việc trong tệp nhật ký. Cụ thể hơn, $r_i$ phải là ID lượt chạy tương ứng với công việc thứ $i$, như nó xuất hiện trong tệp nhật ký.

Nếu có nhiều lời giải, bất kỳ lời giải nào cũng được chấp nhận. Đảm bảo rằng dữ liệu đầu vào là hợp lệ và luôn tồn tại một lời giải.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

1 2 2 1 2 1 3 3 3