2954 - 【入门】归并排序

通过次数

3

提交次数

4

Time Limit : 1 秒
Memory Limit : 128 MB

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

排序规则:

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

周周和玩仔决定分工排序,于是周周排序 n 个人,玩仔排序 m 个人。

他们排序完之后发现还需要合并,你现在的任务是把两个人排序后的成绩进行合并排序。

Input

第一行输入两个整数 n,m,表示周周排序 n 个人,玩仔排序 m 个人。

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

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

Output

请输出排序后的结果。

Examples

Input

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

Output

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