Unique Encryption Keys

The security of many ciphers strongly depends on the fact that the keys are unique and are never re-used. This can be vitally important, since even a relatively strong cipher may be broken if the same key is used to encrypt several different messages.

In this problem, we detect repeated (duplicate) usage of keys. Given a sequence of keys used to encrypt messages, your task is to determine, for a specified interval, whether any key has been used more than once.

The input contains several cipher descriptions. Each description starts with one line containing two integers $M$ and $Q$ separated by a space. $M$ ($1 \le M \le 10^6$) is the number of encrypted messages, and $Q$ ($0 \le Q \le 10^6$) is the number of queries.

Each of the following $M$ lines contains one integer $K_i$ ($0 \le K_i \le 2^{30}$), the identifier of the key used to encrypt the $i$-th message. The next $Q$ lines each contain one query, given by two integers $B_j$ and $E_j$ ($1 \le B_j \le E_j \le M$), the interval of messages to check.

There is one empty line after each description. The input is terminated by a line containing two zeros in place of $M$ and $Q$.

For each query, print one line. Print the string OK if all keys used to encrypt messages between $B_j$ and $E_j$ (inclusive) are pairwise distinct. Otherwise, print the smallest key identifier that occurs at least twice within that interval.

Separate the answers belonging to consecutive descriptions by one empty line.