在蓝锁的残酷世界里, 布拉多 3 是一个被选中推翻卫冕冠军并带领日本 U-20 队走向辉煌的三人组。 纱江伊东 已经锁定了第一名参赛者的位置;剩下的两个名额将在艰难的B面选拔中争夺。
为了测试候选人的战略能力,Buratsuta提出了以下挑战:
给您一个名为“性能记录”的 $$$n$$$ 整数数组和 $$$q$$$ 查询。每个查询指定一个子数组$$$[l, r]$$$。在此子数组中,查找出现的所有记录值 严格更多 比 $$$\lfloor\tfrac{r - l + 1}{3}\rfloor$$$ 倍。
输入
每个测试由多个测试用例组成。
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
下面介绍测试用例。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ $$$(1 \le n, q \le 2\cdot10^5)$$$ — 记录数和查询数。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le 10^9)$$$ — 性能记录。
以下 $$$q$$$ 行中的每一行都包含两个整数 $$$l$$$ 和 $$$r$$$ $$$(1 \le l \le r \le n)$$$ — 查询的边界。
保证所有测试用例的 $$$n$$$ 和 $$$q$$$ 之和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个查询,在一行中输出出现的所有记录值(按排序顺序) 严格更多 比 $$$[l, r]$$$ 段中的 $$$\lfloor\tfrac{r - l + 1}{3}\rfloor$$$ 倍。如果没有这样的值,则输出$$$-1$$$。
示例
输入复制
51 151 14 21 1 2 31 42 36 37 7 7 8 8 91 62 54 68 24 4 4 5 5 5 6 61 83 610 51 2 3 3 3 4 4 4 4 51 101 54 96 97 10
输出复制
511 277 884 5543444
注意
在第二个测试用例中,数组为 $$$a=[1,1,2,3]$$$ 并且有两个查询:
- 查询$$$(l,r)=(1,4)$$$:线段长度$$$len=r-l+1=4$$$,阈值$$$\bigl\lfloor \frac{len}{3}\bigr\rfloor+1 = 2$$$。数字出现次数:$$$1\!\to\!2$$$、$$$2\!\to\!1$$$、$$$3\!\to\!1$$$。只有数字 $$$1$$$ 至少出现 $$$2$$$ 次,所以答案是:$$$1$$$。
- 查询$$$(l,r)=(2,3)$$$:段长度$$$len=2$$$,阈值$$$\bigl\lfloor \frac{len}{3}\bigr\rfloor+1 = 1$$$。数字 $$$1$$$ 和 $$$2$$$ 各出现一次,所以答案是:$$$1 \; 2$$$。
在第四个测试用例中,数组为 $$$a=[4,4,4,5,5,5,6,6]$$$ 并且有两个查询:
- 查询$$$(l,r)=(1,8)$$$:段长度$$$len = 8$$$,阈值$$$\bigl\lfloor \dfrac{len}{3} \bigr\rfloor + 1 = 3$$$。
数字出现次数:$$$4 \!\to\! 3$$$, $$$5 \!\到\! 3$$$, $$$6 \!\到\! 2$$$。只有数字 $$$4$$$ 和 $$$5$$$ 至少出现 $$$3$$$ 次,所以答案是:$$$4 \; 5$$$。
- 查询$$$(l,r)=(3,6)$$$:段长度$$$len = 4$$$,阈值$$$\bigl\lfloor \dfrac{len}{3} \bigr\rfloor + 1 = 2$$$。
数字出现次数:$$$4 \!\to\! 1$$$, $$$5 \!\到\! 3$$$。只有数字 $$$5$$$ 至少出现 $$$2$$$ 次,所以答案是:$$$5$$$。