D. Повторение в массиве
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Джейдена есть массив $$$a$$$, который изначально пуст. Ему необходимо выполнить $$$n$$$ операций двух типов в заданном порядке.

  1. Джейден добавляет целое число $$$x$$$ ($$$1 \leq x \leq n$$$) в конец массива $$$a$$$.
  2. Джейден добавляет $$$x$$$ копий массива $$$a$$$ в конец массива $$$a$$$. Другими словами, массив $$$a$$$ становится равным $$$[a,\underbrace{a,\ldots,a}_{x}]$$$. Гарантируется, что перед этим была выполнена хотя бы одна операция первого типа.

У Джейдена есть $$$q$$$ запросов. Для каждого запроса вы должны сообщить ему $$$k$$$-й элемент массива $$$a$$$. Элементы массива нумеруются с $$$1$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 5000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \leq n, q \leq 10^5$$$) — количество операций и количество запросов.

Следующие $$$n$$$ строк описывают операции. Каждая строка содержит два целых числа $$$b$$$ и $$$x$$$ ($$$b \in \{1, 2\}$$$), где $$$b$$$ обозначает тип операции. Если $$$b=1$$$, то $$$x$$$ ($$$1 \leq x \leq n$$$) является целым числом, которое Джейден добавляет в конец массива. Если $$$b=2$$$, то $$$x$$$ ($$$1 \leq x \leq 10^9$$$) является количеством копий, которые Джейден добавляет в конец массива.

Следующая строка каждого набора входных данных содержит $$$q$$$ целых чисел $$$k_1, k_2, \ldots, k_q$$$ ($$$1 \leq k_i \leq \min(10^{18}, c)$$$), которые обозначают запросы, где $$$c$$$ — размер массива после выполнения всех $$$n$$$ операций.

Гарантируется, что сумма $$$n$$$ и сумма $$$q$$$ по всем наборам входных данных не превышает $$$10^5$$$.

Выходные данные

Для каждого набора входных данных выведите $$$q$$$ целых чисел — ответы на запросы Джейдена.

Пример
Входные данные
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
Примечание

В первом наборе входных данных:

  • После первой операции $$$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]$$$.