已知某国的身份证号的制定规则如下：

身份证号是一个 14 位的数字； 前 3 位对应所在地区的区号； 中间 8 位对应生日，格式为 YYYYMMDD，其中 YYYY 对应年，MM 对应月，DD 对应日； 接下来 2 位对应一个数字，表示你是该地区该天出生的第几个孩子； 最后一位表示性别，其中：奇数是男生，偶数是女生。 比如：有一位叫 Maggie 的同学，她出生时所在地区的区号为 15，出生日期是 2024 年 5 月 1 日，是该地区该天出生的第 7 个孩子，性别为女且性别对应的数字是 8，则 Maggie 的身份证号为： 01520240501078。

现在告诉你该国 n 位同学的身份证号，请你按照如下规则对这些同学的身份证号排序：

出生日期从前往后； 出生日期相同时区号从小到大； 出生日期和区号均相同时女生比男生靠前； 出生日期、区号、性别均相同时按照出生顺序从前往后。 并按照排序后的顺序依次输出每位同学的身份证号。

输入描述

第一行，一个整数 n，表示数列长度（1≤n≤10 5 ）。

第二行，n 个整数 a 1 ​ ,a 2 ​ ,…,a n ​ ，以空格分隔（1≤a i ​ ≤10 9 ）。

输出描述

一行，n 个整数，以空格分隔，表示从大到小排序后的数列。

样例输入 1

6 01020230518051 02520230518258 01020230518033 03320201102012 02520240307055 01020230518124 样例输出 1

03320201102012 01020230518124 01020230518033 01020230518051 02520230518258 02520240307055 提示

数据范围与约定 对于 50% 的数据，n≤1000 对于 100% 的数据，1≤n≤10 5