eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Уникальные ключи шифрования

Уникальные ключи шифрования

Ліміт часу 3 секунди
Ліміт використання пам'яті 128 MiB

Безопасность многих шифров сильно зависит от того, что ключи уникальны и никогда не используются повторно. Это может быть жизненно важным, поскольку относительно сильный шифр может быть взломан, если один и тот же ключ используется для шифрования нескольких разных сообщений.

В этой задаче мы попытаемся обнаружить повторяющееся (дублированное) использование ключей. Имея последовательность ключей, используемых для шифрования сообщений, Ваша задача состоит в том, чтобы определить, какие ключи использовались повторно в течение определенного периода времени.

Вхідні дані

Содержит несколько описаний шифров. Каждое описание начинается с одной строки, содержащей два целых числа: количество зашифрованных сообщений m (1m10^6) и количество запросов q (0q10^6).

Каждая из следующих m строк содержит одно число k[i] (0k[i]2^30) - идентификатора ключа, используемого для шифрования i - го сообщения. Каждая из следующих q строк содержит один запрос. Каждый запрос задается двумя целыми числами b[j] и e[j] (1b[j]e[j]m), задавая интервал сообщений, которые мы хотим проверить.

После каждого теста идет одна пустая строка. Входные данные заканчиваются строкой, содержащей два нуля.

Вихідні дані

Для каждого запроса выведите одну строку. Строка должна содержать "OK", если все ключи, используемые для шифрования сообщений между b[j] и e[j] (включительно), взаимно различаются (имеют разные идентификаторы). Если некоторые из ключей использовались неоднократно, выведите один идентификатор любого такого ключа.

Выведите одну пустую строку после каждого описания шифра.

Приклад

Вхідні дані #1
10 5
3
2
3
4
9
7
3
8
4
1
1 3
2 6
4 10
3 7
2 6

5 2
1
2
3
1
2
2 4
1 5

0 0
Вихідні дані #1
3
OK
4
3
OK

OK
1
Джерело 2011 ACM Central Europe (CERC), Прага, Ноябрь 11 - 13, Задача C