题目描述

小 Y 得到了 \(n\) 道数学题作为家庭作业，每道题有一个难度系数 \(a_i\) ，他将难度相同的题目视为 同一种 。他想分 \(m\) 天写完这些作业。每天他选中第 \(l\) 到 \(r\) 道题作为今天要写的题目（一道题可能做多次）。但是作为一个菜鸡，他想先挑一些简单题做完。于是，他提出下面四个问题：

• 选中的题目中难度不超过 \(k\) 的题目的数量
• 选中的题目中难度不超过 \(k\) 的有多少 种 题目
• 选中的题目中难度第 \(k\) 小的题目的难度
• 选中的题目中按难度从小到大第 \(k\) 种 题目的难度

然而小 Y 还是个菜鸡 OIer ，完全不会上面的问题，于是他找到了你。

输入格式

第一行一个整数 \(T\) 表示测试点编号。

接下来：

\(n\ m\)

\(a_1 \ a_2\ a_3\ …… a_n\)

\(l_1\ r_1\ k_1\)

\(l_2\ r_2\ k_2\)

\(……\)

\(l_m\ r_m\ k_m\)

输出格式

\(m\) 行，每行四个整数表示本次询问的四个问题的答案。对于后两种询问，若不存在对应的答案请输出 -1 。

样例

样例输入 1

0
5 6
2 3 1 1 2
1 3 2
1 4 2
1 5 3
2 4 1
3 5 2
2 2 2

样例输出 1

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

提示说明

样例中的 \(T\) 为 0，实际测试点中并没有样例。

为防暴力卡过，时空限制较紧，可能需要一定IO/常数优化。

数据点编号	\(n\le\)	\(m\le\)	\(a_i,k_i\le\)	特殊性质
\(1-2\)	\(500\)	\(500\)	\(500\)	无
\(3-4\)	\(3\times 10^4\)	\(3\times 10^4\)	\(10^5\)	保证所有 \(k_i=1\)
\(5-6\)	\(10^5\)	\(10^5\)	\(10^5\)	保证所有 \(l_i=1,r_i=n\)
\(7-10\)	\(10^5\)	\(10^5\)	\(10^5\)	无

对于所有数据，保证：

\(1\le n,m\le 10^5\)

\(1\le a_i,k_i\le 10^5\)

\(1\le l_i\le r_i\le n\)