#P17846. [ONTAK 2021]STO

[ONTAK 2021]STO

栈上的区间操作

给定操作序列 c1,…,cNc_1,\ldots,c_N。若 ci=−1c_i=-1,表示弹出栈顶;否则表示将整数 cic_i 压入栈。

栈最初为空。依次给出 MM 个区间 [aj,bj][a_j,b_j],每次将该区间内的操作按原顺序执行一次,栈在不同区间之间保留。保证整个执行过程中不会对空栈执行弹出操作。

执行结束后,询问从栈底开始数的第 p1,…,pKp_1,\ldots,p_K 个元素。保证这些位置都存在。

输入格式

第一行 N,M,KN,M,K。接下来 NN 行,每行一个 cic_i。接下来 MM 行,每行 aj,bja_j,b_j。最后 KK 行,每行一个 pip_i,这些位置严格递增。

输出格式

输出 KK 行,每行是相应位置的元素值。

数据范围

1≤N,M,K≤2000001\le N,M,K\le200000,−1≤ci≤106-1\le c_i\le10^6,1≤aj≤bj≤N1\le a_j\le b_j\le N,1≤pi≤2⋅10101\le p_i\le2\cdot10^{10}。注意最终栈长度可能超过 32 位整数范围。

样例

4 3 2
-1
5
6
-1
2 4
1 3
1 4
1
2
5
5