#include <bits/stdc++.h>

using namespace std;

const int SQ=150;
const int MAXN=100001;
const int MAXLEN=300002;

struct snode
{
    int maxl[SQ],maxr[SQ],maxi,len;
    snode(int x)
    {
        x=min(x,SQ-1);
        for(int i=0;i<SQ;i++)
        {
            maxl[i]=maxr[i]=(i<=x);
            len=1; maxi=x;
        }
    }
    snode()
    {
        maxi=len=0;
        for(int i=0;i<SQ;i++) maxl[i]=maxr[i]=0;
    }
    snode operator+(const snode& other) const
    {
        snode res;
        res.maxi=max(maxi,other.maxi);
        res.len=len+other.len;
        for(int i=0;i<SQ;i++)
        {
            res.maxl[i]=maxl[i];
            if(maxl[i]==len) res.maxl[i]+=other.maxl[i];
            res.maxr[i]=other.maxr[i];
            if(other.maxr[i]==other.len) res.maxr[i]+=maxr[i];
            if(maxr[i]||other.maxl[i]) res.maxi=max(res.maxi,i*(maxr[i]+other.maxl[i]+1));
        }
        return res;
    }
};

snode stree[4*MAXN];
int mtree[4*MAXN];
int lcparr[MAXN];
string arr[MAXN];
set<int> active;
int n,q;
char buf[MAXLEN];

void build(int sq,int node,int l,int r)
{
    if(l>r) return;
    if(l==r)
    {
        if(sq==-1) mtree[node]=arr[l].size();
        else stree[node]=snode(lcparr[l]);
        return;
    }
    int mid=(l+r)/2;
    build(sq,node*2,l,mid);
    build(sq,node*2+1,mid+1,r);
    if(sq==-1) mtree[node]=max(mtree[node*2],mtree[node*2+1]);
    else stree[node]=stree[node*2]+stree[node*2+1];
}

void update(int sq,int node,int l,int r,int ind)
{
    if(ind<l||ind>r||l>r) return;
    if(l==r)
    {
        if(sq==-1) mtree[node]=arr[l].size();
        else stree[node]=snode(lcparr[l]);
        return;
    }
    int mid=(l+r)/2;
    update(sq,node*2,l,mid,ind);
    update(sq,node*2+1,mid+1,r,ind);
    if(sq==-1) mtree[node]=max(mtree[node*2],mtree[node*2+1]);
    else stree[node]=stree[node*2]+stree[node*2+1];}

snode query(int sq,int node,int l,int r,int ql,int qr)
{
    if(r<ql||qr<l||l>r) return snode();
    if(ql<=l&&r<=qr)
        return stree[node];
    int mid=(l+r)/2;
    return query(sq,node*2,l,mid,ql,qr)+query(sq,node*2+1,mid+1,r,ql,qr);
}

int query(int node,int l,int r,int ql,int qr)
{
    if(r<ql||qr<l||l>r) return 0;
    if(ql<=l&&r<=qr) return mtree[node];
    int mid=(l+r)/2;
    return max(query(node*2,l,mid,ql,qr),query(node*2+1,mid+1,r,ql,qr));
}

int solve1(int l,int r)
{
    if(r<l) return arr[l].size();
    int maxi=query(1,1,0,n-2,l,r).maxi;
    return max(maxi,query(1,0,n-1,l,r+1));
}

int lb[2*MAXN],rb[2*MAXN];
stack<int> ll,rr;
vector<int> v;

int solve2(int l,int r)
{
    if(r<l) return arr[l].size();
    int last=-2;
    v.clear();
    for(auto it=active.lower_bound(l);it!=active.upper_bound(r);it++)
    {
        if((*it)!=last+1) v.push_back(0);
        last=(*it);
        v.push_back(lcparr[last]);
    }
    if(v.empty()) return 0;
    while(!ll.empty()) ll.pop();
    while(!rr.empty()) rr.pop();
    int i;
    for(i=0;i<v.size();i++)
    {
        while(!ll.empty()&&v[ll.top()]>=v[i]) ll.pop();
        if(ll.empty()) lb[i]=-1;
        else lb[i]=ll.top();
        ll.push(i);
    }
    for(i=v.size()-1;i>=0;i--)
    {
        while(!rr.empty()&&v[rr.top()]>=v[i]) rr.pop();
        if(rr.empty()) rb[i]=v.size();
        else rb[i]=rr.top();
        rr.push(i);
    }
    int ans=0;
    for(i=0;i<v.size();i++)
    {
        ans=max(ans,v[i]*(rb[i]-lb[i]));
    }
    return ans;
}

void update(int ind,int las)
{
    if(las>=SQ&&lcparr[ind]<SQ)
        active.erase(ind);
    if(las<SQ&&lcparr[ind]>=SQ)
        active.insert(ind);
    int i;
    /*for(i=las+1;i<min(SQ,lcparr[ind]+1);i++)
        update(i,1,0,n-2,ind);
    for(i=min(SQ-1,lcparr[ind]+1);i<=las;i++)
        update(i,1,0,n-2,ind);*/
    update(1,1,0,n-2,ind);
}

int lcp(int x,int y)
{
    int ans=0;
    while(ans<arr[x].size()&&ans<arr[y].size()&&arr[x][ans]==arr[y][ans]) ans++;
    return ans;
}

int main()
{
    scanf("%d %d",&n,&q);
    int i;
    for(i=0;i<n;i++)
    {
        scanf("%s",buf);
        arr[i]=buf;
    }
    for(i=0;i<n-1;i++)
        lcparr[i]=lcp(i,i+1);
    build(1,1,0,n-2);
    build(-1,1,0,n-1);
    for(i=0;i<n-1;i++)
    {
        if(lcparr[i]>=SQ) active.insert(i);
    }
    while(q--)
    {
        int t;
        scanf("%d",&t);
        if(t==1)
        {
            int l,r; scanf("%d %d",&l,&r); l--; r--;
            printf("%d\n",max(solve1(l,r-1),solve2(l,r-1)));
            fflush(stdout);
        }
        else
        {
            int ind;
            scanf("%d %s",&ind,buf);
            ind--;
            arr[ind]=buf;
            update(-1,1,0,n-1,ind);
            if(ind-1>=0)
            {
                int tmp=lcparr[ind-1];
                lcparr[ind-1]=lcp(ind-1,ind);
                update(ind-1,tmp);
            }
            if(ind+1<n)
            {
                int tmp=lcparr[ind];
                lcparr[ind]=lcp(ind,ind+1);
                update(ind,tmp);
            }
        }
    }
}