Во время расследования происхождения Диаволо, Джорно получает от Полнареффа секретный код. Код можно представить в виде бесконечной последовательности целых положительных чисел: \(a_1, a_2, \dots \). Джорно сразу видит закономерность, лежащую в основе кода. Первые \(n\) чисел \(a_1, a_2, \dots, a_n\) являются известными. Для \(i > n\) значение \(a_i\) равно \((a_{i-n}\ |\ a_{i-n+1})\), где \(|\) обозначает операцию побитового ИЛИ.
Части информации о Диаволо скрыты в \(q\) вопросах. Каждый вопрос связан с положительным целым числом \(v\), а ответом на него является наименьший индекс \(i\), такой, что \(a_i > v\). Если такого \(i\) не существует, то ответом будет \(-1\). Помогите Джорно ответить на вопросы!
Выходные данные
Выведите \(q\) чисел. Число \(i\) является ответом на \(i\)-й вопрос, заданный Джорно.
Примечание
В первом примере \(a = [2,1,3,3,\ldots]\).
- Для первого вопроса, \(a_1=2\) – элемент с наименьшим индексом, больший чем \(1\).
- Для второго вопроса, \(a_3=3\) – элемент с наименьшим индексом, больший чем \(2\).
- Для третьего вопроса, нет индекса \(i\), такого что \(a_i > 3\).
.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2 3
2 1
1
2
3
4 5
0 2 1 3
0
1
2
3
4
5 5
1 2 3 4 5
7
2
6
0
4
|
1
3
-1
2
2
4
-1
-1
-1
3
8
1
5
|