Sereja and Prefixes

题意翻译

题面： 初始有一个空序列,有m次操作,每次给出一种操作: 1. 在序列末尾添加一个数x. 2. 将序列长度为l的前缀复制c次插入到序列末尾. 有n组询问，每组询问为操作完的序列上第i号点的值. 输入数据： 第一行一个m 接下来m行操作,形如<1,x> or <2,l,c> 第m+2行一个n 接下来n个数,分别询问第i号位上的值. 输出数据： 仅一行,n个询问的输出. 数据范围： m:[1,1e5] x:[1,1e5] l:[1,1e5] c:[1,1e4] n:[1,1e5] i<sizeof(long long) 注意： 记得开long long! 翻译贡献者：尘染梦

题目描述

Sereja loves number sequences very much. That's why he decided to make himself a new one following a certain algorithm. Sereja takes a blank piece of paper. Then he starts writing out the sequence in $ m $ stages. Each time he either adds a new number to the end of the sequence or takes $ l $ first elements of the current sequence and adds them $ c $ times to the end. More formally, if we represent the current sequence as $ a_{1},a_{2},...,a_{n} $ , then after we apply the described operation, the sequence transforms into $ a_{1},a_{2},...,a_{n}[,a_{1},a_{2},...,a_{l}] $ (the block in the square brackets must be repeated $ c $ times). A day has passed and Sereja has completed the sequence. He wonders what are the values of some of its elements. Help Sereja.

输入输出格式

输入格式

The first line contains integer $ m $ $ (1<=m<=10^{5}) $ — the number of stages to build a sequence. Next $ m $ lines contain the description of the stages in the order they follow. The first number in the line is a type of stage (1 or 2). Type 1 means adding one number to the end of the sequence, in this case the line contains integer $ x_{i} $ $ (1<=x_{i}<=10^{5}) $ — the number to add. Type 2 means copying a prefix of length $ l_{i} $ to the end $ c_{i} $ times, in this case the line further contains two integers $ l_{i},c_{i} $ $ (1<=l_{i}<=10^{5},1<=c_{i}<=10^{4}) $ , $ l_{i} $ is the length of the prefix, $ c_{i} $ is the number of copyings. It is guaranteed that the length of prefix $ l_{i} $ is never larger than the current length of the sequence. The next line contains integer $ n $ $ (1<=n<=10^{5}) $ — the number of elements Sereja is interested in. The next line contains the numbers of elements of the final sequence Sereja is interested in. The numbers are given in the strictly increasing order. It is guaranteed that all numbers are strictly larger than zero and do not exceed the length of the resulting sequence. Consider the elements of the final sequence numbered starting from $ 1 $ from the beginning to the end of the sequence. Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

输出格式

Print the elements that Sereja is interested in, in the order in which their numbers occur in the input.

输入输出样例

输入样例 #1

6
1 1
1 2
2 2 1
1 3
2 5 2
1 4
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

输出样例 #1

1 2 1 2 3 1 2 1 2 3 1 2 1 2 3 4

题意翻译

题面： 初始有一个空序列,有m次操作,每次给出一种操作: 1. 在序列末尾添加一个数x. 2. 将序列长度为l的前缀复制c次插入到序列末尾. 有n组询问，每组询问为操作完的序列上第i号点的值. 输入数据： 第一行一个m 接下来m行操作,形如<1,x> or <2,l,c> 第m+2行一个n 接下来n个数,分别询问第i号位上的值. 输出数据： 仅一行,n个询问的输出. 数据范围： m:[1,1e5] x:[1,1e5] l:[1,1e5] c:[1,1e4] n:[1,1e5] i<sizeof(long long) 注意： 记得开long long! 翻译贡献者：尘染梦