F. Julia the snail

time limit per test

2 seconds

memory limit per test

512 megabytes

input

standard input

output

standard output

After hard work Igor decided to have some rest.

He decided to have a snail. He bought an aquarium with a slippery tree trunk in the center, and put a snail named Julia into the aquarium.

Igor noticed that sometimes Julia wants to climb onto the trunk, but can't do it because the trunk is too slippery. To help the snail Igor put some ropes on the tree, fixing the lower end of the i-th rope on the trunk on the height li above the ground, and the higher end on the height ri above the ground.

For some reason no two ropes share the same position of the higher end, i.e. all ri are distinct. Now Julia can move down at any place of the trunk, and also move up from the lower end of some rope to its higher end. Igor is proud of his work, and sometimes think about possible movements of the snail. Namely, he is interested in the following questions: «Suppose the snail is on the trunk at height x now. What is the highest position on the trunk the snail can get on if it would never be lower than x or higher than y?» Please note that Julia can't move from a rope to the trunk before it reaches the higher end of the rope, and Igor is interested in the highest position on the tree trunk.

Igor is interested in many questions, and not always can answer them. Help him, write a program that answers these questions.

Input

The first line contains single integer n (1  ≤  n ≤  100000) — the height of the trunk.

The second line contains single integer m (1  ≤  m  ≤  100000) — the number of ropes.

The next m lines contain information about the ropes.

The i-th of these lines contains two integers li and ri (1  ≤ li ≤ ri ≤ n) — the heights on which the lower and the higher ends of the i-th rope are fixed, respectively. It is guaranteed that all ri are distinct.

The next line contains single integer q (1  ≤  q  ≤  100000) — the number of questions.

The next q lines contain information about the questions.

Each of these lines contain two integers x and y (1  ≤ x ≤ y ≤ n), where x is the height where Julia starts (and the height Julia can't get lower than), and y is the height Julia can't get higher than.

Output

For each question print the maximum reachable for Julia height.

Examples

input

8 4 1 2 3 4 2 5 6 7 5 1 2 1 4 1 6 2 7 6 8

output

2 2 5 5 7

input

10 10 3 7 1 4 1 6 5 5 1 1 3 9 7 8 1 2 3 3 7 10 10 2 4 1 7 3 4 3 5 2 8 2 5 5 5 3 5 7 7 3 10

output

2 7 3 3 2 2 5 3 7 10 题目大意：一些询问，问一段区间里 被严格覆盖的子区间 的mex（什么玩意。。）

分块好题！

首先我们发现，因为以每个高度为终点的绳子只有一个，我们可以对每个点高度记录一个prv，表示以这个高度为终点的绳子起点在哪，这样我们就可以O（区间长度）的处理询问，具体做法是从区间开始到结束扫一遍，维护当前能从左端点走到的最右面的点，每当找到一个绳子，起点>=左边界，并且<=当前能走到的最右边的点，那么就把能走到的最右边的点更新为这个点。

为什么这样是对的呢？因为这样按照终点从左到右扫描，如果一根绳子当前不能用，那么以后也永远用不到——以后能用的绳子都比它更优秀

然后我们就可以有一个O(qn)的做法，但这样不够优秀，我们考虑优化。

容易看出按照刚才那种做法，把一个区间往后延长一段是可做的，那我们不妨考虑这样一种做法。我们把整个树干分成 $ \sqrt{n} $ 块，预处理出每个起点到每个块终点的答案（能走到的最右边的点），然后我们就可以 $ \sqrt{n} $ 的回答询问了

现在问题在于，怎么求这个东西。

吐槽一下毛子写的英文题解，**不通，晦涩难懂

假设一个块的大小是sz_b

假设这个东西叫做ans[i][j]，表示[j,i*sz_b-1]的答案（我是从0开始标号的）

我们需要一个东西来求它，假设叫做f[i][j]，表示所有以j为起点，终点<i*sz_b，的绳子中，终点最大的，可能有点绕，理解一下，原文更坑爹

这个f我们可以直接two pointers求出来，因为对于每一个j，f[i][j] (j固定，i是变量) 都是单调的，对每个位置维护一个指针就好了

然后我们有了f，要求ans了，我们从右往左做，显然ans[i][j] = max(ans[i][k]) j<=k<=f[i][j]，这个式子还是比较好理解的吧

然后看上去就可以用线段树维护了，但这样还是会T，我们还需要进一步优化

考虑一个正在计算ans[i][j]的位置j，我们不妨假设从右往左扫描max，如果ans[i][j]被ans[i][p]和ans[i][q]（p<q）都更新了一次，那说明了什么？

说明ans[i][q]<ans[i][p]

那么p的位置又比q靠前，能延伸到的位置还比q靠后，显然q这个位置没用啊

然后如果用更新了j，ans[i][j]>=ans[i][p]，i又比p靠前，p也没用了

所以我们对每一趟求ans[*][j]维护一个单调栈，栈中元素是一个二元组（i,j），表示i这个位置的ans是j

扫描到一个元素p时，把所有栈中p能够到(p+f[*][p]>=q)的元素吐出来并更新ans[*][p]，然后把(p,ans[*][p])丢进栈里

这样每一趟求ans也可以线性了

然后就搞定啦！总复杂度 $ O((n+q)\sqrt{n}) $

 

1 #include 
        
           2 #include 
         
            3 #include 
          
             4 #include 
           
              5 #include 
            
               6 #include 
             
               7 #include 
              
                8 #include 
               

to[MAXINT]; 50 int prv[MAXINT], f[MAX_BLOCK][MAXINT], ans[MAX_BLOCK][MAXINT], n, m, q, sz_b = 317, cnt_b, p[MAXINT]; 51 pair

stk[MAXINT]; 52 pair

*tp; 53 void get_input(); 54 void work(); 55 void pre_calc(); 56 int main() { 57 get_input(); 58 pre_calc(); 59 work(); 60 return 0; 61 } 62 void work() { 63 rep0(i, q) { 64 int lm, pl; 65 int l = read() - 1, r = read(); 66 if (r - l > sz_b) { 67 int b_r = r / sz_b; 68 lm = ans[b_r][l]; 69 pl = b_r * sz_b; 70 }else lm = pl = l; 71 for (int j = pl; j < r; ++j) 72 if (prv[j] <= lm && prv[j] >= l) 73 lm = max(lm, j); 74 printf("%d\n", lm + 1); 75 } 76 } 77 void get_input() { 78 memset(prv, INF, sizeof(prv)); 79 n = read(); m = read(); 80 rep0(i, m) { //for convenience, label begin with 0 81 int u = read() - 1, v = read() - 1; 82 prv[v] = u; 83 to[u].pb(v); 84 } 85 q = read(); 86 } 87 void pre_calc() { 88 rep0(i, n) sort(to[i].begin(), to[i].end()); 89 cnt_b = n / sz_b; 90 rep1(i, cnt_b) { 91 rep0(j, i * sz_b) { 92 for (; p[j] < to[j].size() && to[j][p[j]] < i * sz_b; p[j]++); 93 if (p[j]) f[i][j] = to[j][p[j] - 1]; else f[i][j] = j; 94 } 95 } 96 rep1(i, cnt_b) { 97 tp = stk; 98 for (int j = i * sz_b - 1; j >= 0; j--) { 99 ans[i][j] = f[i][j];100 if (tp == stk) ans[i][j] = j;101 else while (tp != stk && f[i][j] >= (tp - 1)->first) 102 ans[i][j] = max(ans[i][j], (tp-1)->second),tp--;103 *tp++ = mp(j, ans[i][j]);104 }105 }106 }