#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5;
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        string a, b;
        cin >> a >> b;
        if (n < m) {
            cout << "NO\n";
            continue;
        }
        bool same = true;
        for (int i = 1; i < b.size(); ++i) {
            if (a[i + n - m] != b[i]) {
                same = false;
                break;
            }
        }
        if (!same) {
            cout << "NO\n";
            continue;
        }
        for (int i = 0; i < n - m + 1; ++i) {
            if (a[i] == b[0]) {
                same = false;
            }
        }
        if (same) {
            cout << "NO\n";
        }
        else {
            cout << "YES\n";
        }
    }
}

#include <stdio.h>
#include <string.h>
#include <vector>
#include <set>
#include <queue>
#include <string>
#include <map>
#include <chrono>
#include <stdlib.h>
#include <time.h>
#include <algorithm>
#include <iostream>
#include <memory>
#include <cstdio>
#include <assert.h>
#include <iostream>
const int MAXN = 300005;
int numbers[MAXN];
int main() {
	int t;
	int n, x;

	scanf("%d", &t);
	while (t--)
	{
		scanf("%d %d", &n, &x);
		for (int i = 1; i <= n; i++) {
			scanf("%d", &numbers[i]);
		}
		int num_min = numbers[1];
		int num_max = numbers[1];
		int res = 0;
		for (int i = 2; i <= n; i++) {
			if (numbers[i] > num_max) {
				num_max = numbers[i];
			}
			if (numbers[i] < num_min) {
				num_min = numbers[i];
			}
			if (num_max - num_min > 2 * x) {
				res++;
				num_min = num_max = numbers[i];
			}
		}
		printf("%d\n", res);
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 500005, inf = 2147483647, M = 1004535809;
int n, m, a[N], T, k;
struct str {
	int x, y;
}t[N];
int main() {
	scanf("%d", &T);
	while (T--) {
		k = 0;
		scanf("%d %d", &n, &m);
		for (int i = 1; i <= m; ++i)
			scanf("%d", &a[i]);
		sort(a + 1, a + 1 + m);
		for (int i = 2; i <= m; ++i)
			t[++k] = { a[i] - a[i - 1] - 1,2 };
		int num_tmp = a[1] + n - a[m] - 1;
		if (num_tmp > 0) {
			t[++k] = { num_tmp, 2 };
		}
		sort(t + 1, t + 1 + k, [](str a, str b) {return a.x > b.x; });
		long long ans = 0, cnt = 0;
		for (int i = 1; i <= k; ++i) {
		    if (t[i].x - cnt * 2 > 0) {
		      int num_tmp = max(1ll, t[i].x - cnt * 2 - 1);
			  ans += num_tmp;
		    }
		    cnt += 2;
		}
		printf("%lld\n", n - ans);
	}
}

#include <stdio.h>
#include <string.h>
#include <vector>
#include <map>
#include <cassert>
const int MAXN = 500005;
std::vector<long long> numbers[MAXN];
std::map<long long, long long> val_to_index;
int main()
{
	int t;
	int n, m;
	scanf("%d ", &t);
	while (t--)
	{
		val_to_index.clear();
		scanf("%d %d", &n, &m);
		long long num_tmp;
		for (int i = 1; i <= n; i++) {
		    numbers[i].clear();
		    numbers[i].push_back(0);
			for (int j = 1; j <= m; j++) {
				scanf("%lld", &num_tmp);
				numbers[i].push_back(num_tmp);
			}
		}
		long long res_tmp = -1;
		for (long long i = 1; i <= n; i++) {
			long long val = 0;
			for (long long j = 1; j <= m; j++) {
				val += (j * numbers[i][j]);
			}
			if (val_to_index.find(val) != val_to_index.end()) {
			    res_tmp = val;
				val_to_index[val] = -1;
			}
			else {
				val_to_index[val] = i;
			}
		}
		assert(val_to_index.size() == 2);
		for (auto &item : val_to_index) {
			if (item.second != -1ll) {
				printf("%lld %lld\n", item.second, std::abs(res_tmp - item.first));
				break;
			}
		}
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 500005, inf = 2147483647, M = 998244353;
int n, m, a[N], u, v, i, d[N], q[N], r, mx;
int b[N], tmp[N];
vector<int> g[N], z[N];
long long s[N];
int p[15];
void NEX(int M) {
	for (int i = 1; i <= n; ++i)
		if (b[i]) {
			tmp[i] += b[i] - 1;
			for (auto it : g[i])
				++tmp[it];
		}
	for (int i = 1; i <= n; ++i) {
		if (tmp[i] >= M)
			b[i] = tmp[i] % M + M;
		else
			b[i] = tmp[i] % M;
		tmp[i] = 0;
	}
}
int cal(int M) {
	for (int i = 1; i <= n; ++i) {
		b[i] = a[i];
	}
	for (int i = 1; i <= n; ++i) {
		bool fl = false;
		for (int j = 1; j <= n; ++j)
			if (b[j])
				fl = true;
		if (!fl)
			return i - 1;
		NEX(M);
	}
	return n;
}
int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		scanf("%d %d", &n, &m);
		for (int i = 1; i <= n; ++i) {
			scanf("%d", &a[i]);
			g[i].clear();
			z[i].clear();
			d[i] = 0;
			tmp[i] = 0;
			s[i] = 0;
		}
		for (int i = 1; i <= m; ++i) {
			scanf("%d %d", &u, &v);
			++d[u];
			g[u].push_back(v);
			z[v].push_back(u);
		}
		mx = cal(M);
		if (mx < n) {
			cout << mx << endl;
			continue;
		}
		r = 0;
		for (int i = 1; i <= n; ++i)
			if (!d[i])
				q[++r] = i;
		s[q[1]] = 1;
		for (int i = 1; i <= r; ++i) {
			s[q[i]] %= M;
			for (auto it : z[q[i]]) {
				--d[it];
				s[it] += s[q[i]];
				if (!d[it])
					q[++r] = it;
			}
		}
		long long ans = n;
		for (int i = 1; i <= n; ++i)
			ans = (ans + s[i] * b[i]) % M;
		cout << ans << endl;
	}
}

#include<bits/stdc++.h>
using namespace std;
const int N=500005,inf=2147483647,M=998244353;
int n,i,t,f[N],vis[N];
char c[N];
int main(){
    for(int i=1;i<=1000;++i){
        for(int j=0;j<=i-2;++j)
            vis[f[j]^f[i-2-j]]=1;
        int j;
        for(j=0;vis[j];++j);
        f[i]=j;
        for(int j=0;j<=i;++j)
            vis[j]=0;
    }
    for(int i=1001;i<N;++i)
        f[i]=f[i-34];
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        scanf("%s",c+1);
        int s=0;
        for(int i=1;i<=n;++i)
            if(c[i]=='R')
                ++s;
            else
                --s;
        if(s>0)
            puts("Alice");
        if(s<0)
            puts("Bob");
        if(s==0){
            int ans=0;
            for(int i=1;i<=n;){
                int j=i+1;
                for(;j<=n&&c[j]!=c[j-1];++j);
                    ans^=f[j-i];
                i=j;
            }
            puts(ans?"Alice":"Bob");
        }
    }
}

#include<bits/stdc++.h>
using namespace std;
const int M1=998244353,M2=1004535809,M3=469762049,E=524288,N=200005;
struct poly{
    const int M;
    poly(int _M):M(_M){}
    int R[N*4];
    long long qpow(long long a,long long b){
        long long ans=1;
        while(b){
            if(b&1)
                ans=ans*a%M;
            a=a*a%M;
            b>>=1;
        }
        return ans;
    }
    long long wn[N*4],iwn[N*4],inv[N*4],fac[N*4],ifac[N*4];
    void init(int E,int g){
        int i;
        iwn[E/2]=wn[E/2]=1;
        long long s1=qpow(g,(M-1)/E);
        long long s2=qpow(s1,M-2);
        for(i=E/2+1;i<E;++i){
            wn[i]=wn[i-1]*s1%M;
            iwn[i]=iwn[i-1]*s2%M;
        }
        for(i=E/2-1;i;--i){
            wn[i]=wn[i<<1];
            iwn[i]=iwn[i<<1];
        }
        ifac[0]=fac[0]=inv[1]=1;
        for(i=2;i<E;++i)
            inv[i]=inv[M%i]*(M-M/i)%M;
        for(i=1;i<E;++i){
            ifac[i]=inv[i]*ifac[i-1]%M;
            fac[i]=fac[i-1]*i%M;
        }
    }
    unsigned long long ccc[N*4];
    void NTT(long long *f,int lim,int op){
        int i,j,k;
        for(i=0;i<lim;++i){
            R[i]=(R[i>>1]>>1)|(i&1?lim>>1:0);
            if(R[i]<i)
                swap(f[R[i]],f[i]);
        }
        for(i=0;i<lim;++i)
            ccc[i]=(f[i]%M+M)%M;
        for(i=1;i<lim;i<<=1)
            for(j=0;j<lim;j+=(i<<1))
                for(k=j;k<j+i;++k){
                    long long w=(op==1?wn[k-j+i]:iwn[k-j+i]);
                    unsigned long long p=ccc[k+i]*w%M;
                    ccc[k+i]=ccc[k]+M-p;
                    ccc[k]+=p;
                }
        for(i=0;i<lim;++i)
            f[i]=ccc[i]%M;
        if(op==-1){
            long long inv=qpow(lim,M-2);
            for(i=0;i<lim;++i)
                f[i]=f[i]*inv%M;
        }
    }
    long long ta[N*4],tb[N*4];
    void mult(long long *a,int n,long long *b,int m,long long *c){
        int lim=1;
        while(lim<n+m)
            lim<<=1;
        copy(a,a+n,ta);
        copy(b,b+m,tb);
        for(int i=n;i<lim;++i)
            ta[i]=0;
        for(int i=m;i<lim;++i)
            tb[i]=0;
        NTT(ta,lim,1);
        NTT(tb,lim,1);
        for(int i=0;i<lim;++i)
            ta[i]=ta[i]*tb[i]%M;
        NTT(ta,lim,-1);
        copy(ta,ta+lim,c);
    }
}X(M1),Y(M2),Z(M3);
int n,m,o[N],t,tn;
long long a[N],b[N],c[N],d[N*4],e[N],f[N*4],ss[N],td[N],tf[N];
bool fl[N],zz;
vector<int> ans;
long long cal(int l,int r){
    return 1ll*(l+r)*(r-l+1)/2;
}
long long cal2(int u,int v){
    return 1ll*((v-u)/2+1)*(u+v)/2;
}
bool iok(int n,int p,int q){
    long long ss=q+1ll*(n/2)*(n/2+1);
    p=p+(n/2+1);
    long long mn=cal(0,p-1),mx=cal(n-p+1,n);
    if(mn<=ss&&ss<=mx){
        for(int i=n;i<n+m-2;++i)
            if(td[i]!=tf[i-n+1]&&td[i]!=tf[i-n+1]-1)
                return false;
        ss-=mn;
        for(int i=n;i<n+m-2;++i)
            if(td[i]!=tf[i-n+1])
                ans.push_back(i+2);
        fill(fl,fl+1+n,0);
        for(int i=0;i<p;++i)
            fl[(ss/p+(i>=p-ss%p)+i)]=1;
        for(int i=0;i<=n;++i)
            if(fl[i]^(i&1)^1)
                if(n+1-i<=tn)
                    ans.push_back(n+1-i);
        zz=true;
        return true;
    }
    return false;
}
void OT(){
    if(!zz)
        puts("-1");
    else{
        printf("%d\n",ans.size());
        for(auto it:ans)
            printf("%d ",it);
        printf("\n");
    }
}
void judgement(poly &v,long long *c,long long *e){
    for(int i=0;i<n-2;++i)
        d[i]=(c[i+1]+c[i+2])%v.M;
    for(int i=0;i<m-2;++i)
        f[i]=(e[i+1]+e[i+2])%v.M;
    reverse(f,f+m-2);
    long long s=0;
    for(int i=0;i<m-2;++i)
        s+=(f[i]*f[i]-f[i])%v.M;
    for(int i=1;i<=n-2;++i)
        ss[i]=(ss[i-1]+d[i-1]*(d[i-1]+1))%v.M;
    v.mult(d,n-2,f,m-2,d);
    for(int i=m-3;i<n-2;++i)
        if((s+ss[i+1]-ss[i-m+3]-2*d[i])%v.M!=0)
            o[i-m+4]=0;
}
int main(){
    X.init(E,3);
    Y.init(E,3);
    Z.init(E,3);
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        tn=n;
        for(int i=1;i<=n;++i)
            scanf("%lld",&a[i]);
        scanf("%d",&m);
        for(int i=1;i<=m;++i)
            scanf("%lld",&b[i]);
        for(int i=1;i<n;++i)
            c[i]=a[i]+a[i+1];
        for(int i=1;i<m;++i)
            e[i]=b[i]+b[i+1];
        fill(o,o+1+n,0);
        ans.clear();
        for(int i=1;i<=n;++i)
            o[i]=1;
        if(m>2){
            for(int i=0;i<n-2;++i)
                td[i+1]=c[i+1]+c[i+2];
            for(int i=0;i<m-2;++i)
                tf[i+1]=e[i+1]+e[i+2];
            judgement(X,c,e);
            judgement(Y,c,e);
            judgement(Z,c,e);
        }
        else
            for(int i=1;i<=n;++i)
                o[i]=1;
        int x=-1;
        zz=false;
        if(m==1){
            for(int i=1;i<=n;++i)
                if(-cal2(0,i/2*2)<=b[1]-a[i]&&b[1]-a[i]<=cal2(1,(i-1)/2*2+1)){
                    for(int j=-(i/2+1);j<=(i+1)/2;++j)
                        if(iok(i,j,b[1]-a[i]))
                            break;
                    break;
                }
        }
        else
            for(int i=1;i+m-1<=n;++i)
                if(o[i]&&iok(i,(a[i]+a[i+1])-(b[1]+b[2]),b[1]-a[i]))
                    break;
        OT();
    }
}

#include<bits/stdc++.h>
using namespace std;
const int N=200005,E=15000005;
const long long inf=1000000000000000000ll;
int n,M,mi[5005][5005];
long long fac[N],inv[N],ans;
long long C(int n,int m){
    return fac[n]*inv[m]%M*inv[n-m]%M;
}
long long qpow(long long a,long long b){
    long long s=a,ans=1;
    while(b){
        if(b&1)
            ans=ans*s%M;
        s=s*s%M;
        b>>=1;
    }
    return ans;
}
int main(){
    cin>>n>>M;
    fac[0]=inv[0]=inv[1]=1;
    for(int i=2;i<=n;++i)
        inv[i]=inv[M%i]*(M-M/i)%M;
    for(int i=1;i<=n;++i){
        inv[i]=inv[i-1]*inv[i]%M;
        fac[i]=fac[i-1]*i%M;
    }
    long long s1=1;
    for(int i=0;i<=n;++i){
        mi[i][0]=1;
        for(int j=1;j<=n;++j)
            mi[i][j]=1ll*mi[i][j-1]*i%M;
    }
    for(int j=1;2*j<=n;++j){
        s1=s1*(n-1)%M;
        for(int i=0;i<=n-2*j;++i)
            ans=(ans+C(n,i)*fac[n-i]%M*s1%M*mi[n-i-j][i]%M*C(n-i-j-1,j-1)%M*inv[j])%M;
    }
    cout<<ans<<endl;
}

#include<bits/stdc++.h>
using namespace std;
const int N=100005,inf=2147483647;
const long long sq5=200717101;
int M;
namespace poly{
    int R[N*4];
    long long qpow(long long a,long long b){
        long long ans=1;
        while(b){
            if(b&1)
                ans=ans*a%M;
            a=a*a%M;
            b>>=1;
        }
        return ans;
    }
    long long wn[N*4],iwn[N*4],inv[N*4],fac[N*4],ifac[N*4],g;
    void init(int E){
        int i;
        iwn[E/2]=wn[E/2]=1;
        long long s1=qpow(g,(M-1)/E);
        long long s2=qpow(s1,M-2);
        for(i=E/2+1;i<E;++i){
            wn[i]=wn[i-1]*s1%M;
            iwn[i]=iwn[i-1]*s2%M;
        }
        for(i=E/2-1;i;--i){
            wn[i]=wn[i<<1];
            iwn[i]=iwn[i<<1];
        }
        ifac[0]=fac[0]=inv[1]=1;
        for(i=2;i<E;++i)
            inv[i]=inv[M%i]*(M-M/i)%M;
        for(i=1;i<E;++i){
            ifac[i]=inv[i]*ifac[i-1]%M;
            fac[i]=fac[i-1]*i%M;
        }
    }
    unsigned long long ccc[N*4];
    void NTT(long long *f,int lim,int op){
        int i,j,k;
        for(i=0;i<lim;++i){
            R[i]=(R[i>>1]>>1)|(i&1?lim>>1:0);
            if(R[i]<i)
                swap(f[R[i]],f[i]);
        }
        for(i=0;i<lim;++i)
            ccc[i]=(f[i]%M+M)%M;
        for(i=1;i<lim;i<<=1)
            for(j=0;j<lim;j+=(i<<1))
                for(k=j;k<j+i;++k){
                    long long w=(op==1?wn[k-j+i]:iwn[k-j+i]);
                    unsigned long long p=ccc[k+i]*w%M;
                    ccc[k+i]=ccc[k]+M-p;
                    ccc[k]+=p;
                }
        for(i=0;i<lim;++i)
            f[i]=ccc[i]%M;
        if(op==-1){
            long long inv=qpow(lim,M-2);
            for(i=0;i<lim;++i)
                f[i]=f[i]*inv%M;
        }
    }
    long long ta[N*4],tb[N*4];
    void mult(long long *a,int n,long long *b,int m,long long *c){
        int lim=1;
        while(lim<n+m)
            lim<<=1;
        copy(a,a+n,ta);
        copy(b,b+m,tb);
        for(int i=n;i<lim;++i)
            ta[i]=0;
        for(int i=m;i<lim;++i)
            tb[i]=0;
        NTT(ta,lim,1);
        NTT(tb,lim,1);
        for(int i=0;i<lim;++i)
            ta[i]=ta[i]*tb[i]%M;
        NTT(ta,lim,-1);
        copy(ta,ta+lim,c);
    }
    long long tmp[N*4],tans[N*4];
    void Getinv(long long *a,long long *ans,int lim){
        ans[0]=qpow(a[0],M-2);
        for(int i=1;i<lim;i<<=1){
            for(int j=i;j<(i<<2);++j)
                ans[j]=tans[j]=tmp[j]=0;
            for(int j=0;j<(i<<1);++j)
                tmp[j]=a[j];
            for(int j=0;j<i;++j)
                tans[j]=ans[j];
            NTT(tmp,i<<2,1);
            NTT(tans,i<<2,1);
            for(int j=0;j<(i<<2);++j)
                tmp[j]=tmp[j]*tans[j]%M*tans[j]%M;
            NTT(tmp,i<<2,-1);
            for(int j=0;j<(i<<1);++j)
                ans[j]=(2*ans[j]-tmp[j])%M;
        }
    }
    long long tinv[N*4];
    void Getln(long long *a,long long *ans,int n){
        for(int i=0;i<n-1;++i)
            ans[i]=a[i+1]*(i+1)%M;
        Getinv(a,tinv,n);
        mult(ans,n-1,tinv,n,ans);
        for(int i=n;i>=1;--i)
            ans[i]=ans[i-1]*inv[i]%M;
        ans[0]=0;
    }
    long long tln[N*4];
    void Getexp(long long *a,long long *ans,int n){
        ans[0]=1;
        for(int i=1;i<n;i<<=1){
            for(int j=i;j<(i<<1);++j)
                ans[j]=0;
            Getln(ans,tln,i<<1);
            for(int j=0;j<(i<<1);++j)
                tln[j]=-tln[j]+a[j];
            ++tln[0];
            mult(ans,i,tln,i<<1,ans);
        }
    }
    void Getroot(long long *a,long long *ans,int n){
        ans[0]=1;
        for(int i=1;i<n;i<<=1){
            fill(ans+i,ans+(i<<1),0);
            Getinv(ans,tinv,i<<1);
            mult(tinv,i<<1,a,i<<1,tinv);
            for(int j=0;j<(i<<1);++j)
                ans[j]=(ans[j]+tinv[j])*inv[2]%M;
        }
    }
    long long ttln[N*4];
    void Getpow(long long *a,long long *ans,int n,int m){
        Getln(a,ttln,m);
        for(int i=0;i<m;++i)
            ttln[i]=ttln[i]*n%M;
        Getexp(ttln,ans,m);
    }
};
int n,m;
long long f[N*4],g[N*4],h[N*4],hd[N*4],tmp[N*4],eh[N*4],tmp2[N*4],inv[N*4];
void Newton(int lim){
    f[0]=f[1]=0;
    for(int i=2;i<lim;i<<=1){
        poly::Getexp(f,g,i<<1);
        for(int j=(i<<1)-1;j>=1;--j)
            g[j]=g[j-1];
        g[0]=0;
        for(int j=0;j<(i<<1);++j)
            h[j]=(f[j]+g[j])%M;
        poly::Getexp(h,eh,i<<1);
        poly::mult(eh,i<<1,h,i<<1,tmp);
        ++h[0];
        ++g[0];
        poly::mult(g,i<<1,h,i<<1,tmp2);
        poly::mult(tmp2,i<<1,eh,i<<1,tmp2);
        for(int j=(i<<1);j>=1;--j){
            tmp2[j]=-tmp2[j-1];
            tmp[j]=-tmp[j-1];
        }
        tmp2[0]=1;
        for(int j=0;j<(i<<1);++j)
            tmp[j]=(tmp[j]+f[j])%M;
        poly::Getinv(tmp2,inv,i<<1);
        poly::mult(inv,i<<1,tmp,i<<1,h);
        for(int j=0;j<(i<<1);++j)
            f[j]=(f[j]-h[j])%M;
    }
}
long long rt[N*4],X[N*4],Y[N*4],p1[N*4],p2[N*4],p[N*4],e1[N*4],e2[N*4];
long long fd[N*4],gd[N*4],as[N*4],ans[N*4],as2[N*4];
int lim=1;
int main(){
    cin>>n>>M;
    int tmpp=M-1;
    vector<int> dz;
    for(int i=2;i*i<=tmpp;++i)
        while(tmpp%i==0){
            tmpp/=i;
            dz.push_back(i);
        }
    if(tmpp!=1)
        dz.push_back(tmpp);
    for(int i=2;i<M;++i){
        int z=M-1;
        bool fl=true;
        for(auto it:dz)
            if(poly::qpow(i,z/it)==1){
                fl=false;
                break;
            }
        if(fl){
            poly::g=i;
            break;
        }
    }
    poly::init(262144);
    ++n;
    while(lim<=n*2)
        lim<<=1;
    Newton(n+1);
    memset(inv,0,sizeof(inv));
    poly::Getexp(f,g,n+1);
    for(int j=n;j>=1;--j)
        g[j]=g[j-1];
    g[0]=0;
    for(int j=0;j<=n;++j)
        h[j]=(f[j]+g[j])%M;
    poly::Getexp(h,eh,n+1);
    for(int j=1;j<=n;++j)
        tmp[j]=-eh[j-1];
    tmp[0]=1;
    poly::Getln(tmp,as2,n+1);
    for(int j=1;j<=n;++j)
        as2[j]=(as2[j]-f[j])%M;
    poly::mult(eh,n+1,h,n+1,X);
    for(int i=0;i<=n;++i)
        eh[i]=(X[i]+eh[i])%M;
    for(int i=n;i>=1;--i){
        eh[i]=eh[i-1];
        Y[i]=eh[i];
    }
    eh[0]=0;
    poly::mult(eh,n+1,g,n+1,eh);
    for(int i=1;i<=n;++i)
        h[i]=(-eh[i]-Y[i])%M;
    h[0]=1;
    poly::Getln(h,as,n+1);
    for(int i=0;i<=n;++i)
        as[i]=(-as[i]+as2[i])%M;
    poly::Getexp(as,ans,n+1);
    --n;
    for(int i=1;i<=n;++i)
        printf("%lld\n",(ans[i]*poly::fac[i]%M+M)%M);
}

#include<bits/stdc++.h>
using namespace std;
#define O(x) cout<<#x<<" "<<(x)<<"\n"
inline int read(){
	int x=0,f=1,c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return f==1?x:-x;
}
const int N=104;
int n,sum,a[N];
vector<pair<int,int> >ans;
inline void solve(){
	n=read();
	sum=0;
	ans.clear();
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1;i<=n;i++){
		a[i]-=read();
		sum+=a[i];
	}
	if(sum){puts("-1");return;}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=a[i];j++){
			for(int k=1;k<=n;k++)if(a[k]<0){
				ans.push_back(make_pair(i,k));
				++a[k];
				break;
			}
		}
	}
	cout<<ans.size()<<"\n";
	for(auto v:ans)cout<<v.first<<" "<<v.second<<"\n";
}
int main(){
	for(int T=read();T--;)solve(); 
	return 0;
}

#include <cstdio>
const int Maxn=1000000;
char s[Maxn+5];
char ans[Maxn+5];
int n,m;
void solve(){
    scanf("%d%d",&n,&m);
    n=(n<<1)-1;
    for(int i=1;i<=m;i++){
        ans[i]=0;
    }
    for(int i=1;i<=n;i++){
        scanf("%s",s+1);
        for(int j=1;j<=m;j++){
            ans[j]^=s[j];
        }
    }
    for(int i=1;i<=m;i++){
        putchar(ans[i]);
    }
    putchar('\n');
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        solve();
    }
	return 0;
}

#include <bits/stdc++.h>
std::vector<int> a;
int cnt[100001][2];
int main() {
  int n, T, flag;
  scanf("%d", &T);
  while(T--){
	scanf("%d", &n), a.resize(n), flag = 0;
    for (int i = 0; i < n; ++i)
      scanf("%d", &a[i]), ++cnt[a[i]][i % 2];
    std::sort(a.begin(), a.end());
    for (int i = 0; i < n; ++i)
      --cnt[a[i]][i % 2];
    for (int i = 0; i < n; ++i)
      if (cnt[a[i]][0] != 0 || cnt[a[i]][1] != 0) {
        puts("NO"), flag = 1;
		break;
      }
    if (flag == 0) puts("YES");
	a.clear();
	for (int i = 0; i < n; ++i)
      cnt[a[i]][0] = cnt[a[i]][1] = 0;
  }
  return 0;
}

#include <bits/stdc++.h>
using namespace std;


const int MAXN = 100010;
const int MOD = 998244353;
char str[MAXN];
long long F[MAXN], rF[MAXN];
long long inv(long long a, long long m) {
	if (a == 1) return 1;
	return inv(m%a, m) * (m - m/a) % m;
}
int main() {
	int T;
	int n;
	F[0] = rF[0] = 1;
	for (int i = 1; i < MAXN; i++) {
		F[i] = F[i-1] * i % MOD;
		rF[i] = rF[i-1] * inv(i, MOD) % MOD;
	}
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		scanf("%s", str);
		int cg = 0;
		int c0 = 0;
		int c1 = 0;
		for (int i = 0; i < n; i++) {
			if (str[i] == '0') {
				c0++;
			} else if (i+1 < n && str[i+1] == '1') {
				cg++;
				i++;
			} else {
				c1++;
			}
		}
		long long ans = F[cg + c0] * rF[c0] % MOD * rF[cg] % MOD;
		printf("%d\n", (int) ans);
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int maxn=500;
const long long mod=998244353;
typedef pair<int,int> pii;
int n,x,y,s,t;
int a[maxn*2+5][maxn+5],b[maxn+5][maxn+5],f[maxn+5];
vector <pii> v;
vector <int> c[maxn+5][maxn+5];
int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d",&n);
        for (int i=1;i<=n;i++)
        {
            for (int j=1;j<=n;j++)
            {
                b[i][j]=0;
                c[i][j].clear();
            }
        }
        for (int i=1;i<=n*2;i++)
        {
            f[i]=0;
            for (int j=1;j<=n;j++)
            {
                scanf("%d",&a[i][j]);
                b[j][a[i][j]]++;
                c[j][a[i][j]].push_back(i);
            }
        }
        int top=0,tail=0;
        int cnt=0,idx=1;
        long long ans=1;
        v.clear();
        for (int i=1;i<=n;i++)
        {
            for (int j=1;j<=n;j++)
            {
                if (b[i][j]==1)
                {
                    tail++;
                    v.push_back(pii(i,j));
                }
            }
        }
        while (cnt<n)
        {
            if (top<tail)
            {
                x=v[top].first;
                y=v[top].second;
                if (b[x][y]!=1)
                {
                    top++;
                    continue;
                }
                for (int i=0;i<c[x][y].size();i++)
                {
                    if (f[c[x][y][i]]==0)
                    {
                        t=c[x][y][i];
                        break;
                    }
                }
            }
            else
            {
                while (f[idx]!=0)
                {
                    idx++;
                }
                t=idx;
                ans=ans*2%mod;
            }
            f[t]=1;
            cnt++;
            for (int i=1;i<=n;i++)
            {
                b[i][a[t][i]]=0;
            }
            for (int i=1;i<=n;i++)
            {
                for (int j=0;j<c[i][a[t][i]].size();j++)
                {
                    s=c[i][a[t][i]][j];
                    if (f[s]==0)
                    {
                        f[s]=2;
                        for (int k=1;k<=n;k++)
                        {
                            b[k][a[s][k]]--;
                            if (b[k][a[s][k]]==1)
                            {
                                tail++;
                                v.push_back(pii(k,a[s][k]));
                            }
                        }
                    }
                }
            }
            top++;
        }
        s=0;
        printf("%lld\n",ans);
        for (int i=1;i<=n*2;i++)
        {
            if (f[i]==1)
            {
                s++;
                if (s<n) printf("%d ",i); else printf("%d\n",i);
            }
        }
    }
}

#include<bits/stdc++.h>
using namespace std;
int n,m,i,j,k,ans1,ans2;
long long a[1010][1010];
long long c[1010],x,y,s,t,temp;
 
int main()
{
    scanf("%d%d",&n,&m);
    for (i=0;i<m;i++)
    {
        for (j=1;j<=n;j++)
        {
            scanf("%lld",&a[i][j]);
            c[i]+=a[i][j];
        }
    }
    x=(c[m-1]-c[0])/(m-1);
    for (i=1;i<m;i++)
    {
        if ((c[i]-c[0])!=x*i)
        {
            ans1=i;
            y=c[i]-c[0]-x*i;
            break;
        }
    }
    for (i=1;i<m-1;i++)
    {
        if (i-1!=ans1&&i!=ans1&&i+1!=ans1)
        {
            x=0;
            for (j=1;j<=n;j++)
            {
                x+=a[i-1][j]*a[i-1][j]+a[i+1][j]*a[i+1][j]-a[i][j]*a[i][j]*2;
            }
            break;
        }
    }
    i=ans1;
    t=s=0;
    for (j=1;j<=n;j++)
    {
        s+=a[i-1][j]*a[i-1][j]+a[i+1][j]*a[i+1][j];
        t+=a[i][j]*a[i][j]*2;
    }
    s-=x;
    for (j=1;j<=n;j++)
    {
        temp=t-a[i][j]*a[i][j]*2+(a[i][j]-y)*(a[i][j]-y)*2;
        if (temp==s)
        {
            ans2=a[i][j]-y;
            break;
        }
    }
    cout<<ans1<<' '<<ans2<<endl;
}

#include<bits/stdc++.h>
using namespace std;
const int N=2000005,E=1000001;
struct str{
	int l;
	long long x;
	int d;
	long long las(){return x+(l-1)*d;}
}a[N];
int ch[N][2],fa[N],h[N],tot,hc,ls[N],siz[N],i;
struct seg{
	int l,r,x;
	bool operator <(const seg &a)const
	{
		return a.r>r;
	}
};
set<seg> p;
void pushup(int i)
{
	siz[i]=siz[ch[i][0]]+siz[ch[i][1]]+a[i].l;
}
void rotate(int x)
{
    int y=fa[x];bool d=(ch[y][0]==x);
    ch[y][!d]=ch[x][d];
    if(ch[x][d]!=0)fa[ch[x][d]]=y;
    fa[x]=fa[y];if(fa[y])ch[fa[y]][ch[fa[y]][1]==y]=x;
    ch[x][d]=y;fa[y]=x;pushup(y);
}
void splay(int i,int x,int t=0)
{
	for(int y=fa[x];y!=t;rotate(x),y=fa[x])
		if(fa[y]!=t&&(ch[fa[y]][0]==y)==(ch[y][0]==x))
			rotate(y);
	pushup(x);
	h[i]=x;
}
void Findmx(int x)
{
	int i=h[x];
	while(ch[i][1])
		i=ch[i][1];
	splay(x,i);
}
void Findmn(int x)
{
	int i=h[x];
	while(ch[i][0])
		i=ch[i][0];
	splay(x,i);
}
void MMerge(int x,int y)
{
	if(h[y]==0||h[x]==0)
	{
		h[x]=h[y]=max(h[x],h[y]);
		return;
	}
	int i=h[y];
	for(;ch[i][0];i=ch[i][0]);
	ch[i][0]=h[x];
	fa[h[x]]=i;
	splay(y,h[x]);
}
int Merge(int x,int y)
{
	Findmx(x),Findmn(y);
	if(abs(a[h[x]].las()-a[h[y]].x)<=1)
	{
		MMerge(x,y);
		return x;
	}
	if(a[h[x]].las()>a[h[y]].x)
	{
		long long la=a[h[y]].x;
		while(h[x]&&abs(a[h[x]].las()-la)>1)
		{
			if(a[h[x]].d==-1)
				la+=a[h[x]].l;
			else
			{
				if(la+a[h[x]].l<a[h[x]].x)
					la+=a[h[x]].l;
				else
				{
					int li=(a[h[x]].l-a[h[x]].x+la+2)/2;
					la+=a[h[x]].l-li;
					a[h[x]].l=li;
					break;
				}
			}
			h[x]=ch[h[x]][0];
			fa[h[x]]=0;
			Findmx(x);
		}
		h[++hc]=++tot;
		a[tot]={(int)(la-a[h[y]].x),la,-1};
		pushup(tot);
		ls[hc]=ls[x];
		MMerge(x,hc);
		MMerge(hc,y);
	}
	else
	{
		long long la=a[h[x]].las();
		while(h[y]&&abs(a[h[y]].x-la)>1)
		{
			if(a[h[y]].d==1)
				la+=a[h[y]].l;
			else
			{
				if(a[h[y]].las()>la+a[h[y]].l)
					la+=a[h[y]].l;
				else
				{
					int li=(a[h[y]].x-la)/2;
					a[h[y]].x-=li;
					a[h[y]].l-=li;
					la+=li;
					break;
				}
			}
			h[y]=ch[h[y]][1];
			fa[h[y]]=0;
			Findmn(y);
		}
		h[++hc]=++tot;
		a[tot]={(int)(la-a[h[x]].las()),a[h[x]].las()+1,1};
		pushup(tot);
		ls[hc]=ls[x];
		MMerge(x,hc);
		MMerge(hc,y);
	}
	return hc;
}
void Find(int n,int x,int w)
{
	if(w<siz[ch[x][0]])
		Find(n,ch[x][0],w);
	else
		if(siz[ch[x][0]]+a[x].l>w)
		{
			if(siz[ch[x][0]]==w)
			{
				splay(n,x,0);
				return;
			}
			int tmp=ch[x][1];
			ch[x][1]=++tot;
			ch[tot][1]=tmp;
			if(tmp)
				fa[tmp]=tot;
			fa[tot]=x;
			a[tot].l=a[x].l-(w-siz[ch[x][0]]);
			a[x].l=w-siz[ch[x][0]];
			a[tot].x=a[x].x+a[x].d*a[x].l;
			a[tot].d=a[x].d;
			splay(n,tot,0);
			return;
		}
		else
			Find(n,ch[x][1],w-a[x].l-siz[ch[x][0]]);
}
void Update(int l,int x)
{
	if(l==ls[x])
		return;
	int ti=l-ls[x];
	ls[x]=l;
	Findmn(x);
	long long w=a[h[x]].x;
	h[++hc]=++tot;
	a[tot]={ti,w+ti,-1};
	pushup(tot);
	MMerge(hc,x);
	while(1)
	{
		Findmx(x);
		if(ti<a[h[x]].l)
		{
			a[h[x]].l-=ti;
			break;
		}
		ti-=a[h[x]].l;
		h[x]=ch[h[x]][0];
		fa[h[x]]=0;
	}
}
void Add(int ti,int l,int r)
{
	h[++hc]=++tot;
	a[tot]={r-l+1,1<<30,1};
	pushup(tot);
	seg t={l,r,hc};
	ls[hc]=ti;
	auto it=p.lower_bound(t);
	if(it!=p.end()&&it->l==r+1)
	{
		Update(ti,it->x);
		t.x=Merge(t.x,it->x);
		t.r=it->r;
		p.erase(it);
	}
	it=p.lower_bound(t);
	if(it!=p.begin())
	{
		--it;
		if(it->r==l-1)
		{
			Update(ti,it->x);
			t.x=Merge(it->x,t.x);
			t.l=it->l;
			p.erase(it);
		}
	}
	p.insert(t);
}
void Del(int ti,int l,int r)
{
	seg t=*p.lower_bound({l,r,0});
	p.erase(t);
	Update(ti,t.x);
	Find(t.x,h[t.x],l-t.l);
	int u=ch[h[t.x]][0];
	fa[u]=ch[h[t.x]][0]=0;
	pushup(h[t.x]);
	int v=0;
	if(siz[h[t.x]]!=r-l+1)
	{
		Find(t.x,h[t.x],r-l+1);
		v=ch[h[t.x]][0];
		fa[v]=ch[h[t.x]][0]=0;
		v=h[t.x];
	}
	if(l!=t.l)
	{
		h[++hc]=u;
		ls[hc]=ti;
		p.insert({t.l,l-1,hc});
	}
	if(r!=t.r)
	{
		h[++hc]=v;
		ls[hc]=ti;
		p.insert({r+1,t.r,hc});
	}
}
int n,l,r,x,y,u,v,tree[N*4],lazy[N*4];
long long as=1<<30;
struct node{
	int l,r;
};
vector<node> ad[E+5],de[E+5];
void modify(int i,int l,int r,int ll,int rr,int x)
{
	if(l>=ll&&r<=rr)
	{
		lazy[i]+=x;
		tree[i]+=x;
		return;
	}
	int mid=l+r>>1;
	if(mid>=ll)
		modify(i<<1,l,mid,ll,rr,x);
	if(mid<rr)
		modify(i<<1|1,mid+1,r,ll,rr,x);
	tree[i]=max(tree[i<<1],tree[i<<1|1])+lazy[i];
}
int Query(int i,int l,int r,int ll,int rr)
{
	if(l>=ll&&r<=rr)
		return tree[i];
	int mid=l+r>>1,s=0;
	if(mid>=ll)
		s=max(s,Query(i<<1,l,mid,ll,rr));
	if(mid<rr)
		s=max(s,Query(i<<1|1,mid+1,r,ll,rr));
	return s+lazy[i];
}
int Findmx(int i,int l,int r,int ll,int s)
{
	if(s+tree[i]==0)
		return -1;
	if(l==r)
		return l-1;
	int mid=l+r>>1;
	s+=lazy[i];
	if(l>=ll)
	{
		int y=Findmx(i<<1,l,mid,ll,s);
		if(y!=-1)
			return y;
		else
			return Findmx(i<<1|1,mid+1,r,ll,s);
	}
	if(mid>=ll)
	{
		int y=Findmx(i<<1,l,mid,ll,s);
		if(y!=-1)
			return y;
	}
	return Findmx(i<<1|1,mid+1,r,ll,s);
}
int Findmn(int i,int l,int r,int rr,int s)
{
	if(s+tree[i]==0)
		return -1;
	if(l==r)
		return l+1;
	int mid=l+r>>1;
	s+=lazy[i];
	if(r<=rr)
	{
		int y=Findmn(i<<1|1,mid+1,r,rr,s);
		if(y!=-1)
			return y;
		else
			return Findmn(i<<1,l,mid,rr,s);
	}
	if(mid<rr)
	{
		int y=Findmn(i<<1|1,mid+1,r,rr,s);
		if(y!=-1)
			return y;
	}
	return Findmn(i<<1,l,mid,rr,s);
}
void dfs(int i)
{
	if(!i)
		return;
	as=min({as,a[i].x,a[i].las()});
	dfs(ch[i][0]);
	dfs(ch[i][1]);
}
int main()
{
	scanf("%d",&n);
	scanf("%d",&x);
	for(i=1;i<=n;++i)
	{
		scanf("%d %d %d %d",&l,&r,&u,&v);
		--l,++r;
		de[l].push_back({u,v});
		ad[r].push_back({u,v});
	}
	p.insert({0,E*2+5,++hc});
	h[hc]=++tot;
	a[tot]={E*2+5-x+1,0,1};
	ch[tot][0]=2;
	fa[++tot]=1;
	a[tot]={x,x,-1};
	pushup(2);
	pushup(1);
	for(i=0;i<=E+1;++i)
	{
		for(auto it:ad[i])
		{
			modify(1,0,E,it.l,it.r,-1);
			auto ii=p.lower_bound({it.l,it.r,0});
			int nr=ii->l-1;
			--ii;
			int nl=ii->r+1;
			if(nl>nr)
				continue;
			int y=Findmx(1,0,E,nl,0);
			if(y>=nr||y==-1)
				Add(i,nl,nr);
			else
			{
				if(y>=nl)
					Add(i,nl,y);
				int y=Findmn(1,0,E,nr,0);
				if(y<=nr)
					Add(i,y,nr);
			}
		}
		for(auto it:de[i])
		{
			modify(1,0,E,it.l,it.r,1);
			while(1)
			{
				auto y=p.lower_bound({0,it.l,0});
				if(y!=p.end())
				{
					if(min(it.r,y->r)>=max(it.l,y->l))
						Del(i,max(it.l,y->l),min(it.r,y->r));
					else
						break;
				}
				else
					break;
			}
		}
	}
	dfs(h[p.begin()->x]);
	cout<<as;
}

// (insert magical incantation)
// (insert offerings for the Gods of codeforces judging servers)
//LXLORZ!!!!//rejudg
#include <bits/stdc++.h>
using namespace std;

#define MAXN 200005
#define SQRTN 210

namespace io {
const int __SIZE = (1 << 21) + 1;
char ibuf[__SIZE], *iS, *iT, obuf[__SIZE], *oS = obuf, *oT = oS + __SIZE - 1,
                                           __c, qu[55];
int __f, qr, _eof;
#define Gc()                                                                   \
  (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin),               \
               (iS == iT ? EOF : *iS++))                                       \
            : *iS++)
inline void flush() { fwrite(obuf, 1, oS - obuf, stdout), oS = obuf; }
inline void gc(char &x) { x = Gc(); }
inline void pc(char x) {
  *oS++ = x;
  if (oS == oT)
    flush();
}
inline void pstr(const char *s) {
  int __len = strlen(s);
  for (__f = 0; __f < __len; ++__f)
    pc(s[__f]);
}
inline void gstr(char *s) {
  for (__c = Gc(); __c < 32 || __c > 126 || __c == ' ';)
    __c = Gc();
  for (; __c > 31 && __c < 127 && __c != ' '; ++s, __c = Gc())
    *s = __c;
  *s = 0;
}
template <class I> inline bool gi(I &x) {
  _eof = 0;
  for (__f = 1, __c = Gc(); (__c < '0' || __c > '9') && !_eof; __c = Gc()) {
    if (__c == '-')
      __f = -1;
    _eof |= __c == EOF;
  }
  for (x = 0; __c <= '9' && __c >= '0' && !_eof; __c = Gc())
    x = x * 10 + (__c & 15), _eof |= __c == EOF;
  x *= __f;
  return !_eof;
}
template <class I> inline void print(I x) {
  if (!x)
    pc('0');
  if (x < 0)
    pc('-'), x = -x;
  while (x)
    qu[++qr] = x % 10 + '0', x /= 10;
  while (qr)
    pc(qu[qr--]);
}
struct Flusher_ {
  ~Flusher_() { flush(); }
} io_flusher_;
} // namespace io
using io::gc;
using io::gi;
using io::gstr;
using io::pc;
using io::print;
using io::pstr;

#define all(a) a.begin(), a.end()
#define fi first
#define se second
#define pb push_back
#define mp make_pair

using ll = long long;
using pii = pair<int, int>;

int n;
int a[MAXN], X[MAXN], Y[MAXN];

int Xa[MAXN], Ya[MAXN];

int dyn[SQRTN + 5];
bool dynp[MAXN];

int ps1[MAXN];
ll ps2[MAXN];

ll ps_7j[MAXN];

int fake_a[MAXN], fake_Xa[MAXN], fake_Ya[MAXN];

// TODO: replace with linked list

struct offl {
  int val, id, nxt;
} detecpool[(SQRTN * SQRTN * 11) / 2 + 5];

int detec[MAXN];
// int detec7[MAXN];
int detec8f[MAXN];
int detecX[MAXN], detecY[MAXN];

int dryans[(SQRTN * SQRTN * 3) / 2 + 5];
int dryansX[(SQRTN * SQRTN) / 2 + 5];
int dryansY[(SQRTN * SQRTN * 4) / 2 + 5];
ll dryans_7[(SQRTN * SQRTN) / 2 + 5];
ll dryans_8_former[(SQRTN * SQRTN * 2) / 2 + 5];
ll ijk_static[MAXN];

void dryrun(vector<pii> ops) {
  copy(a, a + n, fake_a);
  copy(Xa, Xa + n, fake_Xa);
  copy(Ya, Ya + n, fake_Ya);
  memset(detec, -1, sizeof detec);
  memset(detecX, -1, sizeof detecX);
  memset(detecY, -1, sizeof detecY);
  // memset(detec7, -1, sizeof detec7);
  memset(detec8f, -1, sizeof detec8f);
  int pooln = 0;
  auto push_back = [&](int *ve, int pos, int va, int id) {
    detecpool[pooln] = {va, id, ve[pos]};
    ve[pos] = pooln;
    pooln++;
  };
  int dryid = 0, dryidX = 0, dryidY = 0, dryid7 = 0, dryid8f = 0;
  for (auto [opn, r] : ops) {
    if (opn != -1) {
      assert(dynp[opn]);
      a[opn] = r;
      Xa[opn] = X[r];
      Ya[opn] = Y[r];
    } else {
      int mxdyn = 0;
      for (int i = 0; dyn[i] <= r; i++)
        mxdyn++;
      for (int _j = 0; _j < mxdyn; _j++) {
        int j = dyn[_j];
        int pfx_xai_km1 = 0;
        if (j != 0) {
          // int pfx_ixaj_jm1 = dryans[dryid++];
          // int pfx_iyaj_r = dryans[dryid++];
          // int pfx_iyaj_j = dryans[dryid++];
          push_back(detecX, j - 1, a[j], dryidX++);
          push_back(detecY, r, a[j], dryidY++);
          push_back(detecY, j, a[j], dryidY++);

          int k = dyn[_j];
          // pfx_xai_km1 = dryans[dryid++];
          // int pfx_yak_km1 = dryans[dryid++];
          push_back(detec, k - 1, Xa[k], dryid++);
          push_back(detec, k - 1, Ya[k], dryid++);

          // ll pfx_yak_km1 = dryans_7[dryid7++];
          // push_back(detec7, k - 1, Ya[k], dryid7++);
        }
        int i = j;
        if (i != r) {
          // ll sfx_xai_ip1 = dryans_8_former[dryid8f++];
          // ll sfx_xai_rp1 = dryans_8_former[dryid8f++];
          // int pfx_xai_r = dryans[dryid++];
          // int pfx_xai_i = pfx_xai_km1;
          // int pfx_iyxai_n = dryans[dryid++];
          // int pfx_iyxai_r = dryans[dryid++];
          push_back(detec8f, i + 1, Xa[i], dryid8f++);
          push_back(detec8f, r + 1, Xa[i], dryid8f++);
          push_back(detec, r, Xa[i], dryid++);
          push_back(detecY, n, Xa[i], dryidY++);
          push_back(detecY, r, Xa[i], dryidY++);
        }
      }
    }
  }
  for (int i = 0; i <= n; i++) {
    if (i != n && !dynp[i]) {
      ps1[a[i]]++;
    }
    for (int pid = detec[i]; pid != -1; pid = detecpool[pid].nxt)
      dryans[detecpool[pid].id] = ps1[detecpool[pid].val];
  }
  memset(ps1, 0, n * (sizeof(int)));
  ll cpsm = 0;
  for (int i = 0; i <= n; i++) {
    if (i != n && !dynp[i]) {
      cpsm += ps_7j[Ya[i]];
      ps_7j[a[i]] += ps1[a[i]];
      ps1[Xa[i]]++;
    }
    ijk_static[i] = cpsm;
    for (int pid = detecX[i]; pid != -1; pid = detecpool[pid].nxt) {
      dryansX[detecpool[pid].id] = ps1[detecpool[pid].val];
      dryans_7[detecpool[pid].id] = ps_7j[Y[detecpool[pid].val]];
    }
  }
  memset(ps1, 0, n * (sizeof(int)));
  for (int i = 0; i <= n; i++) {
    if (i != n && !dynp[i]) {
      ps1[Ya[i]]++;
    }
    for (int pid = detecY[i]; pid != -1; pid = detecpool[pid].nxt)
      dryansY[detecpool[pid].id] = ps1[detecpool[pid].val];
  }
  memset(ps1, 0, n * (sizeof(int)));
  memset(ps_7j, 0, n * (sizeof(ll)));

  for (int i = n; i >= 0; i--) {
    if (i != n && !dynp[i]) {
      ps2[a[i]] += ps1[a[i]];
      ps1[Ya[i]]++;
    }
    for (int pid = detec8f[i]; pid != -1; pid = detecpool[pid].nxt)
      dryans_8_former[detecpool[pid].id] = ps2[detecpool[pid].val];
  }
  memset(ps1, 0, n * (sizeof(int)));
  memset(ps2, 0, n * (sizeof(ll)));
  copy(fake_a, fake_a + n, a);
  copy(fake_Xa, fake_Xa + n, Xa);
  copy(fake_Ya, fake_Ya + n, Ya);
}

int PfxGud3[MAXN], SfxGud4[MAXN];

void process(vector<pii> ops) {
  set<int> mdfd;
  for (auto [xx, b] : ops)
    if (xx != -1)
      mdfd.insert(xx);
  int dync = 0;
  memset(dyn, 1, sizeof dyn);
  for (int i : mdfd)
    dyn[dync++] = i;
  memset(dynp, 0, sizeof dynp);
  for (int i = 0; i < dync; i++)
    dynp[dyn[i]] = 1;
  dryrun(ops);
  int dryid = 0, dryidX = 0, dryidY = 0, dryid6l = 0, dryid7 = 0, dryid8f = 0;
  for (auto [opn, r] : ops) {
    if (opn != -1) {
      a[opn] = r;
      Xa[opn] = X[r];
      Ya[opn] = Y[r];
    } else {
      int mxdyn = 0;
      for (int i = 0; dyn[i] <= r; i++)
        mxdyn++;
      ll P1 = ijk_static[r], P2 = 0, P3 = 0, P4 = 0, P5 = 0, P6 = 0, P7 = 0,
         P8 = 0;
      for (int _i = 0; _i < mxdyn; _i++) {
        int i = dyn[_i];
        PfxGud3[i] = ps1[a[i]];
        P2 += ps2[Ya[i]];
        ps2[a[i]] += ps1[a[i]];
        ps1[Xa[i]]++;
      }
      for (int _i = 0; _i < mxdyn; _i++) {
        int i = dyn[_i];
        ps2[a[i]] = 0;
        ps1[Xa[i]] = 0;
      }
      for (int _i = mxdyn - 1; _i >= 0; _i--) {
        int i = dyn[_i];
        SfxGud4[i] = ps1[a[i]];
        ps1[Ya[i]]++;
      }
      for (int _i = 0; _i < mxdyn; _i++) {
        int i = dyn[_i];
        ps1[Ya[i]] = 0;
      }
      for (int _j = 0; _j < mxdyn; _j++) {
        int j = dyn[_j];
        int pfx_xai_km1 = 0;
        if (j != 0) {
          int pfx_ixaj_jm1 = dryansX[dryidX++];
          int pfx_iyaj_r = dryansY[dryidY++];
          int pfx_iyaj_j = dryansY[dryidY++];
          P3 += PfxGud3[j] * (pfx_iyaj_r - pfx_iyaj_j);
          P4 += pfx_ixaj_jm1 * SfxGud4[j];
          P5 += 1ll * pfx_ixaj_jm1 * (pfx_iyaj_r - pfx_iyaj_j);

          int k = dyn[_j];
          pfx_xai_km1 = dryans[dryid++];
          int pfx_yak_km1 = dryans[dryid++];
          int pfxDyn_ixyak = ps1[Ya[k]];
          ll pfxDyn_BAD_ixyak = ps2[Ya[k]];
          ps1[Xa[k]]++;
          ps2[Xa[k]] += pfx_xai_km1;
          P6 += 1ll * pfx_yak_km1 * pfxDyn_ixyak - pfxDyn_BAD_ixyak;

          P7 += dryans_7[dryid7++];
        } else {
          ps1[Xa[j]]++;
        }
        int i = j;
        if (i != r) {
          ll sfx_xai_ip1 = dryans_8_former[dryid8f++];
          ll sfx_xai_rp1 = dryans_8_former[dryid8f++];
          int pfx_xai_r = dryans[dryid++];
          int pfx_xai_i = pfx_xai_km1;
          int pfx_iyxai_n = dryansY[dryidY++];
          int pfx_iyxai_r = dryansY[dryidY++];
          P8 += (sfx_xai_ip1 - sfx_xai_rp1) -
                1ll * (pfx_xai_r - pfx_xai_i) * (pfx_iyxai_n - pfx_iyxai_r);
        }
      }
      for (int _i = 0; _i < mxdyn; _i++) {
        int i = dyn[_i];
        ps2[Xa[i]] = 0;
        ps1[Xa[i]] = 0;
      }
      print(P1 + P2 + P3 + P4 + P5 + P6 + P7 + P8);
      pc('\n');
    }
  }
}

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int m;
  gi(n), gi(m);
  for (int i = 0; i < n; i++) {
    gi(a[i]);
    a[i]--;
  }
  for (int i = 0; i < n; i++) {
    gi(X[i]);
    X[i]--;
  }
  for (int i = 0; i < n; i++) {
    gi(Y[i]);
    Y[i]--;
  }
  for (int i = 0; i < n; i++) {
    Xa[i] = X[a[i]];
    Ya[i] = Y[a[i]];
  }
  vector<pii> opq;
  for (int qx = 0; qx < m; qx++) {
    int op, v;
    gi(op);
    gi(v);
    if (op == 1) {
      int r;
      gi(r);
      opq.push_back({v - 1, r - 1});
    } else {
      opq.push_back({-1, v - 1});
    }
    if (opq.size() == SQRTN) {
      process(opq);
      opq.clear();
    }
  }
  process(opq);
}