У Джейдена есть массив \(a\), который изначально пуст. Ему необходимо выполнить \(n\) операций двух типов в заданном порядке.
- Джейден добавляет целое число \(x\) (\(1 \leq x \leq n\)) в конец массива \(a\).
- Джейден добавляет \(x\) копий массива \(a\) в конец массива \(a\). Другими словами, массив \(a\) становится равным \([a,\underbrace{a,\ldots,a}_{x}]\). Гарантируется, что перед этим была выполнена хотя бы одна операция первого типа.
У Джейдена есть \(q\) запросов. Для каждого запроса вы должны сообщить ему \(k\)-й элемент массива \(a\). Элементы массива нумеруются с \(1\).
Выходные данные
Для каждого набора входных данных выведите \(q\) целых чисел — ответы на запросы Джейдена.
Примечание
В первом наборе входных данных:
- После первой операции \(a = [1]\);
- После второй операции \(a = [1, 2]\);
- После третьей операции \(a = [1, 2, 1, 2]\);
- После четвёртой операции \(a = [1, 2, 1, 2, 3]\);
- После пятой операции \(a = [1, 2, 1, 2, 3, 1, 2, 1, 2, 3, 1, 2, 1, 2, 3, 1, 2, 1, 2, 3]\).
В четвёртом наборе входных данных после всех операций \(a = [1, 2]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
5 10
1 1
1 2
2 1
1 3
2 3
1 2 3 4 5 6 14 15 16 20
10 10
1 3
1 8
2 15
1 6
1 9
1 1
2 6
1 1
2 12
2 10
32752 25178 3198 3199 2460 2461 31450 33260 9016 4996
12 5
1 6
1 11
2 392130334
1 4
2 744811750
1 10
1 5
2 209373780
2 178928984
1 3
2 658326464
2 1000000000
914576963034536490 640707385283752918 636773368365261971 584126563607944922 1000000000000000000
2 2
1 1
1 2
1 2
|
1 2 1 2 3 1 2 3 1 3
9 8 1 3 1 3 6 3 8 8
11 11 11 10 11
1 2
|