K-th order statistic

An array of $n$ numbers is given by a generator: $a_1 = x$, and for $i > 1$ $a_i = (A \cdot a_{i-1} + B) \bmod M$. Find the number at position $k$ after sorting the array in increasing order (positions start from $1$).

A single line with six integers: $n$, $k$, $x$, $A$, $B$, $M$ ($1 \le k \le n \le 3 \cdot 10^6$, $1 \le M \le 10^9$, $0 \le x, A, B < M$).

A single number — the $k$-th order statistic.

A full sort is $O(n \log n)$, but when only one position is needed, quickselect runs in $O(n)$ on average: partition the array around a random pivot and continue only in the part that contains position $k$. In C++ this is std::nth_element.

$A \cdot a_{i-1}$ reaches $10^{18}$ — multiply in a 64-bit type. In the first example the array is $3, 7, 5, 1, 3$, sorted $1, 3, 3, 5, 7$, and the answer is $3$.