问题描述

有一条长桌上有 $n$ 个空盘子，编号为 $1 \sim n$，现在要在上面进行 $k$ 次操作，每次操作选择一个区间 $[l, r]$，给区间内每个盘子放一个蛋糕。接下来 $q$ 组查询，每次查询所有盘子中，哪个盘子蛋糕数量大于等于 $x$，如果有多个，输出盘子编号最小的那个。

输入格式

第一行两个整数 $n, k$，代表盘子数量与操作次数。

接下来 $k$ 行每行一个 $[l, r]$，代表操作。

第 $k+2$ 行输入一个 $q$，代表查询次数。

接下来 $q$ 行每行一个 $x$，需要查询的大于等于 $x$ 的蛋糕数量且盘子编号最小的那个，如果不存在，输出 $-1$。

输出格式

对于 $q$ 组查询，每组输出大于等于 $x$ 的蛋糕数量且盘子编号最小的那个，如果不存在，输出 $-1$。

样例输入

5 2
1 3
3 5
3
1
2
3

样例输出

1
3
-1

说明

蛋糕分布为：$a = [1, 1, 2, 1, 1]$。 因此输出 $1, 3, -1$。

数据范围

$1 \leq n \leq 10^5$ $1 \leq k \leq 10^5$ $1 \leq l \leq r \leq n$ $1 \leq q \leq 10^5$ $1 \leq x \leq k$