该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

小明有 $n$ 个数，他希望你找出其中第 $k$ 小的数。

初始代码中已经写好了大部分代码，请在注释的地方写下相应的代码。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <ctime>
using namespace std;
int a[10000005], n, k, x, m;
void quick_sort(int l, int r) {
    if (l >= r) {
        return;
    }
    int p1 = l, p2 = r;
    swap(a[l], a[rand() % (r - l + 1) + l]);
    int pivot = a[l];
    while (p1 < p2) {
        while (a[p2] >= pivot && p1 < p2) {
            p2--;
        }
        while (a[p1] <= pivot && p1 < p2) {
            p1++;
        }
        if (p1 < p2) {
            swap(a[p1], a[p2]);
        }
    }
    swap(a[l], a[p1]);
    // 请在这里写下合适的代码

}
int main() {
    freopen("kth.in", "r", stdin);
    freopen("kth.out", "w", stdout);
    srand(time(NULL));
    cin >> n >> k;
    cin >> a[0] >> x >> m;
    for (int i = 1; i < n; i++) {
        a[i] = (long long)a[i - 1] * x % m;
    }
    quick_sort(0, n - 1);
    cout << a[k - 1] << endl;
    return 0;
}

输入格式

第一行两个整数 $n,k （1≤n≤10^7,1\leq k\leq n）$，两数之间以一个空格分隔。

第二行三个整数 $a,x,m（1≤a,x,m≤10^9）$，这两个数字用来生成这 $n$ 个数，因为 $n$ 太大了，需要你在程序中生成，第 $1$ 个数是 $a$ ，后边的数 $num_i=num_{i-1}× x mod m$，相邻两数之间以一个空格分隔。

输出格式

输出有且仅有一行，包含一个整数，表示这 $n$ 个数中的第 $k$ 小数。

输出时每行末尾的多余空格，不影响答案正确性

要求使用「文件输入输出」的方式解题，输入文件为 kth.in，输出文件为 kth.out

样例输入

3 2
1 2 3

样例输出

1