给定一个大小为 n 的数组 a,并对其进行 q 查询。有两种类型的查询:
- 1 li ri — 向右执行段 [li, ri] 的循环移位。也就是说,对于每个 x,使得 li ≤ x < ri ax + 1 的新值等于 ax 的旧值,并且 ali 的新值等于 ari 的旧值;
- 2 li ri — 反转段 [li, ri]。
数组 b1, b2, ..., bm 中有 m 个重要索引。对于每个 i,使得 1 ≤ i ≤ m,您必须在执行所有查询后输出在数组中具有索引 bi 的数字。
输入
第一行包含三个整数 n、q 和 m (1 ≤ n, q ≤ 2·105, 1 ≤ m ≤ 100)。
第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 109)。
接下来是 q 行。其中第 i 个包含三个整数 ti、li、ri,其中 ti 是第 i 个查询的类型,[li, ri] 是执行该查询的段(1 ≤ ti ≤ 2, 1 ≤ li ≤ ri ≤ n)。
最后一行包含 m 个整数 b1, b2, ..., bm (1 ≤ bi ≤ n) — 数组的重要索引。
输出
打印 m 个数字,其中第 i 个等于所有查询完成后索引 bi 处的数字。
示例
输入 #1
6 3 5 1 2 3 4 5 6 2 1 3 2 3 6 1 1 6 2 2 1 5 3
输出 #1
3 3 1 5 2