Description
PIPI现在手里有一个长度为n的序列 a1 a2 ... an。
这个序列支持两种操作:
1. 对区间 L ~ R 增加一个数P
2. 对区间 L ~ R 减去一个数P
现在经过m次这样的操作之后，PIPI再对这个序列进行q次询问~
每次询问区间 a[L]~a[R]的和，你能告诉PIPI每次的询问结果吗?
Input
输入第一行包含三个数字 n,m,q (1<=n,m,q<=1e5)。
第二行 n 个数字，代表 a 数组。
第3到第 m+2行每行包括 4 个数字 op L R P, op为 1时执行操作 1，否则执行操作2(P<=1e5).
最后 q 行每行 2 个数字 L，R，代表询问的区间。
Output
一个整数，代表 a[L]~a[R]的元素之和。
Sample Input
10 5 1
1 2 3 4 5 6 7 8 9 10
2 1 5 5
2 2 3 6
1 2 5 5
1 2 5 8
2 4 9 6
2 7