유일한 암호화 키

많은 암호(cipher)의 안전성은 키가 유일하며 절대 재사용되지 않는다는 사실에 크게 의존합니다. 동일한 키가 서로 다른 여러 메시지를 암호화하는 데 사용되면 비교적 강력한 암호라도 깨질 수 있으므로, 이 성질은 매우 중요합니다.

이 문제에서는 키의 반복(중복) 사용을 탐지합니다. 메시지를 암호화하는 데 사용된 키의 수열이 주어질 때, 지정된 구간 안에서 두 번 이상 사용된 키가 있는지 판별하는 것이 목표입니다.

입력은 여러 개의 암호 설명(description)으로 이루어집니다. 각 설명은 공백으로 구분된 두 정수 $M$과 $Q$가 담긴 한 줄로 시작합니다. $M$ ($1 \le M \le 10^6$)은 암호화된 메시지의 개수이고, $Q$ ($0 \le Q \le 10^6$)는 질의의 개수입니다.

이어지는 $M$개의 줄에는 각각 하나의 정수 $K_i$ ($0 \le K_i \le 2^{30}$)가 있으며, 이는 $i$번째 메시지를 암호화하는 데 사용된 키의 식별자입니다. 그다음 $Q$개의 줄에는 각각 하나의 질의가 있습니다. 각 질의는 두 정수 $B_j$와 $E_j$ ($1 \le B_j \le E_j \le M$)로 주어지며, 확인하려는 메시지 구간을 나타냅니다.

각 설명 뒤에는 빈 줄이 하나 있습니다. 입력은 $M$과 $Q$ 자리에 두 개의 0이 있는 줄로 종료됩니다.

각 질의에 대해 한 줄을 출력합니다. $B_j$번째부터 $E_j$번째까지(양 끝 포함) 메시지를 암호화하는 데 사용된 키가 모두 서로 다르면 문자열 OK를 출력합니다. 그렇지 않다면, 그 구간 안에서 두 번 이상 등장하는 키 식별자 중 가장 작은 값을 출력합니다.

서로 다른 설명에 속한 답 사이에는 빈 줄을 하나 넣어 구분합니다.