一辆自动驾驶的出租车正在 Innopolis 的街道上行驶。该街道上有
安全起见,出租车只能在被照亮的路段上行驶。换言之,出租车能从站点
在经过一些意外故障或修理之后,街道上的路灯可能是亮起的,也可能是熄灭的。
现在给定
:切换第 个路灯的状态。具体地说,若路灯原来亮起,则现在将熄灭;若路灯原来熄灭,则现在将亮起。 :出租车部门的负责人想知道,从 时刻起到当前时刻,有多少个时刻满足:出租车能够从站点 出发到达站点 。
请你帮助出租车部门的负责人回答他们的问题。
输入格式
第一行包含两个整数
第二行包含一个字符串
接下来
:该时刻切换了第 个路灯的状态。 :计算从 时刻起到该时刻,共有多少个时刻满足:出租车能从站点 出发到达站点 。
至少有一个时刻的事件是
输出格式
对于每个
样例 #1
样例输入 #1
5 7 11011 query 1 2 query 1 2 query 1 6 query 3 4 toggle 3 query 3 4 query 1 6
样例输出 #1
1 2 0 0 1 2
限制与约定
对于全部数据,
详细子任务附加限制与分值如下表.
子任务 | 附加限制 | 分值 |
---|---|---|
1 | 20 | |
2 | 对于所有 |
20 |
3 | 对于所有 |
20 |
4 | 所有 |
20 |
5 | 无特殊限制 | 20 |
时间限制:5s
空间限制:512MB