1822. [AHOI 2013] 作业

【题目描述】

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

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

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

【输入格式】

第一行两个数$n,m$，接下来$n$个数(这些数都大于等于$1$小于等于$n$)，表示给定数列。

接下来$m$行，每行四个数$l,r,a,b$，期中$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

【提示】

$n\leq 10^5,m\leq 10^6$，读入得数字均为$[1,10^5]$内的正整数。