A brand new equipment has been installed in meat store recently - the electronic seller. Now the customer can simply come and press the button, and the seller will select the meat piece automatically. The pieces are stored in a special container inside the seller. Different pieces have different weights (all weights are distinct). There are N pieces of meat in the container. The seller works the following way. There is a special register X in seller circuit, with initial value set to 0. In order to satisfy the customer the seller does the following:
All pieces are numbered from 0 to N-1 in order of weight increase.
The piece with number equal to register X value is selected.
The seller retrieves the selected piece from the container and hands it to the customer.
A request for a new piece is sent to a special warehouse. There are M pieces of meat at the warehouse initially (all weights are distinct). When a request comes, a piece with maximal weight is selected and sent to the container. Thus, the total number of pieces in container remains the same, and the warehouse gets empty after serving M requests.
A new value XAB is written into register X which is calculated like this:
XAB = (X · A + B) mod N
Suppose, that the customer requires K pieces. You must write a program that will calculate the sequence of pieces given out by the seller.

Input
The first line contains 5 integer numbers N, M, A, B, K (2 ≤ N, M ≤ 2^16; 1 ≤ K ≤ M; 0 < A < N; 0 ≤ B < N). The second line contains N integers - weights of pieces in the container. The third line contains M integers - weights of pieces in the warehouse. All weights are distinct. All weights are between 1 and 231-1 inclusively.
Output
Output K numbers separated by spaces - weights of pieces in order of giving out.

Input 1    Output 1
3 2 1 1 2
5 1 3
4 2
1 4
Input 2    Output 2
3 3 2 1 3
5 2 3
1 4 6
2 5 3

//Already I compiled programm but n=65536 time limited
This is meat store`s code in c++
#include <iostream.h>
#include <conio.h>
#include <algorithm>
using namespace std;
void qs(int* y, int first, int last)
{
    int i = first, j = last, x = y[(first + last) / 2],xx;

    do {
        while (y[i] < x) i++;
        while (y[j] > x) j--;

        if(i <= j) {
            if (y[i] > y[j]) {xx=y[i];y[i]=y[j];y[j]=xx;}
            i++;
            j--;
        }
    } while (i <= j);

    if (i < last)
        qs(y, i, last);
    if (first < j)
        qs(y, first, j);
}
int main()
{
int n,m,k,a,b;
cin>>n>>m>>a>>b>>k;
int *y,*z,xx;
y=new int[n+1];
z=new int[m+1];
for(int i=0;i<n;i++)
cin>>y[i];
for(int j=0;j<m;j++)
cin>>z[j];
qs(y,0,n-1);
qs(z,0,m-1);
int x=0;
cout<<y[0]<<" ";
int pp;
for(int t=1;t<k;t++)
{
       pp=z[m-t];
        y[x]=y[n/2];
        y[n/2]=pp;
        qs(y,0,n-1);
        x=(x*a+b) % n;
        cout<<y[x]<<" ";

}
//getch();

       // return 0;
}

Edited by author 03.11.2014 22:16

Edited by author 03.11.2014 22:21