Lonely Number

A number \( x \) is called a Lonely Number if and only if \( x \) is a prime number and \( x \) gives a remainder \( r \) when divided by \( m \). Given four positive integers \( n, m, r, k \), your task is to find the \( k \)th largest lonely number among the numbers from 1 to \( n \). If there are fewer than \( k \) lonely numbers, print \( -1 \).

Example: Consider the numbers \( 3, 5, 11, 7 \). When sorted in descending order, \( 7 \) is the second largest number, so we say \( 7 \) is the second largest lonely number.

inputFormat

The input consists of a single line containing four space-separated positive integers: \( n \), \( m \), \( r \), and \( k \).

outputFormat

Print a single integer representing the \( k \)th largest lonely number in the range \( [1, n] \). If there are fewer than \( k \) lonely numbers, output \( -1 \).

sample

20 4 3 1

19