\(b_1, b_2, \dots, b_n\) (\(n > 1\)) массивінің сұлулығы деп барлық \(i, j\) (\(1 \leq i < j \leq n\)) жұптары үшін \(|b_i - b_j|\) минималды мәнін айтамыз, мұнда \(b_i\) және \(b_j\) массив элементтері болып табылады.

Сізге ұзындығы \(n\) болатын, \(a_1, a_2, \dots, a_n\) бүтін сандар тізбегі берілген. Сонымен қатар, \(q\) сұраулар бар, олардың әрқайсысы екі бүтін \(x\) және \(k\) сандарымен сиппаталады.

Әр сұрау \((x, k)\) үшін сізге келесі әрекеттерді орындау қажет:

• \(b\) массивің құру. Ол \(x\) санынан дәл \(k\) битке ерекшеленетің \(a\)-ның барлық элементтерінен тұрады.

• \(b\) массивінің сұлулығын табу, яғни \(b_i\) және \(b_j\) элементтерінің барлық жұптары үшін \(|b_i - b_j|\) минималды мәнін есептеу.

• Егер \(b\) массивіндегі элементтер саны екіден аз болса, онда массивтің сұлулығы \(-1\) деп есептеледі.

Сізге барлық \(q\) сұрауларға жауап беру қажет. Әр сұрауға жауаптар берілген ретімен шығарылуы керек.

Енгізу

Бірінші жолда екі бүтін сан \(n\) және \(q\) (\(1 \leq n \leq 2^{17}\), \(1 \leq q \leq 10^6\)) — массив \(a\) өлшемі және сұраулар саны.

Екінші жолда \(n\) бүтін сандар \(a_1, a_2, \dots, a_n\) (\(0 \leq a_i < 2^{17}\)) — массив элементтері.

Келесі \(q\) жолдың әрқайсысында екі бүтін сан \(x\) және \(k\) (\(0 \leq x < 2^{17}\), \(0 \leq k \leq 17\)) — сұрау параметрлері.

Шығару

Әр сұрау үшін, барлығы \(q\) сұрауға, бір бүтін санды шығарыңыз — осы сұрауға сәйкес келетін \(b\) массивінің сұлулығы.

Егер \(b\) массивінде екіден аз элемент болса, \(-1\) шығарыңыз.

Бағалау жүйесі

Мысалдар

Енгізу 1

9 6
1 2 3 4 5 6 7 8 7
0 1
0 2
3 1
15 2
26 3
1 3

Жауап 1

1
1
0
1
3
-1