题目描述

2026 丙午马年，新春游园会上最受欢迎的是“翻蹄铁”游艺。

桌面上有 \(m\) 枚蹄铁，每枚蹄铁有正（+）和反（-）两种状态。我们不断执行如下操作，直到所有蹄铁均为反：

• 假设当前有 \(k\) 枚蹄铁是正，翻转第 \(k\) 枚蹄铁。

现在，你的收纳匣里依次堆了 \(n\) 枚蹄铁，有 \(q\) 次询问（询问之间独立），每次询问将第 \(l\) 枚到第 \(r\) 枚蹄铁放置桌上（此时 \(m = r-l+1\)）执行的操作次数。可以证明，在有限次操作内一定能达到目标状态。

输入格式

本题有多组测试数据。输入 \(T\ (1 \le T \le 10)\)，表示数据组数。

对于每组数据：

第一行，输入 \(n\ (1 \le n \le 10^6)\)， \(q\ (1 \le q \le 10^6)\)。

第二行，输入串 \(s\)， \(s_i \in \{'+', '-'\}\) 表示第 \(i\) 枚马蹄的状态。

接下来 \(q\) 行，每行读入两个数 \(l, r\ (1 \le l \le r \le n)\)，表示对区间 \([l, r]\) 的询问。

保证对于所有数据的 \(n\) 的和不超过 \(5 \cdot 10^6\)， \(q\) 的和不超过 \(5 \cdot 10^6\)。

输出格式

由于 I/O 很大，请务必使用极高效的 I/O。

对于每组数据，你只需要输出一行一个数，表示所有询问的操作次数的异或和。

对于第一组数据，每个询问的结果为：

1
4
3

而 \(1\oplus 4\oplus 3 = 6\)，故输出 \(6\)。

对于第二组数据，每个询问的结果为：

1
1
6
6
0
5
5
3
3
1

样例输入

2
3 3
+-+
1 2
1 3
2 3
5 10
+--+-
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

样例输出

6
1