{"problem":{"name":"ID","description":{"content":"In Republic of Atcoder, there are $N$ prefectures, and a total of $M$ cities that belong to those prefectures. City $i$ is established in year $Y_i$ and belongs to Prefecture $P_i$. You can assume tha","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc113_c"},"statements":[{"statement_type":"Markdown","content":"In Republic of Atcoder, there are $N$ prefectures, and a total of $M$ cities that belong to those prefectures.\nCity $i$ is established in year $Y_i$ and belongs to Prefecture $P_i$.\nYou can assume that there are no multiple cities that are established in the same year.\nIt is decided to allocate a $12$\\-digit ID number to each city.\nIf City $i$ is the $x$\\-th established city among the cities that belong to Prefecture $i$, the first six digits of the ID number of City $i$ is $P_i$, and the last six digits of the ID number is $x$.\nHere, if $P_i$ or $x$ (or both) has less than six digits, zeros are added to the left until it has six digits.\nFind the ID numbers for all the cities.\nNote that there can be a prefecture with no cities.\n\n## Constraints\n\n*   $1 \\leq N \\leq 10^5$\n*   $1 \\leq M \\leq 10^5$\n*   $1 \\leq P_i \\leq N$\n*   $1 \\leq Y_i \\leq 10^9$\n*   $Y_i$ are all different.\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$\n$P_1$ $Y_1$\n$:$\n$P_M$ $Y_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc113_c","tags":[],"sample_group":[["2 3\n1 32\n2 63\n1 12","000001000002\n000002000001\n000001000001\n\n*   As City $1$ is the second established city among the cities that belong to Prefecture $1$, its ID number is $000001000002$.\n*   As City $2$ is the first established city among the cities that belong to Prefecture $2$, its ID number is $000002000001$.\n*   As City $3$ is the first established city among the cities that belong to Prefecture $1$, its ID number is $000001000001$."],["2 3\n2 55\n2 77\n2 99","000002000001\n000002000002\n000002000003"]],"created_at":"2026-03-03 11:01:14"}}