#pragma once
template<size_tX=26,charmargin='a'>structTrie{structNode{array<int,X>nxt;vector<int>idxs;intidx;charkey;Node(charc):idx(-1),key(c){fill(nxt.begin(),nxt.end(),-1);}};vector<Node>st;Trie(charc='$'){st.emplace_back(c);}inlineint&next(inti,intj){returnst[i].nxt[j];}voidadd(conststring&s,intx){intpos=0;for(inti=0;i<(int)s.size();i++){intk=s[i]-margin;if(~next(pos,k)){pos=next(pos,k);continue;}intnpos=st.size();next(pos,k)=npos;st.emplace_back(s[i]);pos=npos;}st[pos].idx=x;st[pos].idxs.emplace_back(x);}intfind(conststring&s){intpos=0;for(inti=0;i<(int)s.size();i++){intk=s[i]-margin;if(next(pos,k)<0)return-1;pos=next(pos,k);}returnpos;}intmove(intpos,charc){assert(pos<(int)st.size());returnpos<0?-1:next(pos,c-margin);}intsize()const{returnst.size();}intidx(intpos){returnpos<0?-1:st[pos].idx;}vector<int>idxs(intpos){returnpos<0?vector<int>():st[pos].idxs;}};