Description

描述：

你有一列数 A1, A2 … An 。现在有两种操作：

1、C i j x  : 把数列中的 Ai A(i+1) … Aj 都变成 x

2、Q i j  : 查询 Ai xor A(i+ 1) xor … xor Aj

Input

一个数 T (T <= 10) 表示有 T 组数据。 每组数据第一行是两个数 n 和 m (1 <= n, m <= 100000) 。 第二行是 n 个数，表示 A1, A2 … An 。 最后 m 行表示 m 个查询，格式如上所述，其中 1 <= i <= j <= n ，0 <= x <= 2^32 - 1

Output

对于每个查询，输出一个答案，一个答案占一行。每组数据之后留一个空行。

Sample

Input

1
4 5
1 2 3 4
C 1 1 5
Q 1 2
C 1 3 0
C 2 4 1
Q 1 4

Output

7
1

Source: YCC