灾区救援

题目描述

童童有一批救援物资，预备分装在不同的卡车上，准备运输到灾区救援。每辆货车都有一个载重量，货车按照载重量由小到大排好顺序，都停在一条笔直的马路上，有可能货车的载重量相同。

现在童童想知道，载重量为 $x$ 的货车在队伍中第一次出现的位置和最后一次出现的位置，分别是多少？（注意：货车的位置是从 1 开始的。）

现在童童有 $q$ 次询问，每次询问都输出两个数字 $a, b$，载重量为 $x$ 的卡车第一次和最后一次出现的位置。如果没有这个载重量的卡车输出 $-1$。

输入格式

输入 $n$ 和 $q$，分别是卡车的数量和童童询问的次数。

接下来一行，$n$ 个数字，按照由小到大的顺序，为卡车的载重量。

接下来 $q$ 行，每行一个数字为查询的 $x$。

输出格式

输出为 $q$ 行。每行两个数字，为第一次出现的位置和最后一次出现的位置。如果没有这个重量输出 $-1$。

样例输入 #1

10 3
200 300 300 300 300 300 400 688 788 999
300
688
350

样例输出 #1

2 6
8 8
-1 -1

数据范围

$1 < n \le 100000$，$1 < q \le 10000$，$500 < x \le 200000$。

知识点与难度

本题涉及的知识点从属于 GESP五级（二分查找、二分基础），难度等级：⭐⭐⭐。

测试点分布