Process Messages (FrontEnd focused Full-Stack Eng :)

Process messages by priority and then by time. This site specifies a stable sort for equal keys and adds the standard input protocol.

输入格式

The first line contains n (1≤n≤10^5), followed by n lines of timestamp:priority. timestamp is 0000..9999, and priority is 1..5.

输出格式

Sort by priority number ascending (1 is highest), then by timestamp value ascending, and output each message as is, one per line. Messages with identical keys keep their input order (stable sort).

样例 1

输入：

3
1045:2
0100:1
0100:2

输出：

0100:1
0100:2
1045:2

样例 2

输入：

3
0000:5
9999:1
0001:1

输出：

0001:1
9999:1
0000:5

样例 3

输入：

3
1200:3
1200:3
0000:3

输出：

0000:3
1200:3
1200:3