题目描述

小远用神奇的水泉魔法造出了$N$个不同的水球。

对于每个水球，小远用两个参数来评价它的威力： 水球的大小 $w$，水球的等级 $R$。

其中，$w$ 为一个正整数，$R$ 可以是 A，B，C，D 四个等级之一。四个等级由高到低的顺序是 A > B > C > D 。

等级越高的水球威力越大，若两个水球等级相同则大小越大的水球威力越大。

同时，小远还给每个水球起了一个仅由小写字母组成的名字 $s$ 。

现在 小远给你这 $N$ 个水球的大小和等级 $w,R$，要求你帮他给出这些水球按照威力从大到小的顺序。

输入格式

第一行一个整数 $N$，表示水球的数量。

接下来 $N$行，对于第 $i$ 行 $(1\le i\le N)$ 有一个字符 $R_i$，一个字符串 $s_i$ 和一个正整数 $w_i$，分别表示编号为 $i$ 的水球的等级、名字和大小。

输出格式

一行，共 $N$ 个正整数， 其中第 $i$ 个 $(1\le i\le N)$ 正整数表示威力从大到小排名为 $i$ 的水球的名字。若两个水球威力相同，则按照输入顺序输出。

样例 #1

样例输入 #1

3
B ioi 998
A xp 448
A ak 10

样例输出 #1

xp ak ioi

样例 #2

样例输入 #2

4
C hao 100
B sp 10
B ring 10
D cute 1000

样例输出 #2

sp ring hao cute

提示

本题采用Subtasks捆绑评测。

对于所有数据：$1\le w_i \le 2^{63}-1，|s_i|\le20$，且 $R_i$ 只可能为 A，B，C，D 之一。

Subtask 0 (20分)：$1\le N \le 1000$ 。

Subtask 1 (80分)： $1\le N \le 2 \times 10^5$。