U236173 【模板】可持久化字典树

我们走了很远，以至于忘记了自己为何而出发。 没有谁能够写下亘古的回忆，所以才会用一种方式，留下回忆的足迹。

你曾写下过很多很多的文字，写在了那泛黄的日记本里，但你快要忘记了记载之事的真正意义，现在，正是你回忆的时候。 你一页一页地翻着日记本，一共有 $n$ 页，每一页都记录着一些信息，当你获得了一条信息，你就会记住；但时不时地，你会想过要去查询一些信息，但你会想这条信息是多久的信息，所以你会询问一个历史版本 $k$ ，以及一条信息 $s$ ，你想要知道这条信息在此之前是否出现过。 **简要题意**： 维护一个数据结构，支持以下操作： * $A,s$ ，表示插入一个由字母和数字组成的字符串，称为最新版本； * $Q,x,s$ ，一次询问，查询在 $x$ 版本中是否出现过 $s$ ，返回 `Yes` 或 `No` 。

无

无

$m\leq 10^4$ $|s|\leq 10^5$ 字符仅包含，数字，小写字母，大写字母。 其中 $30\%$ 的数据满足 $n\leq 99$ 其中 $60\%$ 的数据满足 $n\leq 999$ 其中 $100\%$ 的数据满足 $n\leq 10^4$