Beacon 做了一个梦，梦见自己在一座木桥上无忧无虑地玩耍。

木桥由 $n$ 列木板组成。每列都有无限多块木板，对于第 $i$ 列，第一块木板的长度为 $a_i$，之后所有木板的长度均为 $k$。第一块木板的长度不大于 $k$。桥面左下角的坐标为 $(0, 0)$，桥面覆盖的范围为 $\{0 \le x \le n, y \ge 0\}$。下图展示了一个 $n = 4, a = [2, 1, 3, 2], k = 3$ 的例子：

Beacon 觉得桥上的缝隙很有趣。现在他想提出 $q$ 个问题。对于每个询问，给定他从格子 $(x_1, y_1)$ 走到格子 $(x_2, y_2)$，他最少需要跨越多少次木板之间的缝隙？（每次他从一块木板走到另一块木板时，就会跨越一次木板之间的缝隙。）

更具体地说，他的起点是坐标 $(x_1 - 0.5, y_1 - 0.5)$，终点是坐标 $(x_2 - 0.5, y_2 - 0.5)$。他的移动方式如下：当他处于坐标 $(x, y)$ 时，他可以向四个方向（上、下、左、右）之一移动 $1$ 个单位长度，到达 $(x-1, y)$、$(x+1, y)$、$(x, y-1)$ 和 $(x, y+1)$ 四个坐标之一，且他绝不能离开桥面。

由于他太懒了，这些问题就留给你来回答。

输入格式

第一行包含三个整数 $n, k, q$ ($1 \le n, q \le 2 \times 10^5, 1 \le k \le 10^{12}$)。

第二行包含 $n$ 个整数 $a_i$ ($1 \le a_i \le k$)。

接下来的 $q$ 行，每行包含四个整数 $x_1, y_1, x_2, y_2$ ($1 \le y_1, y_2 \le 10^{12}, 1 \le x_1, x_2 \le n$)。

输出格式

输出 $q$ 行，每行包含对应询问的答案。

样例

输入样例 1

4 3 4
2 1 3 2
1 1 3 2
2 5 2 4
4 1 1 7
2 2 4 5

输出样例 1

2
1
4
2

说明

上图展示了对应第三个询问的一条可能路径，跨越了 4 次缝隙。