409013 - 序列操作

有一个长度为 n 的序列,每个字符都是 '0' 或 '1'。有五种操作: 1.修改操作: 0 a b:将区间 [a, b] 内所有字符改为 '0'; 1 a b:将区间 [a, b] 内所有字符改为 '1'; 2 a b:将区间 [a, b] 内所有 '0' 变 '1'、所有 '1' 变 '0'(翻转)。 2.查询操作: 3 a b:输出区间 [a, b] 内 '1' 的个数; 4 a b:输出区间 [a, b] 内最长连续 '1' 串的长度。

Input

第一行一个整数 T(T ≤ 10),表示测试用例组数。 每组测试第一行两个整数 n, m(1 ≤ n, m ≤ 100000)。 下一行 n 个字符('0' 或 '1'),空格隔开。 接下来 m 行,每行一个操作:op a b(0 ≤ op ≤ 4,0 ≤ a ≤ b < n)。

Output

对每个查询操作(op = 3 或 op = 4),输出对应结果。

Examples

Input

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

Output

5
2
6
5
Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题