题目描述

@zls_XICK 接受了来自朋友们诚挚的祝福，高兴地拆开了所有的礼物，礼物各式各样：Switch、深入浅出、六个核桃……大小不一的礼物摆在一起多少有些杂乱，于是 @zls_XICK 打算整理整理这些礼物。

从低到高排列礼物似乎是个不错的选择，但是 @zls_XICK 担心整理礼物的过程中把礼物弄丢了，所以他只想把礼物从右往左一个一个搬，但他很快发现，有些时候无论如何也无法让礼物从低到高排列，@mywwzh 便提议：把礼物尽量低的在前就行了，别那么挑剔。

于是 @zls_XICK 仍按照从右往左一个一个搬的方法整理 $N$ 个礼物，他希望礼物尽量低的在前：

• “从右往左一个一个搬”指的是将第 $N$ 个礼物搬到第 $1$ 个礼物左侧。

• 对于两种排列方式礼物逐个比较，若第 $i$ 个礼物高度 $h_i$ 不同，则称 $h_i$ 较小的排列方式为“尽量低的在前”，高度相等则比较下一位。

• 若有多种排列方式满足最优，则希望“从右往左一个一个搬”操作次数最少。

现在他想知道整理后每个礼物的高度是怎样的，即整理后每个礼物的高度 $h_i$ ，同时，他还想知道此时摆在第一个的礼物是谁送的。

输入格式

输入包括 $N+1$ 行。

第一行一个整数 $N$ ，表示礼物数。

接下来 $N$ 行，表示原来礼物的排列方式，每行 $1$ 个整数 $h_i$ 和 $1$ 个字符串 $S_i$ 分别表示第 $i$ 个礼物的高度、赠送者。

输出格式

输出包括 $2$ 行。

第一行 $N$ 个整数，表示最优排列每个礼物的高度，每两个整数间用空格隔开。

第二行一个字符串，表示此时第一个礼物的赠送者。

5
5 lzh
4 xlw
3 cby
2 rgw
1 mt

1 5 4 3 2
mt

数据规模与约定

对于 $40\%$ 的数据满足 $1 \le N \le 10^3$。

对于 $100\%$ 的数据满足 $1 \le N \le 10^6$，$h_i \in \left[ 1,10^9 \right]$，$S_i.size() \in \left[ 1,10^2 \right]$，且字符串由大、小写字母组成。