#include<bits/stdc++.h>
#ifdef DEBUG_LOCAL
#include <mydebug/debug.h>
#endif
using ll = long long;
const int N = 2e5+5,mod = 1e9 + 7,inv = (1e9 + 8) / 2;
using namespace std;
int T,n,m,k,q,x,y,z,fg[30][2],pw[N * 2]; vector<pair<int,int>> g[N];
struct dsu{
    int tg[N],w[N],fa[N],as,fg,siz[N];
    int fd(int x){
        if(x == fa[x]) return x;
        int t = fa[x]; fa[x] = fd(fa[x]),w[x] ^= w[t];
        return fa[x];
    }void mg(int u,int v,int c){
        int ou = fd(u),ov = fd(v);
        if(siz[ou] < siz[ov]) swap(ou,ov),swap(u,v);
        if(ou == ov){
            if(w[u] ^ w[v] ^ c) fg = 1;
            return ;
        }siz[ou] += siz[ov];
        if(tg[ou] == -1) as --;
        if(tg[ov] == -1) as --;
        fa[ov] = ou,w[ov] = w[v] ^ w[u] ^ c;
        if(tg[ov] >= 0) tg[ov] ^= w[ov];
        tg[ou] = (tg[ou] == -2 ? -2 : (tg[ou] == -1 ? tg[ov] : (tg[ov] == -1 || tg[ou] == tg[ov] ? tg[ou] : -2)));
        if(tg[ou] == -1) as ++;
        if(tg[ou] == -2) fg = 1; 
    }void init(){
        as = 0,fg = 0;
        for(int i = 1;i <= n + m;i ++) fa[i] = i,siz[i] = 1,w[i] = 0,tg[i] = -1;
        for(int i = 2;i <= n + m;i ++) if(i != m + 1) as ++;
    }void tt(int x,int y){
        int ox = fd(x); y ^= w[x];
        if(tg[ox] == -1) as --;
        tg[ox] = (tg[ox] == -2 ? -2 : (tg[ox] == -1 ? y : (y == -1 || y == tg[ox] ? tg[ox] : -2)));
        if(tg[ox] == -2) fg = 1;
    }
}d[30][2];
inline int calc(int x,int y,int z){
    int res = 1,oz = z;
    for(int i = 0;i < 30;i ++){
        int sm = 0;
        for(int j = 0;j < 2;j ++){
            z = (oz >> i) & 1; 
            if(fg[i][j] || d[i][j].fg) continue;
            if(x == 1 && y == 1) {if(z != j) {fg[i][j] = 1;continue;}}
            else if(y == 1) d[i][j].tt(m + x,z);
            else if(x == 1) d[i][j].tt(y,z); 
            else d[i][j].mg(x + m,y,j ^ z);
            if(fg[i][j] || d[i][j].fg) continue;
            sm = (sm + pw[d[i][j].as]) % mod;
        }res = 1ll * res * sm % mod;
    }
    return res;
}void los(){
    cin >> n >> m >> k >> q;  int as = 1; pw[0] = 1;
    for(int i = 1;i <= n + m;i ++) pw[i] = 2ll * pw[i - 1] % mod;
    for(int i = 0;i < 30;i ++) for(int j = 0;j < 2;j ++) d[i][j].init(),fg[i][j] = 0;
    for(int i = 1;i < n + m;i ++) as = 1ll * as * (1ll << 30) % mod;
    for(int i = 1;i <= k;i ++) if(cin >> x >> y >> z,as) as = calc(x,y,z);
    cout << as << "\n";
    for(int i = 1;i <= q;i ++) cin >> x >> y >> z,as = as ? calc(x,y,z) : 0,cout << as << "\n";
}int main(){
   ios::sync_with_stdio(0),cin.tie(0);
    for(cin >> T;T --;) los();
}

We call a $$$\texttt{01}$$$ string $$$s$$$ of length $$$n$$$ good, if and only if:

• $$$\forall i \in [1,n],s_i \ne s_{n-i+1}$$$.

Given a $$$\texttt{01}$$$ string $$$s$$$, calculate how many substrings in $$$s$$$ are good.

$$$n \le 5 \times 10^5$$$.

/**
 *    author: sunkuangzheng
 *    created: 24.01.2024 15:12:52
**/
#include<bits/stdc++.h>
#ifdef DEBUG_LOCAL
#include <mydebug/debug.h>
#endif
using ll = long long;
const int N = 2e6+5;
using namespace std;
int T,n,m,sa[N],rk[N],ok[N],h[N],st[22][N];string s;
void los(){
    cin >> n >> s,s = s + '#' + string(s.rbegin(),s.rend());
    for(int i = n + 1;i < s.size();i ++) s[i] ^= 1;
    auto SA = [&](string &s,int &n){
        s = " " + s,n = s.size() - 1;
        for(int i = 1;i <= n;i ++) sa[i] = i,rk[i] = s[i];
        for(int j = 1;j < n;j *= 2){
            for(int i = 1;i <= n;i ++) ok[i] = rk[i]; int p = 0;
            sort(sa+1,sa+n+1,[&](int x,int y){return rk[x] < rk[y] || rk[x] == rk[y] && rk[x + j] < rk[y + j];});
            auto cmp = [&](int x,int y){return ok[x] == ok[y] && ok[x + j] == ok[y + j];};
            for(int i = 1;i <= n;i ++) if(cmp(sa[i],sa[i-1])) rk[sa[i]] = p; else rk[sa[i]] = ++p;
        }for(int i = 1,k = 0;i <= n;h[rk[i ++]] = k) for(k --,k = max(k,0);s[i + k] == s[sa[rk[i] - 1] + k];k ++);
        for(int i = 1;i <= n;i ++) st[0][i] = h[i];
        for(int j = 1;j <= __lg(n);j ++) for(int i = 1;i + (1 << j) - 1 <= n;i ++)
            st[j][i] = min(st[j-1][i],st[j-1][i + (1 << j - 1)]);
    };SA(s,m);
    auto lcp = [&](int i,int j){
        if(i = rk[i],j = rk[j],i > j) swap(i,j); assert(i != j);
        int k = __lg(j - i);
        return min(st[k][i+1],st[k][j-(1<<k)+1]);
    };auto get = [&](int i){return n + 2 + n - i;};
    ll ans = 0;
    for(int i = 1;i < n;i ++) ans += lcp(get(i),i + 1);
    cout << ans;
}int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    for(T = 1;T --;) los();
}

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int N=5e5,base=1e9+7;
char s[N+10];
ull h1[N+10],h2[N+10],p[N+10];
bool t1[N+10],t2[N+10];
int n; 
void init()
{
	p[0]=1ull;
	for(int i=1;i<=n;i++) p[i]=p[i-1]*base;
	for(int i=1;i<=n;i++) h1[i]=h1[i-1]*base+(s[i]=='1');
	for(int i=1;i<=n;i++) h2[i]=h2[i-1]*base+(s[n-i+1]=='0');
}
ull hs(ull *h,int l,int r) {return h[r]-h[l-1]*p[r-l+1];}
bool check(int l,int r) {return hs(h1,l,r)==hs(h2,n-r+1,n-l+1);}
int erfen(int i)
{
	int l=0,r=min(i,n-i),ans=0;
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(check(i-mid+1,i+mid)) 
		{
			l=mid+1;
			ans=mid;
		} 
		else r=mid-1;
	}
	return ans;
}
int main()
{
	ll ans=0;
	scanf("%d%s",&n,s+1); 
	init();
	for(int i=1;i<n;i++) ans+=erfen(i);
	printf("%lld",ans);
	return 0;
}