给定一个长度为 nnn 的 01 串 SSS 和一个长度为 mmm 的 01 串 TTT。
SSS 通过给定的参数 a,b,ca, b, ca,b,c 构造,其中 aaa 满足 gcd(a,n)=1{\rm gcd}(a, n) = 1gcd(a,n)=1:
Si=[(a⋅i+b) mod n≥c]S_i = [(a\cdot i + b)\ {\rm mod}\ n \geq c]Si=[(a⋅i+b) mod n≥c]
现在有 qqq 个操作或询问:
1 p
2 p
第一行五个正整数 n,a,b,c,mn, a, b, c, mn,a,b,c,m。
第二行一个长度为 mmm 的字符串表示 TTT。
第三行一个整数 qqq。
接下来 qqq 行,一行表示一个操作或询问,格式如上文所述。
对于每一个询问,输出一行一个整数表示答案。
9 5 6 4 3 101 11 1 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 2 1 1 3
0 3 0 2 2 0 3 0 3 1
对于全部数据,1≤a,b,p,m<n≤109,1≤m,q≤100000,gcd(a,n)=11 \leq a, b, p, m < n \leq 10^9, 1 \leq m, q \leq 100000, {\rm gcd}(a, n) = 11≤a,b,p,m<n≤109,1≤m,q≤100000,gcd(a,n)=1。