题目描述

此时己是凌晨两点，刚刚做了 Codeforces 的小 A 掏出了英语试卷。英语作业其实不算多，一个小时刚好可以做完。然后是一个小时可以做完的数学作业，接下来是分别都是一个小时可以做完的化学，物理，语文..... 小 A 压力巨大。

这时小 A 碰见了一道非常恶心的数学题，给定了一个长度为 $n$ 的数列和若干个询问，每个询问是关于数列的区间表示数列的第 $l$ 个数到第 $r$ 个数，首先你要统计该区间内大于等于 $a$，小于等于 $b$ 的数的个数，其次是所有大于等于 $a$，小于等于 $b$ 的，且在该区间中出现过的数值的个数。

小 A 望着那数万的数据规模几乎绝望，只能向大神您求救，请您帮帮他吧。

输入格式

第一行两个整数 $n,m$。

接下来 $n$ 个不超过 $10^5$ 的正整数表示数列。

接下来 $m$ 行，每行四个整数 $l,r,a,b$，具体含义参见题意。

输出格式

输出 $m$ 行，分别对应每个询问，输出两个数，分别为在 $l$ 到 $r$ 这段区间中大小在 $[a,b]$ 中的数的个数，以及大于等于 $a$，小于等于 $b$ 的，且在该区间中出现过的数值的个数（具体可以参考样例）。

3 4
1 2 2
1 2 1 3
1 2 1 1
1 3 1 3
2 3 2 3

2 2
1 1
3 2
2 1

数据范围

对于 $100\%$ 的数据，$n \leq 10^5$，$m \leq 10^6$（此为加强版，原题数据 $m\leq 10^6$），读入的数字均为 $[1,10^5]$ 内的正整数。