/*

定义 dp[t][i][j][k]代表填完前 t 个位置后，{0, 1, 2, 3} 这 4 个数字最后一次出现的位置，

排序后为 t, i, j, k(t > i > j > k) 的方案数目，则按照第 t 位的数字的四种选择，可以得

到四种转移。

t选t-1这个位置的数：dp[t][i][j][k]

t选i这个位置的数：dp[t][t-1][j][k]

t选j这个位置的数：dp[t][t-1][i][k]

t选k这个位置的数：dp[t][t-1][i][j]

枚举r[l]==t+1的所有条件，当且仅当满足所有条件时才进行转移 

最后的方案数=sum{dp[n]}

总时间复杂度 O(n4)。滚动一维，空间复杂度 O(n3)

*/

#include<bits/stdc++.h>

using namespace std;

#define maxn 110

#define ll long long

#define mod 998244353

ll dp[][maxn][maxn][maxn];

int n,m;

struct Node{

    int l,x;

    Node(){}

    Node(int l,int x):l(l),x(x){}

};

vector<Node>v[maxn];

inline void update(ll &a,ll b){

    a=(a+b);

    while(a>=mod)a-=mod;

}

int c;

void solve(){

    c=;

    dp[c][][][]=;

    for(int t=;t<=n;t++){

        c^=;

        for(int i=;i<=t;i++)

            for(int j=;j<=i;j++)

                for(int k=;k<=j;k++)

                    dp[c][i][j][k]=;

        for(int i=;i<t;i++)

            for(int j=;j<=i;j++)

                for(int k=;k<=j;k++){

                    update(dp[c][i][j][k],dp[c^][i][j][k]);

                    update(dp[c][t-][j][k],dp[c^][i][j][k]);

                    update(dp[c][t-][i][k],dp[c^][i][j][k]);

                    update(dp[c][t-][i][j],dp[c^][i][j][k]);

                }

        for(int p=;p<v[t].size();p++){//枚举每个条件

            int l=v[t][p].l,x=v[t][p].x;

            for(int i=;i<t;i++)

                for(int j=;j<=i;j++)

                    for(int k=;k<=j;k++){

                        int cnt=;

                        if(i>=l)cnt++;

                        if(j>=l)cnt++;

                        if(k>=l)cnt++;

                        if(cnt!=x)dp[c][i][j][k]=;

                    }

        }

    }

}

int main(){

    //ios::sync_with_stdio(false);

    int t;cin>>t;

    while(t--){

        for(int i=;i<maxn;i++)v[i].clear();

        scanf("%d%d",&n,&m);

        for(int i=;i<=m;i++){

            int l,r,x;

            scanf("%d%d%d",&l,&r,&x);

            v[r].push_back(Node(l,x));

        }

        solve();

        ll ans=;

        for(int i=;i<n;i++)

            for(int j=;j<=i;j++)

                for(int k=;k<=j;k++)

                    ans+=dp[c][i][j][k],ans%=mod;

        cout<<ans<<'\n';

    }

}

#include<bits/stdc++.h>

using namespace std;

#define maxn 300005

int cnt[maxn][],nxt[maxn][],pos[];

int n,k,l[],r[],used[],up,down;

char ans[maxn],s[maxn];

int judge(int i,int pos){

    int res1=,res2;

    for(int j=;j<;j++){

        if(used[j]+cnt[pos][j] < l[j])return ;

        res1+=max(,l[j]-used[j]);//后面最少要的字符个数

        res2+=min(cnt[pos][j],r[j]-used[j]);//后面最多能的字符个数

    }

    if(res1>k-i || res2<k-i)return ;

    return ;

}

void init(){

    memset(used,,sizeof used);

    up=down=;

    memset(cnt,,sizeof cnt);

    memset(ans,,sizeof ans);

}

int main(){

    while(scanf("%s%d",s+,&k)==){

        init();

        n=strlen(s+);

        for(int i=;i<;i++)scanf("%d%d",&l[i],&r[i]),up+=r[i],down+=l[i];

        for(int i=n;i>=;i--){

            for(int j=;j<;j++)

                if(s[i]-'a'==j)cnt[i][j]=cnt[i+][j]+;

                else cnt[i][j]=cnt[i+][j];

        }

        int flag=;

        if(down>k || up<k){puts("-1");continue;}

        for(int i=;i<;i++)if(cnt[][i]<l[i]){puts("-1");flag=;break;}

        if(flag)continue;

        for(int i=;i<;i++)pos[i]=n+;

        for(int i=n;i>=;i--){

            for(int j=;j<;j++)

                nxt[i][j]=pos[j];

            pos[s[i]-'a']=i;

        }

        for(int j=;j<;j++)nxt[][j]=pos[j];

        int now=;

        for(int i=;i<=k;i++){

            for(int j=;j<;j++){//第i位选择j

                if(used[j]>=r[j])continue;

                int tmp=nxt[now][j];

                used[j]++;

                if(judge(i,tmp+)){

                    ans[i]=j;

                    now=tmp;

                    break;

                }

                else

                    used[j]--;

            }

        }

        for(int i=;i<=k;i++)cout<<(char)(ans[i]+'a');

        puts("");

    }

}