该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

实时排名

题目描述

Y 同学正在负责一场 OI 赛制的模拟赛。

本次比赛共有 $n$ 名选手和 $4$ 道题目。每名选手在每道题上的成绩均以最后一次提交的成绩为准。

初始时，所有选手的 $4$ 道题得分均为 $0$。

接下来依次发生 $m$ 个事件，每个事件有以下两种类型之一：

• 1 s a b：表示选手 $s$ 提交了第 $a$ 道题，本次提交后，该选手第 $a$ 道题的得分变为 $b$；
• 2：查询当前总分最高的选手。

一名选手的总分等于其 $4$ 道题得分之和。

对于每次查询，如果有多名选手的总分并列最高，则输出姓名字典序最小的选手。

请你处理所有事件，并回答每一次查询。

输入格式

第一行包含两个整数 $n,m$，分别表示参赛选手数量和事件数量。

第二行包含 $n$ 个互不相同的字符串 $s_1,s_2,\dots,s_n$，分别表示每名选手的姓名。

接下来 $m$ 行，每行描述一个事件。

若该行第一个整数为 $1$，则接下来输入一个字符串 $s$ 和两个整数 $a,b$，表示选手 $s$ 的第 $a$ 道题得分变为 $b$。

若该行第一个整数为 $2$，则该行没有其他输入。

输出格式

对于每个类型为 $2$ 的事件，输出一行一个字符串，表示当前总分最高的选手姓名。

如果有多名选手总分相同且均为最高分，则输出其中字典序最小的姓名。

样例

样例输入 #1

3 12
a b c
1 b 1 100
1 a 2 90
2
1 b 2 90
1 a 1 100
2
1 b 2 100
2
1 c 1 100
1 c 2 100
1 c 3 100
2

样例输出 #1

b
a
b
c

数据范围与约定

对于 $100\%$ 的数据，保证：

• $1\le n,m\le1000$；
• $1\le a\le4$；
• $0\le b\le100$；
• 每名选手的姓名长度不超过 $6$；
• 所有选手姓名互不相同；
• 类型为 $1$ 的事件中，选手 $s$ 一定是参赛选手之一。

• 特殊性质 A：保证 $n=1$。
• 特殊性质 B：保证每名选手的姓名长度均为 $1$。
• 特殊性质 C：保证所有类型为 $1$ 的事件均满足 $a=1$ 且 $b=100$。