如果树的每个顶点都是叶子(没有子节点的顶点)或者恰好具有 $$$m$$$ 子节点,则该有根树被称为好树。
对于一棵好树,每片叶子 $$$u$$$ 上都写有一个正整数 $$$c_{u}$$$,我们将叶子的值定义为 $$$c_{u} + \mathrm{dep}_{u}$$$,其中 $$$\mathrm{dep}_{u}$$$ 表示从顶点 $$$u$$$ 到顶点 $$$u$$$ 的路径的边数根(也称为 $$$u$$$ 的深度)。一棵好树的价值是它所有叶子的最大价值。
现在,给你一个 $$$n$$$ 整数数组 $$$a_{1}, a_{2}, \ldots, a_{n}$$$,它们是应该写在叶子上的整数。您需要构建一棵具有 $$$n$$$ 叶子的好树,并将数组 $$$a$$$ 中的整数写入所有叶子。形式上,您应该为每个叶子$$$u$$$分配一个索引$$$b_{u}$$$,其中$$$b$$$是长度$$$n$$$的排列,并表示写在叶子$$$u$$$上的整数是$$$c_u = a_{b_{u}}$$$。在这些约束下,你需要最小化好树的价值。
您有 $$$q$$$ 查询。每个查询都会给出 $$$x$$$、$$$y$$$ 并将 $$$a_{x}$$$ 更改为 $$$y$$$,之后,你应该根据当前数组 $$$a$$$ 输出一棵好树的最小值。
长度 $$$n$$$ 的排列是一个由 $$$n$$$ 个从 $$$1$$$ 到 $$$n$$$ 的不同整数以任意顺序组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。他们的描述如下。
第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$q$$$ ($$$1\le n,q \le 2 \cdot 10^5$$$, $$$2\le m \le 2\cdot 10^5$$$, $$$n \equiv 1 \pmod {m - 1}$$$) — 数字叶子的数量、常量 $$$m$$$ 以及查询的数量。
第二行包含 $$$n$$$ 整数 $$$a_{1},a_{2}, \ldots, a_{n}$$$ ($$$1 \le a_{i} \le n$$$) — 初始数组。
对于以下 $$$q$$$ 行,每行包含两个整数 $$$x$$$ 和 $$$y$$$ ($$$1\le x,y\le n$$$),表示将 $$$a_{x}$$$ 更改为 $$$y$$$ 的查询。
保证$$$n$$$之和与$$$q$$$之和不超过$$$2\cdot 10^5$$$。
输出
对于每个测试用例,在一行中输出 $$$q$$$ 个整数,其中第 $$$i$$$ 是第 $$$i$$$ 次更改后的最小树值。
示例
输入 #1
3 5 3 3 3 3 4 4 5 1 4 2 4 3 5 5 2 4 3 3 4 4 5 1 4 2 5 3 5 4 5 7 3 4 1 2 2 3 3 3 4 1 4 2 1 5 5 6 6
输出 #1
6 6 6 7 7 7 8 6 6 6 7
注意
在第一个测试用例中,在第一个查询之后,当前数组 $$$a$$$ 是 $$$[4,3,4,4,5]$$$。我们可以构建这样一棵很好的树:
顶点内的第一个数字是它的索引(在这个问题中,索引并不重要,但有助于理解图形)。如果顶点是叶子,则顶点内的第二个数字是写在其上的整数。
我们可以知道 $$$\mathrm{dep}_{3}=\mathrm{dep}_{4}=1,\mathrm{dep}_{5}=\mathrm{dep}_{6}=\mathrm{dep}_{7}=2$$$ 并且树的值(所有叶子的最大值)为$$$5+1=6$$$。叶子 $$$5$$$、$$$6$$$、$$$7$$$ 的值也等于 $$$6$$$。可以证明,这棵树在所有有效树中具有最小值。