Description

The Chinese ID number is a unique identification code for citizens, consisting of 18 digits or letters (only the last digit may be a letter). The meanings of the 18-digit ID number are as follows: digits 1–2 represent the province, autonomous region, or municipality code; digits 3–4 represent the prefecture-level city, league, or autonomous prefecture code; digits 5–6 represent the county, county-level city, or district code. Digits 7–14 represent the date of birth, for example, 19970401 stands for April 1, 1997; digits 15–16 are the sequence number, digit 17 represents gender (odd for male, even for female), and digit 18 is the checksum (0–9 or X). The checksum is calculated by substituting the first 17 digits into a unified formula. For this problem, you do not need to understand how it is calculated. Now, given n ID numbers, please output the m-th ID number in lexicographical order of birthdates (from oldest to youngest). Some explanations: although the data creators have painstakingly generated various ID numbers (ensuring their birthdates are unique), you do not need to validate any aspect of the ID numbers, including whether the province/city/district codes are valid, whether the birthdates are valid, or whether the checksums are correct. All you need to do is output the m-th oldest ID number.

Input Format

The first line of input contains two positive integers n and m, separated by a space. The next n lines each contain an ID number in the format described above (you do not need to verify the checksum, as it does not affect the solution to this problem). (1 ≤ n ≤ 100, 1 ≤ m ≤ n)

Output Format

The output consists of a single line, which is the ID number required by the problem.

```input1 4 2 110108196004063022 13021119640203652X 420333197902112718 210222200012036512 ``` ```output1 13021119640203652X ``` ```markdown ## Source

CodesOnline