#P2142. 第m大的身份证号码

第m大的身份证号码

Description

身份证号是我国公民的唯一识别码,它由  1818 位数字或者字母组成(只可能最后一位是字母)。 1818 位身份证号码的含义如下:第 121\sim 2 为省、自治区、直辖市代码:第 343\sim 4 位为地级市、盟、自治州代码;第 565\sim 6 位为县、县级市、区代码。第 7147\sim 14 位为出生年月日,比如 1997040119970401 代表 199719974411 日;第 151615\sim 16 位为顺序号,第 1717 位代表性别,男为单数,女为双数,第 1818 位为校验码, 090\sim 9XX 。作为尾号的校验码,是把前十七位数字代入统一的公式计算出来的。解答本题你不用关心是如何计算出来的。现在给你  nn 个身份证号码,请你按照出生年月日的字典序(年龄从大到小)输出第  mm 个人的身份证号。

一些解释:虽然造数据的人非常辛苦的制造各种各样的身份证号(并且让他们生日互不相同),但是你并不需要验证关于身份证号的任何合法性,包括省市区是否合法,出生年月日是否合法,校验值是否合法,你需要做的仅仅是输出年龄从大到小第 mm 个人的身份证号。

Input Format

输入第一行包含两个正整数 nnmm ,两数之间用一个空格分隔,接下来的 nn 行每行为一个形如上述格式的身份证号码(不需要关心校验码的正确性,不影响本题解答)。( 1n1001\le n\le 1001mn1\le m\le n

Output Format

输出仅包含一行,为题目要求的一个身份证号码。

4 2
110108196004063022
13021119640203652X
420333197902112718
210222200012036512
13021119640203652X