题目描述

学生成绩已经按非递减顺序保存为 $a_1,a_2,\ldots,a_n$，相同成绩可以出现多次，下标从 $1$ 开始。

每次给定一个分数 $x$，请输出它第一次出现的位置、最后一次出现的位置，以及一共出现了多少次。

如果没有学生得到这个分数，输出 -1 -1 0。所有查询都不会改变成绩。

输入格式

第一行包含两个整数 $n,q$，表示成绩数量和查询次数。

第二行包含 $n$ 个非递减排列的整数，表示成绩。

接下来 $q$ 行，每行一个整数 $x$。

输出格式

输出 $q$ 行，每行三个整数，依次表示首次位置、末次位置和出现次数；不存在时输出 -1 -1 0。

5 4
60 70 70 70 90
70
80
60
90

2 4 3
-1 -1 0
1 1 1
5 5 1

3 3
0 0 0
0
1
1000000000

1 3 3
-1 -1 0
-1 -1 0

样例 1 解释

分数 70 连续出现在下标 2、3、4，共 3 次；80 不存在；60 和 90 各出现 1 次。

样例 2 解释

0 从下标 1 一直出现到下标 3；其余两个查询分数均不存在。

数据范围与提示

对于所有数据，$1\le n,q\le 200000$，$0\le a_i,x\le 10^9$。保证成绩非递减。

共 $20$ 个测试点，每个测试点 $5$ 分，按测试点独立计分，总分 $100$ 分。

测试点	规模限制
1—5	$n,q\le 20$
6—10	$n,q\le 2000$
11—15	$n,q\le 50000$
16—20	$n,q\le 200000$

表中的规模限制只限制对应参数的上界，所有测试点同时满足上述完整数据范围。

时间限制：2 秒。内存限制：128 MiB。