Se dă un șir a[1], a[2], …, a[n] de numere naturale și un număr natural k.

Cerința

Să se determine cele mai mari k numere din șir.

Date de intrare

Programul citește de la tastatură numerele n, k, A, B, C, D. Șirul de numere se va genera după formulele:

• a[1] = A
• a[i] = (B * a[i-1] + C) % D, pentru i=2..n

Date de ieșire

Programul va afișa pe ecran, ordonate crescător, cele mai mari k numere din șir.

Restricții și precizări

• 1 ≤ n ≤ 5.000.000
• 1 ≤ k ≤ min(100.000, n)
• 1 ≤ A, B, C, D ≤ 1.000.000.000

Exemplu

Intrare

10 4 13 23 47 97

Ieșire

55 56 74 96

Explicație

Se obține șirul de numere a = (13, 55, 51, 56, 74, 3, 19, 96, 24, 17). Cele mai mari patru numere sunt 55, 56, 74, 96.

#include <bits/stdc++.h>
using namespace std;

int n, H[100001], k;
long long a, b, c, d;

void push_up(int k){
    while(k > 1){
        if(H[k] >= H[k / 2])
            return ;
        else
            swap(H[k], H[k / 2]), k /= 2;
    }
}

void push_down(int k, int n){
    while(2 * k <= n){
        int p = 2 * k;
        if(p + 1 <= n && H[p + 1] < H[p])
            p++;
        if(H[k] <= H[p])
            return ;
        else
            swap(H[p], H[k]), k = p;
    }
}

int main(){
    cin >> n >> k >> a >> b >> c >> d;
    H[1] = a;
    for(int i = 2; i <= n; ++i){
        a = (1ll * a * b + c) % d;
        if(i > k){
            if(a > H[1])
                H[1] = a, push_down(1, k);
        }
        else
            H[i] = a, push_up(i);
    }
    while(k > 0){
        cout << H[1] << ' ';
        H[1] = H[k];
        k--;
        push_down(1, k);
    }
    return 0;
}