U3428.二进鸡

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 开始。

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

###_样例_解释

对于第一个询问，区间[2,2] 只有数字0，是3 的倍数，区间[1,3] 可以重排成011(2)=3 (10) ，是3 的倍数，其他区间均不能重排成3 的倍数。

对于第二个询问，全部三个区间均能重排成3 的倍数（注意00 也是合法的）。

###_数据_范围

对于20% 的数据，1≤n,m≤100。

对于50% 的数据，1≤n,m≤5000。

对于100% 的数据，1≤n,m≤100000，l≤r。