The array with n integers is given. Write a program that answers the question: find the minimum on a segment between u and v inclusively.

Input

The first line contains three positive integers n, m (1 ≤ n ≤ 105, m ≤ 107) and a1 (1 ≤ a1 < 16714589) - the number of elements in array, the number of queries and the first element in an array respectively. The second line contains two positive integers u1 and v1 (1 ≤ u1, v1 ≤ n) - the first query.

The elements a2, a3, ..., an are given with the next formula:

ai+1 = (23 · ai + 21563) mod 16714589.

For example, if n = 10, a1 = 12345, we get the next array:

a = (12345, 305498, 7048017, 11694653, 1565158, 2591019, 9471233, 570265, 13137658, 1325095).

The queries are generated this way:

ui+1 = ((17 · ui + 751 + ansi + 2i) mod n) + 1,

vi+1 = ((13 · vi + 593 + ansi + 5i) mod n) + 1,

where ansi is the answer to the i-th query.

Output

Print um, vm and ansm (the values for the last query and the answer to it).