#P1422. 沙拉酱前缀

    ID: 304 远端评测题 1000ms 128MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>CodeForces二分查找暴力枚举二分单调性

沙拉酱前缀

Description

沙拉酱非常喜欢数字序列。这正是他要弄一个关于构造序列的算法的原因。

沙拉酱拿了一张白纸。然后他开始用 mm 个步骤来制作一个序列。每一步他要么向这个序列的末尾添加一个数字,要么拿这个序列的开头 ll 个数字,然后在末尾添加 cc 次。对于第二种操作,一般的,如果当前序列是  a1,a2,,ana_1,a_2,\cdots ,a_n  ,那么经过操作之后序列将变成  a1,a2,,an[,a1,a2,,al]a_1,a_2,\cdots ,a_n[,a_1,a_2,\cdots ,a_l]   (方括号里面的内容会重复 cc 次)。

一天过去了,沙拉酱也完成了他的序列。现在他想知道某个位置是什么数字。

Input Format

单组测试数据。 第一行包含一个整数 m(1m105)m (1 \le m \le 10^5) ,表示构造序列的步骤数目。 接下来 mm 行包含每一个步骤的信息。第一个数字是类型 (1(12)2) 。类型 11 表示在序列后面加一个数字,这种情况下后面会跟一个整数 xi(1xi105),xi (1 \le xi \le 10^5), 表示被加在后面的数字。类型 22 表示复制一段长度为 lili 前缀然后接到后面 cici 次,这种情况下后面会跟两个整数 li,ci(1li105,1ci104)li, ci(1 \le li \le 10^5, 1 \le ci \le 10^4)lili 是前缀的长度, cici 是复制的次数。输入中保证 lili 不会大于当前序列的长度。

接下来一行包含一个整数 n(1n105)n (1 \le n \le 10^5) ,表示查询的数量。接下来一行中包含 nn 个正整数,每一个整数表示要查询的位置。题目保证这些数字大小不会超过序列的长度。序列的下标从 11 开始。

Output Format

对于每一个查询,输出对应查询位置的数字。两个查询之间用空格分开。具体格式看样例。

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 2 1 2 3 1 2 1 2 3 1 2 1 2 3 4