English · Original
Chinese · Translation
Formal · Original
You are given an array _a_ of size _n_, and _q_ queries to it. There are queries of two types:
* 1 _l__i_ _r__i_ — perform a cyclic shift of the segment \[_l__i_, _r__i_\] to the right. That is, for every _x_ such that _l__i_ ≤ _x_ < _r__i_ new value of _a__x_ + 1 becomes equal to old value of _a__x_, and new value of _a__l__i_ becomes equal to old value of _a__r__i_;
* 2 _l__i_ _r__i_ — reverse the segment \[_l__i_, _r__i_\].
There are _m_ important indices in the array _b_1, _b_2, ..., _b__m_. For each _i_ such that 1 ≤ _i_ ≤ _m_ you have to output the number that will have index _b__i_ in the array after all queries are performed.
## Input
The first line contains three integer numbers _n_, _q_ and _m_ (1 ≤ _n_, _q_ ≤ 2·105, 1 ≤ _m_ ≤ 100).
The second line contains _n_ integer numbers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 109).
Then _q_ lines follow. _i_\-th of them contains three integer numbers _t__i_, _l__i_, _r__i_, where _t__i_ is the type of _i_\-th query, and \[_l__i_, _r__i_\] is the segment where this query is performed (1 ≤ _t__i_ ≤ 2, 1 ≤ _l__i_ ≤ _r__i_ ≤ _n_).
The last line contains _m_ integer numbers _b_1, _b_2, ..., _b__m_ (1 ≤ _b__i_ ≤ _n_) — important indices of the array.
## Output
Print _m_ numbers, _i_\-th of which is equal to the number at index _b__i_ after all queries are done.
[samples]
给定一个大小为 $n$ 的数组 $[a]$，以及 $q$ 个对其的查询。查询有两种类型：
数组中有 $m$ 个重要索引 $[b1], [b2], ..., [bm]$。对于每个满足 $1 ≤ i ≤ m$ 的 $i$，你需要输出在所有查询执行完毕后，数组中索引为 $[bi]$ 的元素。
第一行包含三个整数 $n$, $q$ 和 $m$（$1 ≤ n, q ≤ 2·10^5$, $1 ≤ m ≤ 100$）。
第二行包含 $n$ 个整数 $[a1], [a2], ..., [an]$（$1 ≤ ai ≤ 10^9$）。
接下来 $q$ 行，每行包含三个整数 $[ti], [li], [ri]$，其中 $[ti]$ 是第 $i$ 个查询的类型，$[li, ri]$ 是该查询作用的区间（$1 ≤ ti ≤ 2$, $1 ≤ li ≤ ri ≤ n$）。
最后一行包含 $m$ 个整数 $[b1], [b2], ..., [bm]$（$1 ≤ bi ≤ n$）——数组的重要索引。
请输出 $m$ 个数，第 $i$ 个数等于所有查询完成后索引 $[bi]$ 处的元素值。
## Input
第一行包含三个整数 $n$, $q$ 和 $m$（$1 ≤ n, q ≤ 2·10^5$, $1 ≤ m ≤ 100$）。第二行包含 $n$ 个整数 $[a1], [a2], ..., [an]$（$1 ≤ ai ≤ 10^9$）。接下来 $q$ 行，每行包含三个整数 $[ti], [li], [ri]$，其中 $[ti]$ 是第 $i$ 个查询的类型，$[li, ri]$ 是该查询作用的区间（$1 ≤ ti ≤ 2$, $1 ≤ li ≤ ri ≤ n$）。最后一行包含 $m$ 个整数 $[b1], [b2], ..., [bm]$（$1 ≤ bi ≤ n$）——数组的重要索引。
## Output
请输出 $m$ 个数，第 $i$ 个数等于所有查询完成后索引 $[bi]$ 处的元素值。
[samples]
**Definitions**
Let $ n, q, m \in \mathbb{Z}^+ $ denote the array size, number of queries, and number of important indices, respectively.
Let $ A = (a_1, a_2, \dots, a_n) \in \mathbb{Z}^n $ be the initial array.
Let $ B = (b_1, b_2, \dots, b_m) \in \mathbb{Z}^m $ be the sequence of important indices.
Let $ Q = \{(t_i, l_i, r_i) \mid i \in \{1, \dots, q\}\} $ be the sequence of queries, where:
- $ t_i = 1 $: reverse the subarray $ A[l_i:r_i] $ (inclusive),
- $ t_i = 2 $: replace each element $ a_j $ for $ j \in [l_i, r_i] $ with $ a_j^2 $ (element-wise squaring).
**Constraints**
1. $ 1 \leq n, q \leq 2 \cdot 10^5 $
2. $ 1 \leq m \leq 100 $
3. $ 1 \leq a_i \leq 10^9 $
4. $ 1 \leq t_i \leq 2 $
5. $ 1 \leq l_i \leq r_i \leq n $
6. $ 1 \leq b_i \leq n $
**Objective**
Simulate the effect of all $ q $ queries on array $ A $, and output the values $ A[b_i] $ for each $ i \in \{1, \dots, m\} $ after all operations.
API Response (JSON)
{
"problem": {
"name": "D. Yet Another Array Queries Problem",
"description": {
"content": "You are given an array _a_ of size _n_, and _q_ queries to it. There are queries of two types: * 1 _l__i_ _r__i_ — perform a cyclic shift of the segment \\[_l__i_, _r__i_\\] to the right. That is, fo",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF863D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "You are given an array _a_ of size _n_, and _q_ queries to it. There are queries of two types:\n\n* 1 _l__i_ _r__i_ — perform a cyclic shift of the segment \\[_l__i_, _r__i_\\] to the right. That is, fo...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "给定一个大小为 $n$ 的数组 $[a]$，以及 $q$ 个对其的查询。查询有两种类型：\n\n数组中有 $m$ 个重要索引 $[b1], [b2], ..., [bm]$。对于每个满足 $1 ≤ i ≤ m$ 的 $i$，你需要输出在所有查询执行完毕后，数组中索引为 $[bi]$ 的元素。\n\n第一行包含三个整数 $n$, $q$ 和 $m$（$1 ≤ n, q ≤ 2·10^5$, $1 ≤ m ≤...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, q, m \\in \\mathbb{Z}^+ $ denote the array size, number of queries, and number of important indices, respectively. \nLet $ A = (a_1, a_2, \\dots, a_n) \\in \\mathbb{Z}^n $ be the...",
"is_translate": false,
"language": "Formal"
}
]
}