P10564 [ICPC 2024 Xi'an I] Rubbish Sorting

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$ 的类型。

（由 ChatGPT 4o 翻译）