辛苦工作后,伊戈尔决定休息一下。
他决定养一只蜗牛。他买了一个水族箱,中间有一根滑溜溜的树干,并在水族箱里放了一只名叫朱莉娅的蜗牛。
伊戈尔注意到,有时朱莉娅想爬上树干,但由于树干太滑而无法做到。为了帮助蜗牛,伊戈尔在树上放了一些绳子,将第 i 根绳子的下端固定在树干上距地面高度 li 的位置,将较高端固定在距地面高度 ri 的位置。
由于某种原因,没有两根绳子共享较高端的相同位置,即所有 ri 都是不同的。现在,朱莉娅可以在树干的任何位置向下移动,也可以从绳子的下端向上移动到其较高端。伊戈尔对他的工作感到自豪,有时会思考蜗牛可能的运动。也就是说,他对以下问题感兴趣:“假设蜗牛现在位于高度 x 的树干上。如果蜗牛的树干永远不会低于 x 或高于 y,那么它能爬到的最高位置是多少?»请注意,在到达绳子的较高端之前,Julia 无法从绳子移动到树干,而 Igor 对树干上的最高位置感兴趣。
伊戈尔对许多问题感兴趣,但并不总是能回答它们。帮助他,编写一个程序来回答这些问题。
输入
第一行包含单个整数 n (1 ≤ n ≤ 100000) — 树干的高度。
第二行包含单个整数 m (1 ≤ m ≤ 100000) — 绳索的数量。
接下来的 m 行包含有关绳索的信息。
这些行中的第 i 行包含两个整数 li 和 ri (1 ≤ li ≤ ri ≤ n) - 第 i 根绳子的下端和上端分别固定的高度。保证所有 ri 都是不同的。
下一行包含单个整数 q (1 ≤ q ≤ 100000) — 问题数。
接下来的 q 行包含有关问题的信息。
每行都包含两个整数 x 和 y (1 ≤ x ≤ y ≤ n),其中 x 是 Julia 开始的高度(以及 Julia 不能低于的高度),y 是 Julia 不能高于的高度。
输出
对于每个问题,打印 Julia 可达到的最大身高。
示例
输入 #1
8 4 1 2 3 4 2 5 6 7 5 1 2 1 4 1 6 2 7 6 8
输出 #1
2 2 5 5 7
输入 #2
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
输出 #2
2 7 3 3 2 2 5 3 7 10
注意
左边是第一个样本的图片,右边是第二个样本的图片。绳索的颜色只是为了清晰起见,它们没有任何意义。