Ива дала Паву массив \(a\) из \(n\) элементов.
Пусть \(f(l, r) = a_l \ \& \ a_{l+1} \ \& \dots \& \ a_r\) (здесь \(\&\) обозначает побитовое И).
Обратите внимание, что \(f(l, r)\) не определено, если \(l>r\).
Ива также дала Паву \(q\) запросов.
Каждый запрос состоит из 2 чисел, \(k\) и \(l\), и она хочет, чтобы Пав нашел наибольший индекс \(r\) (\(l \le r \le n\)), такой что \(f(l, r) \ge k\).
Пав хочет решить эту задачу быстро, потому что он не хочет расстроить Иву. Он нуждается в вашей помощи.
Примечание
В первом наборе примера \(n=5\), и массив \(a = [15, 14, 17, 42, 34]\)
Первый запрос просит найти наибольший индекс \(r\), такой что \(f(1, r) \ge 7\).
\(f(1,1) = 15, \ f(1, 2) = 14, \ f(1,3)=0 \ f(1, 4)=0 \ f(1, 5)=0\), поэтому ответ \(r=2\).
Второй запрос просит найти \(f(2, r) \ge 15\). Поскольку такой \(r\) не существует, ответ \(-1\).
Третий запрос просит найти \(f(4, r) \ge 5\). \(f(4, 4) = 42, \ f(4, 5) = 34\), поэтому ответ \(r=5\).
Во втором наборе примера \(n=5\), и массив \(a= [7, 5, 3, 1, 7]\).
Для первого запроса, \(f(1, r) \ge 7\).
\(f(1, 1)=7, \ f(1, 2)=5, \ f(1, 3) = 1, \ f(1,4) = 1, \ f(1, 5)=1\), поэтому ответ на этот запрос \(1\).
Для второго запроса, \(f(5, r) \ge 7\).
\(f(5, 5) = 7\), поэтому ответ \(5\).
Для третьего запроса, \(f(2, r) \ge 3\).
\(f(2, 2) = 5, \ f(2, 3) = 1, \ f(2, 4) = 1, \ f(2, 5) = 1\), поэтому ответ \(2\).