[校内训练20161216] T2 版本管理git

时间限制：2000MS      内存限制：1048576KB

难度：$7.0$

• 题目描述

在工程的开发中，我们常常用 $Git$ 进行版本的管理。这个方式具体来说是这样的：刚开始只有一个版本 $0$，表示最初始的情况，也就是空的项目；接下来一个用户可以对某一个版本 $p$ 的项目进行修改，得到一个新的版本 $i$。这样，一个工程就产生了许多不同的版本，而管理员可以选择一些优秀的，将其合并到主版本中。

$F$ 公司有一个项目 $U$，这个项目由一个字符串构成。版本 $0$ 为空串。有 $n$ 个开发者按顺序对这个项目进行了修改，其中第 $i$ 个开发者将第 $p_i ( 0 \le p_i < i)$ 个版本的开头添加上一个字符 $c_i (1 \le c_i \le m)$ 作为新的版本 $i$。

作为项目的总负责人，你希望对这些版本进行评价。对一个字符串 $S$，称串 $S$ 是串 $T$ 的超前缀，当且仅当串 $S$ 是串 $T^{*}$ 的前缀。 $T^{*}$ 表示 $T$ 重复无限次得到的一个无限长度的串，如若 $T = abcd$，则 $T^{*} = abcdabcdabcd \cdots$。我们称串 $S$ 的 “$kitty$ 长度” 为 $l$，当且仅当存在一个长度为 $l$ 的串 $T$ 使得 $S$ 是 $T$ 的超前缀，且不存在小于 $l$ 的串 $T’$ 使得 $S$ 是 $T’$ 的超前缀（定义空串的 $kitty$ 长度为 $0$）。你需要做的就是对每一个版本求出其的 $kitty$ 长度（设版本 $i$ 的 $kitty$ 长度为 $kitty(i)$）。

在实际运营中，有两种情况，我们用一个数 $k \in \{0,1\}$ 表示。在 $k = 0$ 的情况中， 你可以等候开发者进行所有修改后，再进行计算；但在 $k = 1$ 的情况中，开发者希望能够实时得到自己修改得到的版本的 $kitty$ 长度，你需要实时计算出每个版本的 $kitty$ 长度。

• 输入格式

第一行包含三个整数 $n,m,k$。

接下来 $n$ 行，其中第 $i$ 行包含两个整数 $p^{′}_{i}; c^{′}_{i}$，其中：

如果 $k = 0$ ，则 $p_i = p^{′}_{i}$，$c_i = c^{′}_{i}$；

如果 $k = 1$，则 \(p_i = p^{′}_{i} \oplus kitty(i …