# #783. 新年的双区间操作

### 样例一

#### input

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



#### output

8
7
7
7
10
7



### 子任务

$1$ $100$ $100$ $500$ $5$
$2$ $10^5$ $1\,000$ $10$
$3$ $4 \times 10^4$ $5 \times 10^4$ $l_i = r_i = l_i' = r_i'$ $10$
$4$ $2 \times 10^5$ $l_i = r_i$ 且 $l_i' = r_i'$ $15$
$5$ $10^5$ $20$
$6$ $10^5$ $20$
$7$ $2 \times 10^5$ $6 \times 10^5$ $20$