题目描述

给定一个长度为 $n$ 的颜色序列 $c$，对于该序列中的任意一个元素 $c_i$，都有 $1\le c_i\le m$。对于一种颜色 $k$ 来说，区间 $[L,R]$ 内的权值定义为这种颜色在该区间中出现的次数的平方，即区间 $[L,R]$ 内中满足 $c_i=k$ 的元素个数的平方。接下来给出 $Q$ 个询问，询问区间 $[L,R]$ 内颜色 $[a,b]$ 的权值总和。

输入格式

• 第 $1$ 行三个整数 $n,m,Q$。分别代表序列长度，颜色总数和询问总数。
• 第 $2$ 行 $n$ 个整数，代表序列 $c_i$。
• 第 $3$ 行到第 $Q+2$ 行，每行 $4$ 个整数 $l,r,a,b$。记上一次计算出的答案为 $Lans$。那么实际的 $l,r,a,b$ 为给出的$l,r,a,b$ $xor$ 上 $Lans$。第一个询问的时候 $Lans=0$。

输出格式

• 总共 $Q$ 行，对于每一个询问，输出权值总和。

4 2 3
1 1 2 2 
1 4 1 2
10 11 9 10
3 0 0 0

8
2
0

数据规模与约定

对于 $100\%$ 的数据，$1\le n,Q\le 5\times 10^4$，$m\le 2\times 10^4$。