该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个 $n\times n$ 的矩阵 $A$，再给定一个数 $k$，求矩阵中所有大小为 $k\times k$ 的子矩阵的中位数的最小值。

一个 $k\times k$ 的矩阵的中位数被定义为将矩阵中的所有数从大到小排序后的第 $\lfloor\frac{k^2}{2}\rfloor+1$ 个数。

输入格式

第一行两个正整数 $n,k$。

第二行两个正整数 $c,d$。

矩阵按照先从左到右再从上到下的顺序生成，且满足递推式 $a = (a + c)$ $\%$ $d$。

输出格式

输出一行一个数，表示中位数的最小值。

输入输出样例 #1

输入 #1

11 4
5 14

输出 #1

4

说明/提示

$1\le k\le n\le 3000,0< c,d\le 10^9$。