题目描述

一个长度为 \(n\) 的序列 \(a\)，初始全 \(0\)。

有一个长度为 \(m\) 的操作序列（\(r_i, v_i\)），每个操作表示将 \(a[1, r_i]\) 和 \(v_i\) 取 \(\max\)。

给定 \(q\) 次询问，求依次执行 \([L_i, R_i]\) 里面的操作之后 \(a\) 的和。

特别地，设 \(p_i\) 表示左边第一个 \(v_j > v_i\) 的位置，那么有 \(\max_{j = p_i + 1}^{i} r_j = r_i\) 。

保证测试数据组数 \(T = 5\)。

对于每组测试数据， \(1 \le n, m, q \le 10^5, 1 \le v_i \le 10^9, 1 \le L_i \le R_i \le m, 1 \le r_i \le n\)。

输入格式

第一行一个正整数 \(T\)，表示测试数据组数。保证 \(T = 5\)。

对于每组测试数据：

第一行三个正整数 \(n, m, q\)。

接下来 \(m\) 行 \(r_i, v_i\)。

接下来 \(q\) 行 \(L_i, R_i\)。

输出格式

对于每组测试数据，输出一行，一个数表示所有询问答案的异或和。

样例输入

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

样例输出

21
1
37
30
47