Sparse Tables#691
Sign in

Sparse Tables

2 seconds
128 megabytes
Hard

An array of integers is given. Write a program that answers queries of the following form: find the minimum value in the segment from to , inclusive.

Input

The first line contains three integers: n, m~(1 \le n \le 10^5, m \le 10^7), and a_1~(1 \le a_1 < 16714589) — the number of elements in the array, the number of queries, and the first element of the array, respectively.

The second line contains two integers u_1 and v_1~(1 \le u_1, v_1 \le n), describing the first query.

The elements a_2, a_3, \ldots, a_n are defined by the following formula:

a_{i+1} = (23 \cdot a_i + 21563) \bmod 16714589

For example, if n = 10 and a_1 = 12345, the array will be:

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

The queries are generated as follows:

u_{i+1} = ((17 \cdot u_i + 751 + ans_i + 2i) \bmod n) + 1 \\ v_{i+1} = ((13 \cdot v_i + 593 + ans_i + 5i) \bmod n) + 1

Here, ans_i denotes the answer to the -th query.

Output

Print u_m, v_m, and ans_m — the parameters of the last query and its answer.

Examples

Example 1

Loading
Loading