Унікальні ключі шифрування
Безпека багатьох шифрів значною мірою залежить від унікальності ключів і їх одноразового використання. Це може бути критично важливим, оскільки навіть відносно сильний шифр може бути зламаний, якщо один і той самий ключ застосовується для шифрування кількох різних повідомлень.
У цій задачі ми спробуємо виявити повторне використання ключів. Маючи послідовність ключів, що використовуються для шифрування повідомлень, ваше завдання полягає в тому, щоб визначити, які ключі використовувалися повторно протягом певного періоду часу.
Вхідні дані
Містять кілька описів шифрів. Кожен опис починається з одного рядка, що містить два цілі числа: кількість зашифрованих повідомлень m (1 ≤ m ≤ 10^6) і кількість запитів q (0 ≤ q ≤ 10^6).
Кожен з наступних m рядків містить одне число k[i] (0 ≤ k[i] ≤ 2^30) - ідентифікатор ключа, що використовується для шифрування i-го повідомлення. Кожен з наступних q рядків містить один запит. Кожен запит задається двома цілими числами b[j] і e[j] (1 ≤ b[j] ≤ e[j] ≤ m), що визначають інтервал повідомлень, які ми хочемо перевірити.
Після кожного тесту йде один порожній рядок. Вхідні дані закінчуються рядком, що містить два нулі.
Вихідні дані
Для кожного запиту виведіть один рядок. Рядок повинен містити "OK", якщо всі ключі, використані для шифрування повідомлень між b[j] і e[j] (включно), є унікальними (мають різні ідентифікатори). Якщо деякі з ключів використовувалися повторно, виведіть один ідентифікатор будь-якого такого ключа.
Виведіть один порожній рядок після кожного опису шифру.