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(1\le n\le 10^5,m\le 10^7)$ and $a_1(1\le a_1<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 $u_1$ and $v_1(1\le u_1,v_1\le n)$ — the first query.

The elements $a_2,a_3,...,a_n$ are given with the next formula:

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

The queries are generated this way:

where $an{s}_i$ is the answer to the $i$-th query.

Output

Print $u_m,v_m$ and $an{s}_m$ (the values for the last query and the answer to it).

Examples