Ở một đất nước, có \(n\) tỉnh và tổng cộng \(m\) thành phố thuộc các tỉnh đó. Thành phố thứ \(i\) được thành lập vào năm \(y_i\) và thuộc về tỉnh \(p_i\).

Giả sử không có hai thành phố nào được thành lập vào cùng một năm. Người ta quyết định phân bổ một số ID gồm 12 chữ số cho mỗi thành phố. Nếu thành phố thứ \(i\) được thành lập vào năm thứ \(x\) trong số các thành phố thuộc tỉnh \(p_i\) thì 6 chữ số đầu tiên của số ID của thành phố \(i\) là \(p_i\), và 6 chữ số cuối cùng của số ID là \(x\).

Ở đây, nếu \(p_i\) hoặc \(x\) (hoặc cả hai) có ít hơn 6 chữ số, các số 0 sẽ được thêm vào bên trái cho đến khi có đủ 6 chữ số. Tìm số ID cho tất cả các thành phố.

Lưu ý rằng có thể có một tỉnh không thuộc thành phố nào.

INPUT FORMAT

Dòng đầu tiên gồm hai số nguyên dương \(n, m(1 \leq n, m \leq 10^5)\).

\(m\) dòng tiếp theo, dòng thứ \(i\) gồm hai số nguyên dương \(p_i\) và \(y_i\) \((1 \leq p_i \leq n, 1 \leq y_i \leq 10^9)\).

OUTPUT FORMAT

In ra \(m\) dòng, dòng thứ \(i\) chứa ID của thành phố thứ \(i\).

Ví dụ 1:

Input

2 3
1 32
2 63
1 12

Output

000001000002
000002000001
000001000001

Ví dụ 2:

Input

2 3
2 55
2 77
2 99

Output

000002000001
000002000002
000002000003

Giải thích ví dụ mẫu

Ví dụ 1:

• Input:

  2 3 1 32 2 63 1 12

• Giải thích: Thành phố đầu tiên có tỉnh 1, thứ tự 1 là 000001, ID là 000001000002; thành phố thứ hai là 000002000001; thành phố thứ ba là 000001000001.

Ví dụ 2:

• Input:

  2 3 2 55 2 77 2 99

• Giải thích: Tất cả các thành phố đều thuộc tỉnh 2, ID của chúng lần lượt là 000002000001, 000002000002, 000002000003.
  

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House