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

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

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

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

Каждая из следующих m строк содержит одно число ki (0 ≤ ki ≤ 230) - идентификатор ключа, используемый для шифрования i - го сообщения. Каждая из следующих q строк содержит один запрос. Каждый запрос задается двумя целыми числами bj и ej (1 ≤ bj ≤ ej ≤ m), задавая интервал сообщений, которые мы хотим проверить.

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

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

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

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