Consider an array of integers (C = c_1, c_2, \ldots, c_n) of length (n). Let's build the sequence of arrays (D_0, D_1, D_2, \ldots, D_{n}) of length (n+1) in the following way: The first element of this sequence will be equals (C): (D_0 = C). For each (1 \leq i \leq n) array (D_i) will be constructed from (D_{i-1}) in the following way: Let's find the lexicographically smallest subarray of (D_{i-1}) of length (i). Then, the first (n-i) elements of (D_i) will be equals to the corresponding (n-i) elements of array (D_{i-1}) and the last (i) elements of (D_i) will be equals to the corresponding elements of the found subarray of length (i). Let's find the lexicographically smallest subarray of (D_{i-1}) of length (i). Then, the first (n-i) elements of (D_i) will be equals to the corresponding (n-i) elements of array (D_{i-1}) and the last (i) elements of (D_i) will be equals to the corresponding elements of the found subarray of length (i). Array (x) is subarray of array (y), if (x) can be obtained by deletion of several (possibly, zero or all) elements from the beginning of (y) and several (possibly, zero or all) elements from the end of (y). For array (C) let's denote array (D_n) as (op(C)). Alice has an array of integers (A = a_1, a_2, \ldots, a_n) of length (n). She will build the sequence of arrays (B_0, B_1, \ldots, B_n) of length (n+1) in the following way: The first element of this sequence will be equals (A): (B_0 = A). For each (1 \leq i \leq n) array (B_i) will be equals (op(B_{i-1})), where (op) is the transformation described above. She will ask you (q) queries about elements of sequence of arrays (B_0, B_1, \ldots, B_n). Each query consists of two integers (i) and (j), and the answer to this query is the value of the (j)-th element of array $$$B_