K-я порядковая статистика

Массив из $n$ чисел задан генератором: $a_1 = x$, для $i > 1$ $a_i = (A \cdot a_{i-1} + B) \bmod M$. Найдите число, которое окажется на $k$-м месте после сортировки массива по возрастанию (места нумеруются с $1$).

В одной строке шесть целых чисел: $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$).

Одно число — $k$-я порядковая статистика.

Полная сортировка — $O(n \log n)$, но если нужно одно место, quickselect работает в среднем за $O(n)$: разбейте массив вокруг случайного опорного элемента и продолжайте только в той части, куда попало $k$-е место. В C++ это std::nth_element.

$A \cdot a_{i-1}$ достигает $10^{18}$ — умножайте в 64-битном типе. В первом примере массив $3, 7, 5, 1, 3$, после сортировки $1, 3, 3, 5, 7$, ответ $3$.