У нас є \(HW\) карток, які розташовані в матриці з \(H\) рядками і \(W\) стовпцями. Для кожного \(i=1, \ldots, N\), карта на \(A_i\) ряду і \(B_i\) стовпцю містить напис - число \(i\). На інших картках \(HW-N\) нічого не написано.

Ми будемо повторювати наступні два види операцій над цими картками доки зможемо.

• Якщо є рядок без пронумерованої картки, видаліть усі картки в цьому ряду та заповніть проміжок, зсунувши решту карт вгору.

• Якщо є стовпець без пронумерованої картки, видаліть усі картки в цій колонці та заповніть прогалину, перемістивши решту карток ліворуч.

Знайдіть положення кожної пронумерованої картки після завершення процесу, описаного вище.

Можна довести, що ці позиції однозначно визначаються без залежності від порядку, в якому виконуються операції.

Формат вхідних даних

Перший рядок містить цілі числа \(H,W,N\) (\(1 \le H,W \le 10^9\), \(1 \le N \le min(10^5,HW)\))

Наступні  \(N\) рядків містять цілі числа \(A_i, B_i\) (\(1 \le A_i \le H\), \(1 \le B_i \le W\))

Формат вихідних даних

У вихідний потік виведіть \(N\) рядків.

Якщо після завершення процесу карта з номером \(i\) знаходиться в \(C_i\) рядкц і \(D_i\) стовпці, то \(i\)-й рядок повинен містити \(C_i\) і \(D_i\) в такому порядку з пробілом між ними.

Примітка

До прикладу 1:

Нехай * представляє картку, на якій нічого не написано. Початкове розташування карток таке:

*****
****2
*1***
*****

Після закінчення процесу вони розташовуються таким чином:

*2
1*

Тут картка з 1 знаходиться в 2-му рядку і 1-му стовпці, а картка з 2 знаходиться в 1-му рядку і 2-му стовпці.

Приклад вхідних даних

4 5 2
3 2
2 5

Приклад вихідних даних

2 1
1 2

Приклад вхідних даних

1000000000 1000000000 10
1 1
10 10
100 100
1000 1000
10000 10000
100000 100000
1000000 1000000
10000000 10000000
100000000 100000000
1000000000 1000000000

Приклад вихідних даних

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