考虑一个长度为 $L$ 的圆，并在圆上选取一点作为原点。在本题中，圆上一点的坐标定义为从原点沿逆时针方向到该点的弧长。因此，圆上每个点的坐标都在 $0$（包含）到 $L$（不包含）之间。圆上坐标为 $a$ 和 $b$ 的两点之间的距离是连接它们的最短弧长，即 $\min(|a - b|, L - |a - b|)$。

给定圆上的 $n$ ($1 \le n \le 1\,000\,000$) 个房屋，其坐标均为整数。房屋的坐标由一个特殊的伪随机数生成器生成。生成器的代码如下所示。注意，多个房屋可能位于同一位置。

你需要选择 $k$ ($1 \le k \le n$) 个坐标为整数的点，并在这些点上放置收集器。同样，多个收集器和/或房屋可能位于同一位置。

放置收集器后，你需要将每个房屋分配给一个收集器。最后，对于每个收集器，计算分配给它的所有房屋到该收集器的距离之和。你的任务是放置收集器并分配房屋，使得这些距离之和的最大值尽可能小。计算并输出该值。

输入格式

在本题中，$L = 2^{30}$。

第一行包含两个整数 $n$ 和 $k$ ($1 \le k \le n \le 1\,000\,000$)。此外有一个特殊条件：如果 $n \ge 100$，则 $10 \le k \le \frac{n}{10}$ 且 $n \pmod k = 0$。

第二行包含两个整数 $seed$ 和 $add$ ($1 \le seed, add < L$)。在所有测试用例中，这些数字均均匀随机选择。如果我们用 $a_i$ 表示第 $i$ 个点的坐标，则坐标可以通过以下伪代码计算：

1. for (i = 0; i < n; i++) {
2. seed = (seed * 239017 + add) mod L;
3. ai = seed;
4. }

输出格式

输出一个整数：所有收集器中，分配给该收集器的房屋到该收集器的距离之和的最大值的最小值。

样例

样例输入 1

10 2
13 123

样例输出 1

626098570

样例输入 2

10 3
13 123

样例输出 2

302532222

样例输入 3

10 10
13 123

样例输出 3

0

说明

生成器生成的点为：3107344, 752440587, 778714046, 266135273, 241409356, 201905063, 489905338, 937040197, 1024665608, 579507651。

请注意你的实现。时间限制非常紧。