Problems

# Sparse Tables

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 (1n105, m107) and a1 (1a1 < 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 (1u1, v1n) - 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).

Time limit 2 seconds
Memory limit 128 MiB
Input example #1
10 8 12345
3 9

Output example #1
5 3 1565158

Author В.Гольдштейн
Source Зимние сборы в Харькове 2010 День 2