回音
题号：NC213854
时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

只有回音在指尖上缠绕冰冷了烛光

拖曳疲惫身躯低吟浅唱在人海中流浪

谁人能够听到些微我的歌声吗

逆着光 来到深海中央

将门扉叩响

只有回音在生命中陪伴寒暄着过往

用窒息的孤独感将身躯花葬

星点的回音汇成声浪强烈的力量

将心房不断叩响


条子给了你一个序列ai,长度为n，一个长度为m的区间序列[xi,yi]。

现在有q次询问,每次询问有3个参数l,r,k。

每次询问开始，你有一个空的可重集S,然后对于每个区间[xi,yi](l <= i <= r)，将axi...yi的所有数插入S中。

现在条子想知道，S中第k小的数是多少。


输入描述:

第一行，三个整数n,m,q，分别表示序列a，区间序列的长度，询问次数。
第二行，n个整数ai。
后面m行，每行两个整数xi,yi。
后面q行，每行三个整数l,r,k表示一次询问。

输出描述:

q行,每行一个整数，第i行表示第i次询问的答案。
示例1

输入

复制 
8 4 3
1 4 6 2 3 4 1 5
1 4
2 4
3 6 
6 8
1 4 10
2 3 3
2 4 8

输出

复制 
4
3
5

备注:

1≤n,m,q≤200000
1≤ai≤n
1≤xi≤yi≤n
1≤l≤r≤m