题目描述

在计算机科学中，trie，又称前缀树，是一种搜索树，一种有序的树形数据结构，其键通常为字符串。

这里我们有一棵包含 $(n + 1)$ 个节点的 trie，节点编号为 $0$ 到 $n$，其根为编号 $0$ 的节点。trie 中的所有边均从高度较低的节点指向高度较高的节点。每条边仅包含一个小写字母，且从同一节点出发的任意两条边所具有的字符互不相同。

我们希望在 trie 上为任意字符串 $T[1..k]$ 引入一种特殊的匹配过程。

匹配将从根开始，按顺序依次考虑所有字符 $T[1], T[2], \cdots, T[k]$，并沿着某条从当前节点出发且包含当前所考虑字符的边移动。如果匹配到达某个节点后无法沿任何边继续移动，则：

• 它将在当前字符处记录一次失败，跳过该字符并移回根节点；
• 随后它将在下一次匹配步中考虑下一个字符，因为失败的字符应当被跳过。

最终，在考虑完 $T$ 中的所有字符后，匹配将停留在 trie 的某个节点上，该节点指示了此次匹配的目的地。我们将目的地的编号记作 $Dest(T)$，并将匹配过程中失败的总次数记作 $CFail(T)$。 现在，我们给你一个长度为 $m$ 的全小写字母字符串 $S[1..m]$，你需要回答 $q$ 个查询。一个查询定义为

$$\displaystyle Query(l, r) = (CFail(S[l..r]), Dest(S[l..r])),$$

即询问 $S$ 的子串 $S[l..r]$ 所对应的匹配失败总次数及目的地。

输入格式

输入包含多组测试数据，第一行包含一个正整数 $T$，表示测试数据组数，最多为 $1000$。

对于每组测试数据，第一行包含三个整数 $n$、$m$ 和 $q$，分别表示 trie 的节点数、给定字符串 $S$ 的长度以及查询的总数，满足 $1 \leq n, m, q \leq 10^5$。

接下来的 $n$ 行描述 trie。其中第 $i$ 行包含一个整数 $f_i$（满足 $0 \leq f_i < i$）和一个小写字母 $c_i$，分别表示第 $i$ 个节点的父节点以及连接它们的边上的字符。

再接下来一行包含一个全小写字母的字符串，表示给定的长度为 $m$ 的字符串 $S$。

最后 $q$ 行中的每一行包含两个整数 $l$ 和 $r$，表示一个查询 $Query(l, r)$，满足 $1 \leq l \leq r \leq m$。

我们保证所有测试数据中 $n$ 的总和、$m$ 的总和以及 $q$ 的总和均分别不超过 $10^6$。

输出格式

对于每组测试数据，输出若干行以回答所有查询。

对于每个查询，输出一行包含两个整数，分别表示 $CFail(S[l..r])$ 和 $Dest(S[l..r])$。你应在两个数字之间恰好输出一个空格。

1
5 10 5
0 a
0 b
1 a
1 c
2 a
aaacbaacab
1 5
1 6
1 7
3 9
4 10

2 2
2 5
3 0
2 1
4 0

提示

下图展示了样例测试数据中给出的 trie。

:::align{center} :::

所有查询的路径描述如下，其中每个 $\Longrightarrow$ 表示一次失败。

• $Path(1, 5) = Path(\text{``aaacb"}) = 0 \longrightarrow 1 \longrightarrow 3 \Longrightarrow 0 \Longrightarrow 0 \longrightarrow 2;$
• $Path(1, 6) = Path(\text{``aaacba"}) = 0 \longrightarrow 1 \longrightarrow 3 \Longrightarrow 0 \Longrightarrow 0 \longrightarrow 2 \longrightarrow 5;$
• $Path(1, 7) = Path(\text{``aaacbaa"}) = 0 \longrightarrow 1 \longrightarrow 3 \Longrightarrow 0 \Longrightarrow 0 \longrightarrow 2 \longrightarrow 5 \Longrightarrow 0;$
• $Path(3, 9) = Path(\text{``acbaaca"}) = 0 \longrightarrow 1 \longrightarrow 4 \Longrightarrow 0 \longrightarrow 1 \longrightarrow 3 \Longrightarrow 0 \longrightarrow 1;$
• $Path(4, 10) = Path(\text{``cbaacab"}) = 0 \Longrightarrow 0 \longrightarrow 2 \longrightarrow 5 \Longrightarrow 0 \Longrightarrow 0 \longrightarrow 1 \Longrightarrow 0.$

翻译由 DeepSeek V4 Pro 完成