CF793F Julia the snail

经过努力之后，Igor 决定休息一下。 他决定养一只蜗牛。他买了一个带有光滑树干的水族箱，并把一只名叫 Julia 的蜗牛放了进去。 Igor 发现有时 Julia 想爬到树干上，但是因为树干太光滑而做不到。为了帮助蜗牛，Igor 在树上放了一些绳子，第 $i$ 根绳子的下端固定在树干离地面 $l_{i}$ 的高度，上端固定在离地面 $r_{i}$ 的高度。 由于某些原因，没有两根绳子的上端位置相同，即所有 $r_{i}$ 都互不相同。现在 Julia 可以在树干上的任意位置往下爬，也可以通过某根绳子从其下端爬到其上端。Igor 对自己的工作很自豪，有时候会思考蜗牛可能的移动方式。具体来说，他感兴趣的问题是：“假设蜗牛现在位于树干的高度 $x$。如果它从不低于 $x$ 也不高于 $y$，那么它能到达的树干上的最高位置是多少？”请注意，Julia 在到达绳子的上端之前，无法从绳子回到树干上，Igor 只关心树干上的最高位置。 Igor 有很多类似问题，但并不总能回答。请帮助他，编写程序解答这些问题。

第一行包含一个整数 $n$（$1\leq n\leq 100000$），表示树干的高度。 第二行包含一个整数 $m$（$1\leq m\leq 100000$），表示绳子的数目。 接下来 $m$ 行描述绳子的信息。 第 $i$ 行包含两个整数 $l_{i}$ 和 $r_{i}$（$1\leq l_{i}\leq r_{i}\leq n$），分别表示第 $i$ 根绳子的下端和上端所在的高度。保证所有的 $r_{i}$ 互不相同。 下一行包含一个整数 $q$（$1\leq q\leq 100000$），表示询问的数量。 接下来 $q$ 行描述每个询问。 每行包含两个整数 $x$ 和 $y$（$1\leq x\leq y\leq n$），表示 Julia 的起始高度 $x$（Julia 不能低于该高度）以及不能高于的高度 $y$。

对于每个询问，输出 Julia 能到达的树干上的最大高度。

第一组样例的图片在左侧，第二组样例的图片在右侧。绳子的颜色仅为显示清晰起见，没有实际意义。  由 ChatGPT 5 翻译