Дед Мороз и Снегурочка приходят на детские утренники с мешком конфет. Дед Мороз делит конфеты поровну между всеми присутствующими детьми (детей на утреннике никогда не бывает больше 100), а оставшиеся конфеты отдает Снегурочке. Снегурочка каждый раз записывает в блокнот количество полученных конфет. Если конфеты разделились между всеми детьми без остатка, Снегурочка ничего не получает и ничего не записывает. Когда утренники закончились, Деду Морозу стало интересно, какое число чаще всего записывала Снегурочка.
Дед Мороз и Снегурочка – волшебники, поэтому число утренников N, на которых они побывали, может быть очень большим.
Напишите программу, которая будет решать эту задачу. Перед текстом программы кратко опишите алгоритм решения задачи, укажите используемый язык программирования и его версию. Желательно, чтобы программа была эффективной как по времени работы, так и по используемой памяти.
Программа будет считаться эффективной по памяти, если используемая память не зависит от размера входных данных (то есть числа утренников). Программа будет считаться эффективной по времени, если при увеличении размера входных данных N в t раз (t – любое число) время её работы увеличивается не более чем в t раз.
Гарантируется выполнение следующих соотношений: \(1 <= N <= 10000\), \(1 <= D <= 100\) (для каждого D), \(D <= K <= 1000\) (для каждой пары D, K)
Программа должна вывести одно число – то, которое Снегурочка записывала чаще всего. Если несколько чисел записывались одинаково часто, надо вывести большее из них. Если Снегурочка ни разу ничего не записывала, надо вывести ноль.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
7
10 58
15 315
20 408
100 1000
32 63
32 63
11 121
|
31 |