[BJOI2018]二进制

题目描述

pupil 发现对于一个十进制数,无论怎么将其的数字重新排列,均不影响其是不是$3$ 的倍数。他想研究对于二进制,是否也有类似的性质。 于是他生成了一个长为$n$ 的二进制串,希望你对于这个二进制串的一个子区间,能求出其有多少位置不同的连续子串,满足在重新排列后(可包含前导$0$)是一个$3$ 的倍数。 两个位置不同的子区间指开始位置不同或结束位置不同。 由于他想尝试尽量多的情况,他有时会修改串中的一个位置,并且会进行多次询问。

输入输出格式

输入格式


输入第一行包含一个正整数$n$,表示二进制数的长度。 之后一行$n$ 个空格隔开的整数,保证均是$0$ 或$1$,表示该二进制串。 之后一行一个整数$m$ ,表示询问和修改的总次数。 之后m 行每行为```1 i```,表示pupil 修改了串的第$i$ 个位置($0$ 变成$1$ 或$1$ 变成$0$ ),或```2 l r```,表示pupil 询问的子区间是$[l,r]$。 串的下标从$1$ 开始。

输出格式


对于每次询问,输出一行一个整数表示对应该询问的结果。

输入输出样例

输入样例 #1

4
1 0 1 0
3
2 1 3
1 3
2 3 4

输出样例 #1

2
3

说明

###样例解释 对于第一个询问,区间$[2,2]$ 只有数字$0$,是$3$ 的倍数,区间$[1,3]$ 可以重排成$011_{(2)} = 3_{(10)}$,是$3$ 的倍数,其他区间均不能重排成$3$ 的倍数。 对于第二个询问,全部三个区间均能重排成$3$ 的倍数(注意$00$ 也是合法的)。 ###数据范围 对于$20\%$ 的数据,$1 \leq n,m \leq 100$。 对于$50\%$ 的数据,$1 \leq n,m \leq 5000$。 对于$100\%$ 的数据,$1 \leq n,m \leq 100000$,$l \leq r$。