Деяка країна має \(N\) областей та \(M\) міст, які належать до цих областей. Місто \(i\) засноване у році \(Y_i\) і належить до області \(P_i\). Можна припустити, що немає кількох міст, які засновані в одному році. Кожному місту було вирішено присвоїти 12-значний ідентифікаційний номер. Якщо місто \(i\) є \(x\)-м містом, що входить до складу області \(i\), то перші шість цифр ідентифікаційного коду міста \(i\) - \(P_i\), а останні шість цифр коду - \(x\). Якщо \(P_i\) або \(x\) (обо обидва) мають менше шести цифр, то зліва слід приписати певну кількість нулів щоб вийшло шість цифр. Знайдіть ідентифікаційні номери для всіх міст. Деякі області можуть не мати у своєму складі міст.

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

Перший рядок вхідного потоку містить два цілі числа \(N, M\) (\(1 \le N,M \le 10^5\)).

Наступні M рядків містять по два цілі числа \(P_i, Y_i\) (\(1 \le P_i \le N\), \(1 \le Y_i \le 10^9\)), які розділяються пропуском. \(Y_i\) є унікальним.

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

У вихідний потік вивести ідентифікаційні коди міст в окремих рядках.

Примітка

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

Оскільки місто 1 є другим заснованим містом серед міст, що належать до області 1, його ідентифікаційний номер 000001000002.

Оскільки місто 2 є першим заснованим містом серед міст, що належать до області 2, його ідентифікаційний номер 000002000001

Оскільки місто 3 є першим заснованим містом серед міст, що належать до області 1, його ідентифікаційний номер 000001000001.

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

2 3
1 32
2 63
1 12

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

000001000002
000002000001
000001000001

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

2 3
2 55
2 77
2 99

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

000002000001
000002000002
000002000003

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

4 10
3 254
1 316
2 43
2 91
2 3535
3 2018
4 112
1 1
2 53
4 5235

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

000003000001
000001000002
000002000001
000002000003
000002000004
000003000002
000004000001
000001000001
000002000002
000004000002