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$$$执行如下:
- 对于每个$$$j$$$,使得$$$l_i < j \leq r_i$$$,设置$$$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$$$ 操作。
输入
输入的第一行包含三个整数 $$$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$$$ 段的边界。
输出
输出 $$$m$$$ 个整数。如果我们从初始数组开始并执行操作 $$$x \bmod m +1, (x+1) \bmod m + 1, \ldots, (x+k-1) \bmod m +1$$$ 操作,那么第 $$$(x+1)$$$ 个整数应该是数组中不同颜色的数量。
示例
输入 #1
7 5 5 3 5 2 3 4 6 5 7 1 2
输出 #1
3 3 3 3 2
输入 #2
10 9 4 1 1 2 3 3 4 7 9 6 8 5 7 2 4 9 10 1 3
输出 #2
6 6 7 6 5 5 7 7 7
注意
在第一个测试用例中,下图分别显示了 $$$x=0,1,2$$$ 值的结果数组。