{"raw_statement":[{"iden":"problem statement","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."},{"iden":"constraints","content":"*   $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."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$\n$P_1$ $Y_1$\n$:$\n$P_M$ $Y_M$"},{"iden":"sample input 1","content":"2 3\n1 32\n2 63\n1 12"},{"iden":"sample output 1","content":"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$."},{"iden":"sample input 2","content":"2 3\n2 55\n2 77\n2 99"},{"iden":"sample output 2","content":"000002000001\n000002000002\n000002000003"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}