Problem Statement

Shawn is smart,innovative and hardworking.He has managed to program an app which helps us to communicate any people throughout the universe.This made Bebe,a girl from other planet,fall in love with him.She decides to meet him only when he solves the following statement.He needs your help !!

You are given an array A of N elements.All elements are distinct .You are also given an integer K.
You have been given Q queries.Each of those queries consists of L and R.
For each of those queries find the minimum/smallest (starting from 1) missing number in an array from range L to R which is strictly greater than K .

Constraints :

• $1 \le N \le 10^5$
• $1 \le A[i] \le 10^6$
• $1 \le Q \le 10^5$
• $1 \le L \le R \le N$
• $1 \le K \le 10^6$

Input

First line contains N and K , implies size of the array and K as explained above.
Next line follows N integers which implies elements of an array.
Then next line contains value Q which is total number of queries to be performed.
Then each of the next Q lines contains L and R.

Output

For each query print the required answer as explained.

Note : Count of missing number always starts from 1 .