#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb(x) push_back(x)
#define vll vector < long long >
const int N = (2e5) + 9;
const int BUCKET_SIZE = 8500;
ll powr(ll a, ll b, ll mod)
{
ll x = 1LL%mod;
a %= mod;
while(b)
{
if(b&1)
x = (x*a)%mod;
a = (a*a)%mod;
b >>= 1;
}
return x;
}
ll inv(ll a, ll mod)
{
return powr(a,mod-2LL,mod);
}
class NTT{
ll p,g,n,logn;
public:
NTT(ll P, ll G, ll LOGN)
{
p = P;
ll g1 = G;
logn = LOGN;
n = (1<<LOGN);
assert((p-1LL)%n == 0LL);
// p = k*n + 1;
// We need g = g1^k, so that the order of g wrt p is n.
g = powr(g1,(p-1LL)>>logn,p);
}
int bitrevcopy(int i)// create bitreversed copy of i.
{
int ret = 0;
for(int j = 0;j<logn;j++)
if(i&(1<<j))
ret|=(1<<(logn-1-j));
return ret;
}
void fft(vll& a, bool invert) // Use fast fourier transform to find polynomial values at g^i,0<=i<n
{
ll mod = p;
for(int i = 0;i<n;i++)
{
int br = bitrevcopy(i);
if(i<br)
swap(a[i],a[br]);
}
for(int i = 1;i<=logn;i++)
{
ll mul = powr(g,1<<(logn-i),p);
if(invert)
mul = inv(mul,p);
int add = (1<<i);
for(int k = 0;k<n;k+=add)
{
ll w = 1;
ll lim = (add>>1);
for(int j = 0;j<lim;j++)
{
ll u = (w*a[k+j+lim])%p, v = a[k+j];
a[k+j] = u+v;
if(a[k+j]>=p)
a[k+j] -= p;
a[k+j+lim] = v-u;
if(a[k+j+lim]<0)
a[k+j+lim]+=p;
w = (w*mul)%p;
}
}
}
if(invert){
ll _inv = inv(n,p);
for(int i = 0;i<n;i++){
a[i] = (a[i]*_inv)%p;
}
}
return;
}
};
// Code for NTT ends here
const ll PRIME = 998244353LL;// (2^23)*7*17 + 1
const ll G = 3LL;
void poly_mul(vll& a, vll b)// a = a*b
{
int _sz = a.size()+b.size()-1;
int LOGN = 0;
while((1<<LOGN) < _sz)
LOGN++;
ll N = (1LL<<LOGN);
a.resize(N);
b.resize(N);
NTT fft = NTT(PRIME,G,LOGN);
fft.fft(a,false);
fft.fft(b,false);
for(int i = 0;i<N;i++)
a[i] = (a[i]*b[i])%PRIME;
fft.fft(a,true);
a.resize(_sz);
for(int i = 0;i<_sz;i++)
a[i] %= PRIME;
return;
}
ll a[N], pre_sum_a[N], pre_sum_b[N];
vector < int > ind;
vector < ll > A, B;
void update(int n)
{
int i, max_val = 0;
A.clear();
A.resize(n+1);
for(i = 0; i <= n; i++)
A[i] = 0LL;
for(i = 0; i < ind.size(); i++)
{
max_val = max(max_val, ind[i]);
A[ind[i]-1]++;
}
A.resize(max_val);
poly_mul(A,B);
for(i = 1; i <= n; i++)
{
a[i] += A[i];
pre_sum_a[i] = pre_sum_a[i-1] + a[i];
}
ind.clear();
return;
}
ll calc_sum_a(int l, int r)
{
if(l > r)
return 0LL;
return (pre_sum_a[r]-pre_sum_a[l-1]);
}
ll query(int l, int r)
{
ll ans = calc_sum_a(l,r);
int i;
for(i = 0; i < ind.size(); i++)
{
if(ind[i] < l)
ans += (pre_sum_b[r-ind[i]+1]-pre_sum_b[l-ind[i]]);
else if(ind[i] <= r)
ans += pre_sum_b[r-ind[i]+1];
}
return ans;
}
int main()
{
clock_t clk = clock();
//freopen ("t10.txt","r",stdin);
//freopen ("o10.txt","w",stdout);
int n, q, i, l, r, t;
ll b, ans;
scanf("%d %d", &n, &q);
for(i = 1; i <= n; i++)
scanf("%lld", &a[i]);
B.clear();
B.resize(n+1);
B[0] = 0LL;
for(i = 1; i <= n; i++)
{
scanf("%lld", &b);
B[i] = b;
}
for(i = 1; i <= n; i++)
{
pre_sum_a[i] = pre_sum_a[i-1] + a[i];
pre_sum_b[i] = pre_sum_b[i-1] + B[i];
}
for(i = 1; i <= q; i++)
{
scanf("%d", &t);
if(t == 1)
{
scanf("%d", &l);
ind.pb(l);
}
else
{
scanf("%d %d", &l, &r);
ans = query(l,r);
printf("%lld\n", ans);
}
if(ind.size() == BUCKET_SIZE)
update(n);
}
clk = clock() - clk;
//cerr << fixed << setprecision(6) << "Time: " << ((double)clk)/CLOCKS_PER_SEC << "\n";
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgbGwgbG9uZyBsb25nCiNkZWZpbmUgcGIoeCkgcHVzaF9iYWNrKHgpCiNkZWZpbmUgdmxsIHZlY3RvciA8IGxvbmcgbG9uZyA+CiAKY29uc3QgaW50IE4gPSAoMmU1KSArIDk7CmNvbnN0IGludCBCVUNLRVRfU0laRSA9IDg1MDA7CiAKIApsbCBwb3dyKGxsIGEsIGxsIGIsIGxsIG1vZCkKewogICAgbGwgeCA9IDFMTCVtb2Q7CiAgICBhICU9IG1vZDsKICAgIHdoaWxlKGIpCiAgICB7CiAgICAgICAgaWYoYiYxKQogICAgICAgICAgICB4ID0gKHgqYSklbW9kOwogICAgICAgIGEgPSAoYSphKSVtb2Q7CiAgICAgICAgYiA+Pj0gMTsKICAgIH0KICAgIHJldHVybiB4Owp9CmxsIGludihsbCBhLCBsbCBtb2QpCnsKICAgIHJldHVybiBwb3dyKGEsbW9kLTJMTCxtb2QpOwp9CiAKY2xhc3MgTlRUewogICAgbGwgcCxnLG4sbG9nbjsKcHVibGljOgogICAgTlRUKGxsIFAsIGxsIEcsIGxsIExPR04pICAgIAogICAgewogICAgICAgIHAgPSBQOwogICAgICAgIGxsIGcxID0gRzsKICAgICAgICBsb2duID0gTE9HTjsKICAgICAgICBuID0gKDE8PExPR04pOwogICAgICAgIGFzc2VydCgocC0xTEwpJW4gPT0gMExMKTsKICAgICAgICAvLyBwID0gaypuICsgMTsKICAgICAgICAvLyBXZSBuZWVkIGcgPSBnMV5rLCBzbyB0aGF0IHRoZSBvcmRlciBvZiBnIHdydCBwIGlzIG4uCiAgICAgICAgZyA9IHBvd3IoZzEsKHAtMUxMKT4+bG9nbixwKTsKICAgIH0KIAogICAgaW50IGJpdHJldmNvcHkoaW50IGkpLy8gY3JlYXRlIGJpdHJldmVyc2VkIGNvcHkgb2YgaS4KICAgIHsKICAgICAgICBpbnQgcmV0ID0gMDsKICAgICAgICBmb3IoaW50IGogPSAwO2o8bG9nbjtqKyspCiAgICAgICAgICAgIGlmKGkmKDE8PGopKQogICAgICAgICAgICAgICAgcmV0fD0oMTw8KGxvZ24tMS1qKSk7CiAgICAgICAgcmV0dXJuIHJldDsKICAgIH0KICAgIHZvaWQgZmZ0KHZsbCYgYSwgYm9vbCBpbnZlcnQpIC8vIFVzZSBmYXN0IGZvdXJpZXIgdHJhbnNmb3JtIHRvIGZpbmQgcG9seW5vbWlhbCB2YWx1ZXMgYXQgZ15pLDA8PWk8bgogICAgeyAgIAogICAgICAgIGxsIG1vZCA9IHA7CiAgICAgICAgZm9yKGludCBpID0gMDtpPG47aSsrKQogICAgICAgIHsKICAgICAgICAgICAgaW50IGJyID0gYml0cmV2Y29weShpKTsKICAgICAgICAgICAgaWYoaTxicikKICAgICAgICAgICAgICAgIHN3YXAoYVtpXSxhW2JyXSk7CiAgICAgICAgfQogICAgICAgIGZvcihpbnQgaSA9IDE7aTw9bG9nbjtpKyspCiAgICAgICAgewogICAgICAgICAgICBsbCBtdWwgPSBwb3dyKGcsMTw8KGxvZ24taSkscCk7CiAgICAgICAgICAgIGlmKGludmVydCkKICAgICAgICAgICAgICAgIG11bCA9IGludihtdWwscCk7CiAgICAgICAgICAgIGludCBhZGQgPSAoMTw8aSk7CiAgICAgICAgICAgIGZvcihpbnQgayA9IDA7azxuO2srPWFkZCkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgbGwgdyA9IDE7CiAgICAgICAgICAgICAgICBsbCBsaW0gPSAoYWRkPj4xKTsKICAgICAgICAgICAgICAgIGZvcihpbnQgaiA9IDA7ajxsaW07aisrKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIGxsIHUgPSAodyphW2sraitsaW1dKSVwLCB2ID0gYVtrK2pdOwogICAgICAgICAgICAgICAgICAgIGFbaytqXSA9IHUrdjsKICAgICAgICAgICAgICAgICAgICBpZihhW2sral0+PXApCiAgICAgICAgICAgICAgICAgICAgICAgIGFbaytqXSAtPSBwOwogICAgICAgICAgICAgICAgICAgIGFbaytqK2xpbV0gPSB2LXU7CiAgICAgICAgICAgICAgICAgICAgaWYoYVtrK2orbGltXTwwKQogICAgICAgICAgICAgICAgICAgICAgICBhW2sraitsaW1dKz1wOwogICAgICAgICAgICAgICAgICAgIHcgPSAodyptdWwpJXA7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgaWYoaW52ZXJ0KXsKICAgICAgICAgICAgbGwgX2ludiA9IGludihuLHApOwogICAgICAgICAgICBmb3IoaW50IGkgPSAwO2k8bjtpKyspewogICAgICAgICAgICAgICAgYVtpXSA9IChhW2ldKl9pbnYpJXA7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgcmV0dXJuOwogICAgfQp9OwogCi8vIENvZGUgZm9yIE5UVCBlbmRzIGhlcmUKIApjb25zdCBsbCBQUklNRSA9IDk5ODI0NDM1M0xMOy8vICgyXjIzKSo3KjE3ICsgMQpjb25zdCBsbCBHID0gM0xMOwogCnZvaWQgcG9seV9tdWwodmxsJiBhLCB2bGwgYikvLyBhID0gYSpiCnsKICAgIGludCBfc3ogPSBhLnNpemUoKStiLnNpemUoKS0xOwogICAgaW50IExPR04gPSAwOwogICAgd2hpbGUoKDE8PExPR04pIDwgX3N6KQogICAgICAgIExPR04rKzsKICAgIGxsIE4gPSAoMUxMPDxMT0dOKTsKICAgIGEucmVzaXplKE4pOwogICAgYi5yZXNpemUoTik7CiAgICBOVFQgZmZ0ID0gTlRUKFBSSU1FLEcsTE9HTik7CiAgICBmZnQuZmZ0KGEsZmFsc2UpOwogICAgZmZ0LmZmdChiLGZhbHNlKTsgCiAgICBmb3IoaW50IGkgPSAwO2k8TjtpKyspCiAgICAgICAgYVtpXSA9IChhW2ldKmJbaV0pJVBSSU1FOwogICAgZmZ0LmZmdChhLHRydWUpOwogICAgYS5yZXNpemUoX3N6KTsKICAgIGZvcihpbnQgaSA9IDA7aTxfc3o7aSsrKQogICAgICAgIGFbaV0gJT0gUFJJTUU7CiAgICByZXR1cm47Cn0KIApsbCBhW05dLCBwcmVfc3VtX2FbTl0sIHByZV9zdW1fYltOXTsKdmVjdG9yIDwgaW50ID4gaW5kOwp2ZWN0b3IgPCBsbCA+IEEsIEI7CiAKdm9pZCB1cGRhdGUoaW50IG4pCnsKICAgIGludCBpLCBtYXhfdmFsID0gMDsKICAgIEEuY2xlYXIoKTsKICAgIEEucmVzaXplKG4rMSk7CiAgICBmb3IoaSA9IDA7IGkgPD0gbjsgaSsrKQogICAgICAgIEFbaV0gPSAwTEw7CiAgICBmb3IoaSA9IDA7IGkgPCBpbmQuc2l6ZSgpOyBpKyspCiAgICB7CiAgICAgICAgbWF4X3ZhbCA9IG1heChtYXhfdmFsLCBpbmRbaV0pOwogICAgICAgIEFbaW5kW2ldLTFdKys7CiAgICB9CiAgICBBLnJlc2l6ZShtYXhfdmFsKTsKICAgIHBvbHlfbXVsKEEsQik7CiAgICBmb3IoaSA9IDE7IGkgPD0gbjsgaSsrKQogICAgewogICAgICAgIGFbaV0gKz0gQVtpXTsKICAgICAgICBwcmVfc3VtX2FbaV0gPSBwcmVfc3VtX2FbaS0xXSArIGFbaV07CiAgICB9CiAgICBpbmQuY2xlYXIoKTsKICAgIHJldHVybjsKfQogCmxsIGNhbGNfc3VtX2EoaW50IGwsIGludCByKQp7CiAgICBpZihsID4gcikKICAgICAgICByZXR1cm4gMExMOwogICAgcmV0dXJuIChwcmVfc3VtX2Fbcl0tcHJlX3N1bV9hW2wtMV0pOwp9CiAKbGwgcXVlcnkoaW50IGwsIGludCByKQp7CiAgICBsbCBhbnMgPSBjYWxjX3N1bV9hKGwscik7CiAgICBpbnQgaTsKICAgIGZvcihpID0gMDsgaSA8IGluZC5zaXplKCk7IGkrKykKICAgIHsKICAgICAgICBpZihpbmRbaV0gPCBsKQogICAgICAgICAgICBhbnMgKz0gKHByZV9zdW1fYltyLWluZFtpXSsxXS1wcmVfc3VtX2JbbC1pbmRbaV1dKTsKICAgICAgICBlbHNlIGlmKGluZFtpXSA8PSByKQogICAgICAgICAgICBhbnMgKz0gcHJlX3N1bV9iW3ItaW5kW2ldKzFdOwogICAgfQogICAgcmV0dXJuIGFuczsKfQogCmludCBtYWluKCkKewogICAgY2xvY2tfdCBjbGsgPSBjbG9jaygpOwogICAgLy9mcmVvcGVuICgidDEwLnR4dCIsInIiLHN0ZGluKTsKICAgIC8vZnJlb3BlbiAoIm8xMC50eHQiLCJ3IixzdGRvdXQpOwogCiAgICBpbnQgbiwgcSwgaSwgbCwgciwgdDsKICAgIGxsIGIsIGFuczsKICAgIHNjYW5mKCIlZCAlZCIsICZuLCAmcSk7CiAgICBmb3IoaSA9IDE7IGkgPD0gbjsgaSsrKQogICAgICAgIHNjYW5mKCIlbGxkIiwgJmFbaV0pOwogICAgQi5jbGVhcigpOwogICAgQi5yZXNpemUobisxKTsKICAgIEJbMF0gPSAwTEw7CiAgICBmb3IoaSA9IDE7IGkgPD0gbjsgaSsrKQogICAgewogICAgICAgIHNjYW5mKCIlbGxkIiwgJmIpOwogICAgICAgIEJbaV0gPSBiOwogICAgfQogICAgZm9yKGkgPSAxOyBpIDw9IG47IGkrKykKICAgIHsKICAgICAgICBwcmVfc3VtX2FbaV0gPSBwcmVfc3VtX2FbaS0xXSArIGFbaV07CiAgICAgICAgcHJlX3N1bV9iW2ldID0gcHJlX3N1bV9iW2ktMV0gKyBCW2ldOwogICAgfQogICAgZm9yKGkgPSAxOyBpIDw9IHE7IGkrKykKICAgIHsKICAgICAgICBzY2FuZigiJWQiLCAmdCk7CiAgICAgICAgaWYodCA9PSAxKQogICAgICAgIHsKICAgICAgICAgICAgc2NhbmYoIiVkIiwgJmwpOwogICAgICAgICAgICBpbmQucGIobCk7CiAgICAgICAgfQogICAgICAgIGVsc2UKICAgICAgICB7CiAgICAgICAgICAgIHNjYW5mKCIlZCAlZCIsICZsLCAmcik7CiAgICAgICAgICAgIGFucyA9IHF1ZXJ5KGwscik7CiAgICAgICAgICAgIHByaW50ZigiJWxsZFxuIiwgYW5zKTsKICAgICAgICB9CiAgICAgICAgaWYoaW5kLnNpemUoKSA9PSBCVUNLRVRfU0laRSkKICAgICAgICAgICAgdXBkYXRlKG4pOwogICAgfQogCiAgICAgY2xrID0gY2xvY2soKSAtIGNsazsKICAgICAvL2NlcnIgPDwgZml4ZWQgPDwgc2V0cHJlY2lzaW9uKDYpIDw8ICJUaW1lOiAiIDw8ICgoZG91YmxlKWNsaykvQ0xPQ0tTX1BFUl9TRUMgPDwgIlxuIjsKICAgIHJldHVybiAwOwp9IA==