[R70B]寻觅 - 代码源竞赛平台

时空限制

1S/512M

题目描述

给定一个长度为 $n$ 的正整数序列 $A=[a_1,a_2,\dots,a_n]$，序列的下标从 $1$ 开始。

现有 $m$ 次相互独立的询问。每次询问给定一个正整数 $x$，你需要求出：

• $x$ 在序列 $A$ 中出现的次数；
• $x$ 在序列 $A$ 中第一次出现的位置；
• $x$ 在序列 $A$ 中最后一次出现的位置。

若 $x$ 没有在序列 $A$ 中出现，则其出现次数为 $0$，第一次出现的位置和最后一次出现的位置均记为 $-1$。

格式

输入格式

第一行包含两个正整数 $n,m$，分别表示序列的长度和询问次数。

第二行包含 $n$ 个正整数 $a_1,a_2,\dots,a_n$，表示序列 $A$。

接下来 $m$ 行，每行包含一个正整数 $x$，表示一次询问中需要查找的数。

输出格式

输出 $m$ 行。对于每次询问，输出一行三个由空格分隔的整数，依次表示 $x$ 在序列 $A$ 中出现的次数、第一次出现的位置和最后一次出现的位置。

若 $x$ 没有在序列 $A$ 中出现，输出 0 -1 -1。

样例

样例输入 #1

7 4
3 1 3 2 3 1 5
3
1
4
5

样例输出 #1

3 1 5
2 2 6
0 -1 -1
1 7 7

样例解释 #1

• $3$ 在序列中出现了 $3$ 次，第一次出现的位置为 $1$，最后一次出现的位置为 $5$；
• $1$ 在序列中出现了 $2$ 次，第一次出现的位置为 $2$，最后一次出现的位置为 $6$；
• $4$ 没有在序列中出现，因此输出 0 -1 -1；
• $5$ 只在位置 $7$ 出现了一次，因此第一次出现的位置和最后一次出现的位置均为 $7$。

数据规模

注意：你只有通过了该题目的所有测试点，才能获得分数。

对于 $100\%$ 的数据，满足 $1\le n,m\le 1000$，$1\le a_i,x\le 10^9$。