给定一个包含 $N$ 个整数的数组 $A$。 同时给定两个整数 $K$ 和 $L$。 你需要将整个数组 $A$ 分割成恰好 $K$ 个非空区间，使得每个区间的长度都不超过 $L$。 区间 $[S, E]$ 的代价是数组 $A$ 中下标在 $[S, E]$ 范围内的所有元素的按位异或和。 一种分割方案的得分是该方案中所有 $K$ 个区间的代价的最大值。你对“最优分割”感兴趣：即最小化分割得分的方案。由于这对于你来说太简单了，所以问题被反转了。 已知最小得分：原问题的答案不大于 $X$。现在你想要求出 $K$ 的最大值。

输入格式

第一行包含三个整数 $N, X$ 和 $L$（$1 \le L \le N \le 10^5$，$0 \le X < 268\,435\,456$）。 第二行包含三个整数 $A_1, P$ 和 $Q$（$0 \le A_1, P, Q < 268\,435\,456$）。数组 $A$ 的所有后续整数通过以下方式生成：对于每个整数 $1 < k \le N$，$A_k = (A_{k-1} \cdot P + Q) \pmod{268\,435\,456}$。

输出格式

输出一行包含答案。如果答案不存在，则输出 0。

样例

输入 1

3 1 2
1 1 1

输出 1

2

输入 2

3 0 3
1 1 1

输出 2

1