Bản đồ sân trường PTNK là một hình chữ nhật kích thước ~m×n~ được chia thành lưới ô vuông đơn vị ~m~ hàng ~n~ cột. Các hàng của lưới được đánh số từ 1 tới ~m~ và các cột của lưới được đánh số từ 1 tới ~n~, ô nằm ở hàng ~i~, cột ~j~ được gọi là ô ~i,j~. Bam giám hiệu quyết định đặt ~k~ khu vui chơi vào một số ô của lưới, mỗi khu vui chơi nằm hoàn toàn trong một ô và có thể có nhiều khu vui chơi nằm trong cùng một ô.
Hệ thống chiếu sáng của công viên gồm có m đèn loại ~A: a_1,a_2,…,a_m~ và ~n~ đèn loại ~B: b_1,b_2,…,b_n~. Đèn ai có thể chiếu sáng tất cả các ô trên hàng i và đèn bj có thể chiếu sáng tất cả các ô trên cột ~j (1≤i≤m;1≤j≤n)~.

Yêu cầu:

Hãy bật sáng một số ít nhất các đèn để chiếu sáng toàn bộ các ô có khu vui chơi.

Dữ liệu:

Dòng 1: Chứa ba số nguyên dương ~m,n,k~
~k~ dòng tiếp theo, dòng thứ ~i~ ghi chỉ số hàng và chỉ số cột của khu vui chơi thứ ~i~.

Kết quả:

Dòng 1 ghi số đèn loại ~A (p)~ và số đèn loại ~B (q)~ cần bật sáng
Dòng 2 ghi chỉ số của ~p~ đèn loại ~A~ được bật sáng, tiếp theo là chỉ số của ~q~ đèn loại ~B~ được bật sáng.

Giới hạn:

~n, m, k \leq 10^5~.

Input

5 5 8
1 1
1 2
1 3
2 3
3 3
4 4
4 5
5 4

Output

2 2
1 4 3 4

Giải thích: