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

Разделы > Неотсортированные > задача:


Порядковая статистика

Задачи раздела

• Подсказки к задачам
• Подсказки к задачам
• Подсказки к задачам
• Поедание сыра
• Поиск элемента
• Покер
• Покупка пирожков
• Полибия
• Порядковая статистика
• Порядковая статистика — 2
• Последовательность
• Постиранный пароль
• Постфиксное выражение
• Почти совершенная задача
• Почтовые цифры
• Почтовый принтер
• Правый двоичный поиск

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

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

Лимит времени 5000/5000/5000/5000 мс. Лимит памяти 524288/524288/524288/524288 Кб.

Порядковая статистика
Порядковая статистика
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив, элементами которого являются целые числа. Начальный элемент массива равен A0, а все остальные вычисляются по правилу (запись обозначает операцию взятия остатка от деления).

Определите, какой элемент будет находиться на K-м месте, если массив будет отсортирован по неубыванию.

Входные данные

Первая строка содержит целое число N (1 ≤ N ≤ 4·107) — количество элементов массива.

Вторая строка содержит целые числа A0, X и Y (0 ≤ A0, X, Y ≤ 109) — соответственно начальный элемент массива и параметры для вычисления остальных элементов.

Третья строка содержит целое число K (0 ≤ K ≤ N - 1) — индекс, для которого требуется определить значение элемента.

Выходные данные

Выведите одно целое число — значение элемента, имеющего индекс K в отсортированном массиве.

Примеры

Входные данные
10
123 10000 1
2
Выходные данные
30605701
Входные данные
10
123 10000 1
5
Выходные данные
78586011
Входные данные
10
123 10000 1
8
Выходные данные
490003064

Примечание

В показанных примерах рассматривается массив

{123, 1230001, 300009917, 99149001, 490003064, 30605701, 57007859, 78586011, 860104506, 44999794}.

После сортировки он будет иметь следующий вид:

{123, 1230001, 30605701, 44999794, 57007859, 78586011, 99149001, 300009917, 490003064, 860104506}.

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

www.contester.ru