CF1764H.Doremy's Paint 2

Doremy has $n$ buckets of paint which is represented by an array $a$ of length $n$. Bucket $i$ contains paint with color $a_i$. Initially, $a_i=i$.

Doremy has $m$ segments $[l_i,r_i]$ ($1 \le l_i \le r_i \le n$). Each segment describes an operation. Operation $i$ is performed as follows:

• For each $j$ such that $l_i \lt j \leq r_i$, set $a_j := a_{l_i}$.

Doremy also selects an integer $k$. She wants to know for each integer $x$ from $0$ to $m-1$, the number of distinct colors in the array after performing operations $x \bmod m +1, (x+1) \bmod m + 1, \ldots, (x+k-1) \bmod m +1$. Can you help her calculate these values? Note that for each $x$ individually we start from the initial array and perform only the given $k$ operations in the given order.

Doremy 有 $n$ 桶颜料，用一个长度为 $n$ 的数组 $a$ 表示。其中第 $i$ 桶颜料的颜色为 $a_i$。初始时，$a_i = i$。

Doremy 还有 $m$ 个区间 $[l_i, r_i]$（满足 $1 \le l_i \le r_i \le n$）。每个区间描述一次操作。第 $i$ 次操作的执行方式如下：

• 对每个满足 $l_i < j \leq r_i$ 的 $j$，令 $a_j := a_{l_i}$。

此外，Doremy 还选定一个整数 $k$。她希望对每个从 $0$ 到 $m-1$ 的整数 $x$，计算在初始数组上依次执行操作 $(x \bmod m) + 1,\ (x+1) \bmod m + 1,\ \ldots,\ (x+k-1) \bmod m + 1$ 后，数组中不同颜色的种类数。你能帮她算出这些值吗？注意：对每个 $x$，我们均从初始数组出发，仅按给定顺序执行这 $k$ 次操作。

The first line of input contains three integers $n$, $m$, and $k$ ($1\le n,m\le 2\cdot 10^5$, $1 \le k \le m$) — the length of the array $a$, the total number of operations, and the integer that Doremy selects.

The $i$-th line of the following $m$ lines contains two integers $l_i$, $r_i$ ($1\le l_i\le r_i\le n$) — the bounds of the $i$-th segment.

输入的第一行包含三个整数 $n$、$m$ 和 $k$（$1\le n,m\le 2\cdot 10^5$，$1 \le k \le m$）——分别表示数组 $a$ 的长度、操作总数以及 Doremy 所选择的整数。

接下来的 $m$ 行中，第 $i$ 行包含两个整数 $l_i$、$r_i$（$1\le l_i\le r_i\le n$）——表示第 $i$ 个区间的左右端点。

Output $m$ integers. The $(x+1)$-th integer should be the number of distinct colors in the array if we start from the initial array and perform operations $x \bmod m +1, (x+1) \bmod m + 1, \ldots, (x+k-1) \bmod m +1$.

输出 $m$ 个整数。第 $(x+1)$ 个整数应为：从初始数组出发，依次执行操作 $x \bmod m +1,\ (x+1) \bmod m + 1,\ \ldots,\ (x+k-1) \bmod m +1$ 后，数组中不同颜色的数量。

In the first test case, the picture below shows the resulting array for the values of $x=0,1,2$ respectively.

在第一个测试用例中，下图分别展示了 $x=0,1,2$ 时所得数组的结果。