## Linear congruential generator

We have designed and implemented a new prime factorization algorithm. It is believed that the most challenging inputs to the algorithm are integers which are the product of K distinct primes. We would like to test the algorithm on a sequence of integers generated by a linear congruential generator. The question is how to choose the generator seed so that many challenging inputs are generated.

### The task

You are given parameters of a linear congruential generator. Your task is to compute the seed of the generator which will produce a sequence of N pseudorandom values containing as many as possible integers whose prime factorization consists of exactly K distinct primes.

### Input

The input is one line containing integers A, C, M, K, N separated by a space. Values A, C, M determine linear congruential generator given by formula
x_{i+1}=Ax_{i}+C mod M.
It is guaranteed that the generator has a period of length M. Value N is the number of inputs we are supposed to generate from
a chosen seed to test the algorithm. The generated values are thus x_{1}, x_{2},...,x_{N} where x_{1} equals the seed.

Values of A, C and M are not greater than 3 × 10^{8}. Moreover, 1 ≤ K ≤ 10 and 1 ≤ N ≤ M.

### Output

The output is one line containing two integers S and I separated by a space. S is the optimal seed, I is the number of the most challenging inputs
that will be generated from S. If more seeds generate the same number of the most challenging inputs, S is that seed among them which is
generated by the generator from the initial value x_{1}=0 earlier than the other seeds.

### Example 1

**Input**

5 11 8 1 4

**Output**

0 3The generator produces numbers 0, 3, 2, 5, 4, 7, 6, 1. Since K=1, the most challenging inputs are primes. If seed 0 is chosen, primes 2, 3 and 5 are included in the generated sequence of length N=4. This is the optimal setting as a sequence of length 4 cannot include all 4 primes produced by the generator.

### Example 2

**Input**

5 3 16 2 7

**Output**

8 3The produced numbers are sequentially 0, 3, 2, 13, 4, 7, 6, 1, 8, 11, 10, 5, 12, 15, 14, 9. Since K=2, the most challenging inputs are those numbers in 0,..,15 that are products of two distinct primes (6, 10, 14, 15). The optimal seed is thus 8.

### Example 3

**Input**

17 9 32 2 10

**Output**

13 5

### Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.

**Link to public data set**