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

typedef long long ll;
typedef unsigned long long ull;
#define PI acos(-1.0)
#define INF 0x3f3f3f3f3f3f3f3f
#define P pair<ll, int>
#define debug(x) cout << (#x) << ": " << (x) << " "
#define fastio ios::sync_with_stdio(false), cin.tie(0)
const int mod = 1e9 + 7;
const int M = 15 + 10;
const int N = 100000 + 10;

int t, n, q;

// suffix array
int sa[N], height[N], rk[N];
int k, tmp[N];
char s[N];

bool compare_sa(int i,int j){
    if(rk[i]!=rk[j]) return rk[i]<rk[j];
    else{
        int x=i+k<=n?rk[i+k]:-1;
        int y=j+k<=n?rk[j+k]:-1;
        return x<y;
    }
}

void calc_sa(char s[],int *sa){
    for(int i=0;i<=n;i++){
        sa[i]=i;
        rk[i]=i<n?s[i]:-1;
    }
    for(k=1;k<=n;k*=2){
        sort(sa,sa+n+1,compare_sa);
        tmp[sa[0]]=0;
        for(int i=1;i<=n;i++){
            tmp[sa[i]]=tmp[sa[i-1]]+(compare_sa(sa[i-1],sa[i])?1:0);
        }
        for(int i=0;i<=n;i++){
            rk[i]=tmp[i];
        }
    }
}

void calc_lcp(char s[],int *sa,int *lcp){
    for(int i=0;i<=n;i++) rk[sa[i]]=i;
    int h=0;
    lcp[0]=0;
    for(int i=0;i<n;i++){
        int j=sa[rk[i]-1];
        if(h>0) h--;
        for(;j+h<n&&i+h<n;h++){
            if(s[j+h]!=s[i+h]) break;
        }
        lcp[rk[i]-1]=h;
    }
}

// binary search of height
int f[N][M], lg2[N];

void ST_pre()
{
    for(int i = 1; i <= n; i ++) { lg2[i] = log2(i); }
    for(int i = 1; i <= n; i ++) { f[i][0] = height[i]; }
    for(int j = 1; j <= lg2[n]; j ++) {
        for(int i = 1; i <= n - (1<<j) + 1; i ++) {
            f[i][j] = min(f[i][j-1], f[i+(1<<(j-1))][j-1]);
        }
    }
}

int ST_query(int l, int r)
{
    int k = lg2[r - l + 1];
    return min(f[l][k], f[r-(1<<k)+1][k]);
}

int hquery_L(int p, int val)
{
    int l = 1, r = p;
    while(l < r) {
        int mid = l + r >> 1;
        if(ST_query(mid, p) >= val) r = mid;
        else l = mid + 1;
    }
    return r;
}

int hquery_R(int p, int val)
{
    int l = p, r = n;
    while(l < r) {
        int mid = l + r + 1 >> 1;
        if(ST_query(p, mid) >= val) l = mid;
        else r = mid - 1;
    }
    return l;
}

// segment tree of suffix array
struct node {
    int ls, rs;
    int num;
} tree[N<<5];
int rt[N], cnt;

void build(int &now, int l = 1, int r = n)
{
    now = ++cnt;
    tree[now].num = 0;
    if(l == r) return ;
    int mid = (l + r) >> 1;
    build(tree[now].ls, l, mid);
    build(tree[now].rs, mid + 1, r);
}

void add(int &now, int pre, int pos, int l = 1, int r = n)
{
    now = ++cnt;
    tree[now] = tree[pre];
    tree[now].num ++;
    if(l ==