#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();
    }
}