ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Сборники > Kovrov IT 2009 > задача:


C. Meat store

Задачи сборника

• A. Tetris 3D
• B. Knights of the Rook
• C. Meat store
• D. Many-coloured roads
• E. Kovrov
• F. Interesting permutations
• G. What about judges?
• H. Triangles
• I. ATM

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Автор: Дмитрий Шевченко, ВлГУ.

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 ≤ 216; 1 ≤ KM; 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

Для отправки решений необходимо выполнить вход.

www.contester.ru