题目描述

Bob 有很多垃圾。有一天，他想要对它们进行分类。

对于每一件垃圾，其类型用一个正整数表示。

他有 $q$ 个操作。对于每个操作，可能是以下两种操作之一。

• 1 s x 他告诉你，名为 $s$ 的垃圾类型为 $x$。
• 2 s 他想询问你垃圾 $s$ 的类型。

但他的记忆并不总是准确的。

对于每个操作 $2$，$s$ 可能没有在之前的操作 $1$ 中出现过。

我们定义两个字符串 $s_1$ 和 $s_2$ 的相似度为 $\sum_{i=1}^{\min\{|s_1|,|s_2|\}} [s_{1,i}=s_{2,i}]$。

这里所有字符串的索引从 $1$ 开始。

对于一个字符串 $s$，其类型是与 $s$ 相似度最大的字符串的类型，在所有之前操作 $1$ 中出现过的字符串中。如果有多个字符串与 $s$ 的相似度都最大，那么 $s$ 的类型是这些字符串类型中的最小值。

现在，他希望你解决这个问题。

输入格式

第一行包含一个整数 $q(1\le q\le 3\times 10^5)$，表示操作的数量。

接下来的 $q$ 行包含操作，每行一个。它们对应于题目中给出的描述。

保证对于每个操作 $2$，在它之前至少有一个操作 $1$。

但有些垃圾会有多种类型，你可以将其视为你读到的最小类型。

垃圾的名称仅由小写拉丁字母组成。

$1 \le |s| \le 5, 1 \le x \le 10^9$。

输出格式

对于每个操作 $2$，你应该在单独的一行中输出一个整数，即垃圾 $s$ 的类型。

输入输出样例 #1

输入 #1

4
1 aaa 1
2 aa
1 ab 2
2 bb

输出 #1

1
2

限制与约定

对于 $40\%$的样例， $2 \le q \le 100 , 1 \le x \le 100$

对于 $100\%$的样例， $2 \le q \le 100 , 1 \le x \le 10^9$

• 时间限制: $2 s$
• 空间限制: $256 MB$