该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

身份证号是我国公民的唯一识别码，它由 18 位数字或字母组成（只可能最后一位是字母）。

18 位身份证号码各位的含义如下：第 1 − 2 位为省、自治区、直辖市代码；第 3 − 4 位为地级市、盟、自治州代码；第 5 − 6 位为县、县级市、区代码。第 7 − 14 位为出生年月日，比如19970401 代表 1997 年 4 月 1 日；第 15 − 16 位为顺序号，第 17 位代表性别，男为单数，女为双数；第 18 位为校验码，0 − 9 和 X。作为尾号的校验码，是把前十七位数字代入统一的公式计算出来的，解答本题你不用关心是如何计算出来的。

现在给你 n 个身份证号码，请你按照出生年月日的字典序（年龄从大到小）输出第 m 个人的身份证号。

输入格式

第一行包含两个正整数 n 和 m，两数间用一个空格分隔，接下来的 n 行每行为一个形如上述格式的身份证号码（不需要关心校验码的正确性，不影响本题解答）。

输出格式

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

输入输出样例

输入

4 2
110108196004063022
13021119640203652X
420333197902112718
210222200012036512

输出

13021119640203652X

说明/提示

【样例解释】

共有 4人的身份证，要找到年龄第二大的身份证，按照身份证位数找到年龄，年龄第二大的是1964年的，所以输出对应的身份证号。

【数据范围】

对所有测试数据有：1<=n<=10000，1<=m<=n。