2952 - 【入门】插入排序

通过次数

3

提交次数

3

Time Limit : 1 秒
Memory Limit : 128 MB

一天老师让周周把全班的同学的成绩排个名。

排序规则:

  • 如果分数不相等,按照分数排序
  • 如果分数相等,按照用时排序。
  • 如果分数和用时相同,就按照学号排序。

周周辛辛苦苦排序完成之后,结果发现漏了一个人没有排序,需要插入到已经拍好序的名单中。现在周周已经没有力气,所以便把这个艰巨的问题交给了你。

Input

第一行输入一个整数 n,表示一个共有 n 个人。

接下来 n 行,每行三个整数 grade,time,id

n-1 个是已经排序好的成绩,第 n 个是漏掉的。

Output

请输出排序后的结果。

数据范围 n \le 1000, grade,time,id \le 100

Examples

Input

4
100 120 1
99 110 2
99 119 3
100 120 4

Output

100 120 1
100 120 4
99 110 2
99 119 3