Message Spreading

Problem Description

一个星球上有 $n$ 个国家，编号为 $1\sim n$。 对于每个 $1\le i< n$，第 $i$ 号国家与第 $i+1$ 号国家互为盟友。特别的，第 $1$ 号国家和第 $n$ 号国家也互为盟友。 现在有一条消息需要在星球上进行传播。初始时有一些国家知道该消息，有一些国家不知道。 你作为星球的统领者，每天可以进行如下两种传播操作之一：

• 指定一个国家，告诉该国家消息。该操作会让被指定的一个国家知道该消息。
• 让所有已经知道该消息的国家告知他们的所有盟友。该操作会使当前至少有一个“已知消息盟友”的国家知道该消息。 你想知道至少需要多少天才能让所有国家都知道该消息。 接下来还有 $q$ 次修改操作，每次给定 $op,l,r$，表示进行如下修改：
• 若 $op=1$，则将编号为 $l\sim r$ 的所有国家都设置为初始时知道该消息。
• 若 $op=2$，则将编号为 $l\sim r$ 的所有国家都设置为初始时不知道该消息。 每次操作之后，你都需要求出至少需要多少天才能让所有国家都知道该消息。注意，你并不会真正进行传播操作。

Input

本题有多组数据。第一行一个正整数 $T$（$1\le T\le 5$）表示数据组数。对于每组测试数据： 第一行输入两个整数 $n,q$（$1\le n,q\le 2\cdot 10^5$），表示国家数量和修改次数。 第二行输入一个长度为 $n$ 的只包含字符 0 和 1 的字符串 $s$，若 $s$ 的第 $i$ 个字符是 0，则表示第 $i$ 个国家最初不知道该消息，否则表示第 $i$ 个国家最初知道该消息。 接下来 $q$ 行，每行三个整数 $op,l,r$（$1\le op\le 2$，$1\le l\le r\le n$），表示一次修改操作。 保证 $\sum n,\sum q\le 5\cdot 10^5$。

Output

对于每组测试数据，输出 $q$ 行，每行一个整数，表示每一次修改之后的答案。

Sample Input

1
6 5
011100
1 1 4
2 2 5
1 1 3
1 6 6
2 2 4

Sample Output

1
2
2
1
2

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（10）