对于一种权值的生成树的存在性，可以将其转化为该权值的生成树个数的计数问题。
先考虑运算若不是位运算，是加法的情况，要怎么处理。对于边权为 (v) 的一条边，将其边权赋为 (x^v)，然后应用矩阵树定理，若所得行列式的第 (i) 次项系数不为 (0)，即生成树个数不为 (0)，就说明存在边权和为 (i) 的生成树。
同样，对于位运算也是适用的。分别考虑每种边权，对于每种边权都构造出基尔霍夫矩阵，沃尔什变换后求解行列式，然后记录每种边权求得的行列式的值，对其逆沃尔什变换后即为答案。
因为每一位的位运算类型不同，所以沃尔什变换时要考虑每一位的类型，应用对应的变换。在应用矩阵树定理时还需模一个大质数。
(code:)
#include<bits/stdc++.h>
#define maxn 75
#define maxv 5010
#define p 998244353
#define inv2 499122177
using namespace std;
typedef long long ll;
template<typename T> inline void read(T &x)
{
x=0;char c=getchar();bool flag=false;
while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
if(flag)x=-x;
}
int n,m,w,all;
ll t[maxn][maxn][maxv],a[maxn][maxn],ans[maxv];
char s[maxn];
void FWT(ll *a,int type)
{
for(int len=1,pos=1;len<all;len<<=1,++pos)
{
for(int i=0;i<all;i+=len<<1)
{
for(int j=i;j<i+len;++j)
{
if(s[pos]=='|') a[j+len]=(a[j+len]+a[j]*type+p)%p;
if(s[pos]=='&') a[j]=(a[j]+a[j+len]*type+p)%p;
if(s[pos]=='^')
{
ll x=a[j],y=a[j+len];
a[j]=(x+y)%p,a[j+len]=(x-y+p)%p;
if(type!=1) a[j]=a[j]*inv2%p,a[j+len]=a[j+len]*inv2%p;
}
}
}
}
}
ll qp(ll x,ll y)
{
ll v=1;
while(y)
{
if(y&1) v=v*x%p;
x=x*x%p,y>>=1;
}
return v;
}
ll det()
{
ll v=1;
for(int i=1;i<n;++i)
{
int pos=i;
for(int j=i+1;j<n;++j)
{
if(a[j][i])
{
pos=j;
break;
}
}
if(pos!=i) swap(a[i],a[pos]),v*=-1;
if(!a[i][i]) return 0;
ll inv=qp(a[i][i],p-2);
for(int j=i+1;j<n;++j)
{
ll d=a[j][i]*inv%p;
for(int k=i;k<n;++k)
a[j][k]=(a[j][k]-a[i][k]*d%p+p)%p;
}
v=v*a[i][i]%p;
}
return v;
}
int main()
{
read(n),read(m);
scanf("%s",s+1),w=strlen(s+1),all=1<<w;
for(int i=1;i<=m;++i)
{
int x,y,v;
read(x),read(y),read(v);
t[x][x][v]++,t[y][y][v]++;
t[x][y][v]--,t[y][x][v]--;
}
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
FWT(t[i][j],1);
for(int k=0;k<all;++k)
{
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
a[i][j]=t[i][j][k];
ans[k]=det();
}
FWT(ans,-1);
for(int i=all-1;i>=0;--i)
{
if(ans[i])
{
printf("%d",i);
return 0;
}
}
puts("-1");
return 0;
}