题目背景

题目描述

给出长度为 $n$ 的排列 $\{a\}$。

$m$ 次询问，每次给出 $p,x,q,y$，求：

$$\sum_{i\equiv x\pmod p}\sum_{j\equiv y\pmod q}[a_i<a_j] $$

$[P]$ 为艾弗森括号，当 $P$ 为真时值为 $1$，否则为 $0$。

输入格式

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

第二行 $n$ 个互异正整数 $a_i$。

之后 $m$ 行，每行四个非负整数 $p,x,q,y$，表示一次询问。

输出格式

对于每次询问输出一行表示对应的答案。

10 10
5 7 6 9 3 8 10 4 1 2
6 3 2 0
9 4 3 0
1 0 1 0
10 7 4 0
3 1 6 0
5 2 4 3
3 2 1 0
3 2 5 2
4 2 6 4
9 8 8 2

8
0
45
0
2
1
16
5
3
1

提示

对于所有数据，$1\leq n\leq 5\times10^4$，$1\leq m\leq10^5$，$1\leq a_i,p,q\le n$，$0\le x<p\land0\le y<q$，保证 $\{a\}$ 为排列。

本题采用捆绑测试，你需要通过一个子任务的所有测试点才能得到该子任务的分数。

子任务编号	$n\le$	$m\le$	特殊性质	分值	子任务依赖
$1$	$5\times10^3$		无	$10$	无
$2$	$5\times10^4$	$10^5$	A	$20$
$3$			B
$4$			无	$50$	$1,2,3$

特殊性质 A：保证 $q=1$。
特殊性质 B：保证 $p,q\le20$。