题目描述

有 $n$ 位同学按照年龄从小到大排好队。

王老师想要查询，年龄为 $x$ 的同学，在队伍中首次出现的位置和最后一次出现的位置；如果队伍中不存在年龄为 $x$ 的同学，请输出 $-1$ 。

由于人数太多，一个一个数，太慢啦，请你编程求解。

请注意：本题中王老师查询年龄 $x$ 出现的起止位置，并不是查询了 $1$ 次，而是查询了 $q$ 次。

比如：

假设有 $6$ 位同学的年龄为： $1$ $2$ $2$ $2$ $3$ $3$ ，王老师查询了 $4$ 个年龄，分别是 $2$ $1$ $3$ $8$ ，那么：

年龄为 $2$ 的同学首次和最后一次出现的位置分别是： $2$ $4$ ；

年龄为 $1$ 的同学首次和最后一次出现的位置分别是： $1$ $1$ ；

年龄为 $3$ 的同学首次和最后一次出现的位置分别是： $5$ $6$ ；

年龄为 $8$ 的同学首次和最后一次出现的位置分别是： $-1$ $-1$ ；

输入

第一行包含整数 $n$ 和 $q$ ，表示队伍中的总人数和询问个数。

第二行包含 $n$ 个整数（整数的值均在 $1 \sim 10000$ 范围内），表示队伍中每个人的年龄。

接下来 $q$ 行，每行包含一个整数 $x$ ，表示一次询问的值。

输出

共 $q$ 行，每行包含两个整数，表示所求年龄在队伍中的起始位置和终止位置。

如果数组中不存在该元素，则返回 -1 -1。

样例

6 3
1 2 2 2 3 3
2
1
8

2 4
1 1
-1 -1

说明

数据范围

$1≤n≤100000,1≤q≤10000,1≤x≤10000$ 。

来源

二分