题目描述

称一个数 $x$ 是孤独数，当且仅当 $x$ 是质数且 $x$ 除以 $m$ 的余数是 $r$。

给出正整数 $n,m,r,k$，求 $1\sim n$ 内第 $k$ 大的孤独数。若不存在输出 $-1$。

例如，$3,5,11,7$ 这四个数中，从大到小排序时 $7$ 是第 $2$ 名，那么我们说 $7$ 是第二大的。

输入格式

输入一行四个正整数 $n,m,r,k$，含义见题目描述。

输出格式

输出一行一个整数，表示 $1\sim n$ 内第 $k$ 大的孤独数，若不存在则输出 $-1$。

样例 #1

样例输入 #1

20 3 2 2

样例输出 #1

11

样例 #2

样例输入 #2

10000 6 4 1

样例输出 #2

-1

样例 #3

样例输入 #3

97 10 7 6

样例输出 #3

7

提示

数据范围

对于全部测试点，保证 $1\leq k\leq n\leq 10000$，$1\leq r<m\leq n$。