Given an array of (pseudo) random numbers generated by the C++ function below, your task is to find the K-th smallest number of all the numbers.

unsigned array[5000000];
void randomize(unsigned a,unsigned b,unsigned mod)
{
for( int i=0 ; i<5000000 ; i++ )
{
a = 31014 * (a & 65535) + (a >> 16);
b = 17508 * (b & 65535) + (b >> 16);
array[i] = ((a << 16) + b) % mod;
}
}

Note that the computation might overflow, but we only care about the last 32 bit of each result so it doesn't matter.

Input

One line with 4 numbers (a, b, mod, K) separated by space.

0 < a, b < 65535

2 < mod < 2³²-1

1 < K < 5x10⁶

Output

K-th smallest number of all the generated numbers.

Example

Input:
2 3 100000007 23
Output:
434