题目描述

为了在全市中小学的社团中独树一帜，断罪中学麻将社主办了一场轰轰烈烈的校际立直麻将联赛，共计\(N\)名来自各大中学的雀士参与到了此次盛会。\(N\)名参赛者依次编号为\(1 \sim N\)。联赛采取一般的4人麻将规则，系统为每名参赛者随机安排\(K\)场对局，取这\(K\)场中该参赛者的分数之和作为其总成绩。
输入所有\(NK / 4\)场对局的信息，包括每场的参赛者编号以及各自的分数，请你按照总成绩从大到小的顺序输出每名参赛者编号与总分。若有多人总分相同，则编号较小的先输出。

输入格式

第一行是两个正整数\(N, K\)；
之后\(NK / 4\)行，每行包含8个正整数\(c_1, c_2, c_3, c_4, s_1, s_2, s_3, s_4\)，其中\(c_1 \cdots c_4\)表示该场对局中4名参赛者的编号，之后的\(s_i\)表示编号为\(c_i\)的参赛者在该场对局中的得分。输入保证\(1 \le c_1 < c_2 < c_3 < c_4 \le N\)。

输出格式

输出\(N\)行，按照“题目描述”中规定的顺序输出每名选手的信息。每行包含2个整数\(c,S\)，分别表示该参赛者的编号和总分，中间用一个空格隔开。

样例

输入

5 4
1 2 3 4 170 325 245 260
1 2 3 5 -30 845 125 60
1 2 4 5 150 450 85 315
1 3 4 5 90 693 233 -16
2 3 4 5 310 95 610 -15

输出

2 1930
4 1188
3 1158
1 380
5 344

数据规模及约定

\(N \le 10^5, \quad K \in \{4, 8, 16\}, \quad -1000 \le s_i \le 1000\)
时间限制1s，空间限制64MB。