题目描述

给定一个长度为 $n$ 的序列 $a_1,a_2,...a_n$ 及 $q$ 次询问，每次询问包含 $4$ 个参数 $l1_i,r1_i,l2_i,r2_i$ ，你可以从区间 $[l1_i,r1_i]$ 中任意取出一个整数 $x$ 、 区间 $[l2_i,r2_i]$ 中任意取出一个整数 $y$ ，$x$与$y$可以是序列中的同一个数字。

请问对于每一次询问给定的参数，有多少种取法可以使得 $x=y$？

输入格式

输入第一行，两个正整数 $n,q$ 输入第二行，$n$ 个正整数 $a_1,...,a_n$ 接下来 $q$ 行，每行四个正整数，其中第 $i+2$ 行的数表示第 $i$ 个询问的参数 $l1_i,r1_i,l2_i,r2_i$

输出格式

输出共 $q$ 行，第 $i$ 行对应第 $i$ 个问题的答案

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

2
6

数据范围

• 对于 $30\%$ 的数据，$1\leq n,q \leq 100$
• 对于 $60\%$ 的数据，$1\leq n,q \leq 10^3$
• 对于 $100\%$ 的数据，$1\leq n,q\leq 5\times 10^4$，$1 \leq a_i \leq n$，$1 \leq l1_i \leq r1_i \leq n$，$1 \leq l2_i \leq r2_i \leq n$