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 \le r_i$ 的 $j$，令 $a_j := a_{l_i}$。

Doremy 还选择了一个整数 $k$。她想知道，对于每个从 $0$ 到 $m - 1$ 的整数 $x$，在从初始数组开始并依次执行操作 $x \bmod m+1, (x+1) \bmod m+1, \dots, (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 + 1)$ 个整数应当是：从初始数组开始，依次执行操作 $x \bmod m+1, (x+1) \bmod m+1, \dots, (x+k-1) \bmod m+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$ 时最终的数组状态。