310291: CF1810F. M-tree

F. M-treetime limit per test2.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

A rooted tree is called good if every vertex of the tree either is a leaf (a vertex with no children) or has exactly $m$ children.

For a good tree, each leaf $u$ has a positive integer $c_{u}$ written on it, and we define the value of the leaf as $c_{u} + \mathrm{dep}_{u}$, where $\mathrm{dep}_{u}$ represents the number of edges of the path from vertex $u$ to the root (also known as the depth of $u$). The value of a good tree is the maximum value of all its leaves.

Now, you are given an array of $n$ integers $a_{1}, a_{2}, \ldots, a_{n}$, which are the integers that should be written on the leaves. You need to construct a good tree with $n$ leaves and write the integers from the array $a$ to all the leaves. Formally, you should assign each leaf $u$ an index $b_{u}$, where $b$ is a permutation of length $n$, and represent that the integer written on leaf $u$ is $c_u = a_{b_{u}}$. Under these constraints, you need to minimize the value of the good tree.

You have $q$ queries. Each query gives you $x$, $y$ and changes $a_{x}$ to $y$, and after that, you should output the minimum value of a good tree based on the current array $a$.

A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

Input

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Their description follows.

The first line contains three integers $n$, $m$, and $q$ ($1\le n,q \le 2 \cdot 10^5$, $2\le m \le 2\cdot 10^5$, $n \equiv 1 \pmod {m - 1}$) — the number of the leaves, the constant $m$, and the number of queries.

The second line contains $n$ integers $a_{1},a_{2}, \ldots, a_{n}$ ($1 \le a_{i} \le n$) — the initial array.

For the following $q$ lines, each line contains two integers $x$ and $y$ ($1\le x,y\le n$), representing a query changing $a_{x}$ to $y$.

It is guaranteed that both the sum of $n$ and the sum of $q$ do not exceed $2\cdot 10^5$.

Output

For each test case, output $q$ integers in one line, the $i$-th of which is the minimum tree value after the $i$-th change.

ExampleInput

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

Output

6 6 6
7 7 7 8
6 6 6 7

Note

In the first test case, after the first query, the current array $a$ is $[4,3,4,4,5]$. We can construct such a good tree:

The first number inside a vertex is its index (in this problem, the indices do not matter, but help to understand the figure). If a vertex is a leaf, the second number inside the vertex is the integer written on it.

We can tell that $\mathrm{dep}_{3}=\mathrm{dep}_{4}=1,\mathrm{dep}_{5}=\mathrm{dep}_{6}=\mathrm{dep}_{7}=2$ and the value of the tree, which is the maximum value over all leaves, is $5+1=6$. The value of leaves $5$, $6$, $7$ is also equal to $6$. It can be shown that this tree has the minimum value over all valid trees.

题目大意：
一个有根树被称为“好的”，如果每个顶点要么是叶子（没有子节点的顶点），要么有恰好 m 个子节点。

对于一个好的树，每个叶子 u 上都写有一个正整数 c_u，我们定义叶子的值为 c_u + \text{dep}_u，其中 \text{dep}_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 输出好树的最小价值。

输入输出数据格式：
输入：
- 第一行包含一个整数 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。

输出：
- 对于每个测试用例，输出 q 个整数，第 i 个整数是第 i 次更改后的最小树价值。

示例输入：
```
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
```

示例输出：
```
6 6 6
7 7 7 8
6 6 6 7
```

注意：
在第一个测试用例中，经过第一次查询后，当前数组 a 为 [4,3,4,4,5]。我们可以构建这样一个好树：
```
1
/ \
2 3
/ \ / \
4 5 6 7
```
我们可以看出 \text{dep}_3=\text{dep}_4=1,\text{dep}_5=\text{dep}_6=\text{dep}_7=2，并且树的价值，即所有叶子的最大值是 5+1=6。叶子的价值 5, 6, 7 也是 6。可以证明，这棵树在所有有效树中的价值是最小的。题目大意： 一个有根树被称为“好的”，如果每个顶点要么是叶子（没有子节点的顶点），要么有恰好 m 个子节点。 对于一个好的树，每个叶子 u 上都写有一个正整数 c_u，我们定义叶子的值为 c_u + \text{dep}_u，其中 \text{dep}_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 输出好树的最小价值。 输入输出数据格式： 输入： - 第一行包含一个整数 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。 输出： - 对于每个测试用例，输出 q 个整数，第 i 个整数是第 i 次更改后的最小树价值。 示例输入： ``` 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 ``` 示例输出： ``` 6 6 6 7 7 7 8 6 6 6 7 ``` 注意： 在第一个测试用例中，经过第一次查询后，当前数组 a 为 [4,3,4,4,5]。我们可以构建这样一个好树： ``` 1 / \ 2 3 / \ / \ 4 5 6 7 ``` 我们可以看出 \text{dep}_3=\text{dep}_4=1,\text{dep}_5=\text{dep}_6=\text{dep}_7=2，并且树的价值，即所有叶子的最大值是 5+1=6。叶子的价值 5, 6, 7 也是 6。可以证明，这棵树在所有有效树中的价值是最小的。