问题描述

有一条长桌上有 $n$ 个空盘子，编号为 $1 \sim n$，现在要在上面进行 $k$ 次操作，每次操作选择一个区间 $[l, r]$，给区间内每个盘子放一个蛋糕。

接下来 $q$ 组查询：

在所有满足 $a_i \ge x$ 的盘子中，按照以下规则排序：

• 先按蛋糕数从小到大排序

• 若蛋糕数相同，则按编号从小到大排序

输出排序后的第一个盘子的编号。

如果不存在满足条件的盘子，输出 $-1$。

输入格式

第一行两个整数 $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$