此时已是凌晨两点，刚刚做了 Codeforces 的小A掏出了英语试卷。英语作业其实不算多，一个小时刚好可以做完。然后是一个小时可以做完的数学作业，接下来是分别都是一个小时可以做完的化学，物理，语文......小A压力巨大。
这是小 A 碰见了一道非常恶心的数学题，给定了一个长度为 $n$ 的数列和若干个询问，每个询问是关于数列的区间 $[l,r]$ （表示数列的第 $1$ 个数到第 $r$ 个数），首先你要统计该区间内大于等于 $a$，小于等于 $b$ 的数的个数，其次是所有大于等于 $a$, 小于等于 $b$ 的，且在该区间中出现过的数值的个数。
小A望着那数万的数据规模几乎绝望，只能向大神您求救，请您帮帮他吧。
第一行两个数 $n,m$，接下来 $n$ 个数（这些数都大于等于 $1$ 小于等于$n$），表示给定数列。接下来 $m$ 行，每行四个数 $l,r,a,b$：
$l,r$ 表示询问的区间，$a,b$ 表示询问的数值的范围。
输出 $m$ 行，分别对应每个询问，输出两个数，分别为在 $1$ 到 $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=100000,M=1000000$
Comet OJ