My library

fast-io-and-init-code.cpp

#include"limits"
#include"cstdio"
#include"vector"
#include"list"
#include"cmath"
#include"set"
#include"map"
#include"queue"
#include"stack"
#include"bitset"
#include"cstring"
#include"cstdlib"
#include"string"
#include"cassert"
#include"iostream"
#include"algorithm"
#include"functional"
#include"numeric"
#include"sstream"
#include"iomanip"
#include"cctype"
#include"ctime"

#define MAX_INPUT 10<<20
#define MAX_OUTPUT 10<<20

typedef long double F128;       //            1.18973... E 4932
typedef double F64;             //            1.79769... E 308
typedef float F32;              //            3.40282... E 38
#if !defined(__STRICT_ANSI__) && defined(_GLIBCXX_USE_INT128)
typedef unsigned __int128 I128; // 3.4028236692093846... E 38
typedef signed __int128 I127;   // 1.7014118346046923... E 38
#endif
typedef unsigned long long I64; // 1.8446744073709551615 E 19
typedef signed long long I63;   //  9.223372036854775807 E 18
typedef unsigned int I32;       //           4.294967295 E 9
typedef signed int I31;         //           2.147483647 E 9
typedef unsigned short I16;     //                6.5535 E 4
typedef signed short I15;       //                3.2767 E 4
typedef unsigned char I8;       //                  2.55 E 2
typedef signed char I7;         //                  1.27 E 2
const I64 ULMAX = std::numeric_limits<I64>::max();
const I63 SLMAX = std::numeric_limits<I63>::max();
const I63 SLMIN = std::numeric_limits<I63>::min();
const I32 UIMAX = std::numeric_limits<I32>::max();
const I31 SIMAX = std::numeric_limits<I31>::max();
const I31 SIMIN = std::numeric_limits<I31>::min();
const I16 USMAX = std::numeric_limits<I16>::max();
const I15 SSMAX = std::numeric_limits<I15>::max();
const I15 SSMIN = std::numeric_limits<I15>::min();
const I8 UCMAX = std::numeric_limits<I8>::max();
const I7 SCMAX = std::numeric_limits<I7>::max();
const I7 SCMIN = std::numeric_limits<I7>::min();

const F64 PI = acos(-1);
const I63 INF2 = SLMAX>>1;
const I63 INF  = SIMAX>>1;
const F64 EPS = 1e-9;

template<typename T> struct unsign {
    typedef T type;
};

template<> struct unsign<I7> {
    typedef I8 type;
};
template<> struct unsign<I15> {
    typedef I16 type;
};
template<> struct unsign<I31> {
    typedef I32 type;
};
template<> struct unsign<I63> {
    typedef I64 type;
};
#if !defined(__STRICT_ANSI__) && defined(_GLIBCXX_USE_INT128)
template<> struct unsign<I127> {
    typedef I128 type;
};
#endif
template<bool b> class param{};
class IO {
    char INPUT[MAX_INPUT], OUTPUT[MAX_OUTPUT];
    char* inp, *otp;
    I32 inpsz;
    public:
    IO() {
        assert((inpsz=fread(INPUT, 1, sizeof(INPUT), stdin))<MAX_INPUT);
        inp = INPUT;
        otp = OUTPUT;
    }
    bool eof() {
        while(*inp>='\t' and *inp<=' ') inp++;
        return inp >= INPUT + inpsz;
    }
    template<typename T> inline void parse(T& n, param<true>) {
        n=(*inp)-'0';
        while(*++inp>='0')
            n = (n<<3)+(n<<1)+(*inp)-'0';
    }
    template<typename T> inline void parse(T& n, param<false>) { // decimal num
        n = 0;
        T pow = 1;
        bool seen_decimal = false;
        while((*inp>='.' and *inp<='9'))
            if(*inp=='.')
                seen_decimal = true, inp++;
            else if(not seen_decimal)
                n = n*10+(*inp++)-'0';
            else
                n = n + ((*inp++)-'0')*(pow*=0.1);
        while(*inp>' ') inp++; // parse that token
        // not handling 1e8
    }
    template<bool nonempty> inline void readline(char* c) {
        if(nonempty)
            while(*inp=='\n') inp++;
        while(*inp>'\n')*c++ = *inp++;
        *c = 0;
        inp++;
    }
    template<typename T> inline void read_vector(std::vector<T>& v, I32 sz=-1) {
        if(not (sz+1))
            (*this)>>sz;
        while(sz--) {
            T temp;
            (*this)>>temp;
            v.push_back(temp);
        }
    }
    template<typename T> inline void write(param<true>, T n) {
        I8 len = n>9?(n>99?(n>999?(n>9999?(n>99999?(n>999999?(n>9999999?(n>99999999?(n>999999999?10:9):8):7):6):5):4):3):2):1, j;
        if(len>9 and n>9999999999ll) {
            while(len<19 and lengs[len]<n)
                len++;
            if(n>9999999999999999999ull) len++;
        }
        j = len;
        while(--j)
            otp[j] = '0'+n%10, n/=10;
        *otp = n+'0';
        //assert(len==1 or (*otp>'0' and *otp<='9'));
        otp += len;
    }
    template<typename T> inline void write(param<false>, T& n) {
        const I8 len = sizeof(T);
        otp += sprintf(otp, len<=4?"%f":(len<=8?"%lf":"%Lf"), n);
    }
    template<typename T> inline IO& operator>>(T& n) {
        bool sgn=0;
        if(std::numeric_limits<T>::is_signed)
            while(*inp<'.') sgn = sgn or *inp=='-', inp++;
        else 
            while(*inp<'.') inp++;
        parse<T>(n, param<std::numeric_limits<T>::is_integer>());
        if(sgn) n = -n;
        return *this;
    }
    inline IO& operator>>(char* c) {
        while(*inp<=' ') inp++;
        *c++ = *inp++;
        while(*inp>' ') *c++ = *inp++;
        *c = 0;
        return *this;
    }
    inline IO& operator>>(char& c) {
        c = *inp++;
        return *this;
    }
    const static I64 lengs[19];
    template<typename T> inline IO& operator<<(T n) {
        if(n<0) *otp++ = '-', n = -n;
        write<T>(param<std::numeric_limits<T>::is_integer>(), n);
        return *this;
    }
    inline IO& operator<<(const char c) {
        *otp++ = c;
        return *this;
    }
    inline IO& operator<<(char* c) {
        while(*c)
            *otp ++ = *c++;
        return *this;
    }
    inline IO& operator<<(const char* c) {
        while(*c)
            *otp ++ = *c++;
        return *this;
    }
    void flush() {
        fwrite(OUTPUT, 1, otp-OUTPUT, stdout);
        otp = OUTPUT;
    }
    ~IO() {
        flush();
    }
};
const I64 IO::lengs[19] = {0, 9, 99, 999, 9999, 99999, 999999, 9999999, 99999999, 999999999, 9999999999ll, 99999999999ll, 999999999999ll, 9999999999999ll, 99999999999999ll, 999999999999999ll, 9999999999999999ll, 99999999999999999ll, 999999999999999999ll};
#if !defined(__STRICT_ANSI__) && defined(_GLIBCXX_USE_INT128)
template<> inline void IO::write(param<true>, I128 n) {
    I8 len = n>9?(n>99?(n>999?(n>9999?(n>99999?(n>999999?(n>9999999?(n>99999999?(n>999999999?10:9):8):7):6):5):4):3):2):1, j;
    if(len>9 and n>9999999999ll) {
        while(len<19 and lengs[len]<n)
            len++;
        if(n>9999999999999999999ull) {
            I128 m = n/10000000000000000000ull;
            write(param<true>(), m);
            n %= 10000000000000000000ull;
        }
    }
    j = len;
    while(--j)
        otp[j] = '0'+n%10, n/=10;
    *otp = n+'0';
    otp += len;
}
#endif
using namespace std;
IO io;
template<class T1, class T2> inline T1 min(T1 a, T2 b){return a<b?a:b;}
template<class T1, class T2> inline T1 max(T1 a, T2 b){return b<a?a:b;}
template<class T1, class T2> inline void putmin(T1 a, T2 b){if(b<a)a=b;}
template<class T1, class T2> inline void putmax(T1 a, T2 b){if(a<b)a=b;}

#define SIZE(A) ((int)A.size())
#define LENGTH(A) ((int)A.length())
#define MP(A,B) make_pair(A,B)
#define PB(X) push_back(X)
#define REP(i,n) for(I32 i=0; i<(n); i++)
#define LOOP(i, a, b) for(I32 i=(a); i<(b); i++)
#define ALL(x) (x).begin(), (X).end()
#define FOREACH(it, x) for(typeof((x).begin()) it=(x).begin(); it!=(x).end(); it++)

void preprocess(){
}
void solve(){
}
int main() {
    preprocess();
    I32 T;
    io>>T;
    for(I32 i=0; i<T; i++) {
        solve();
    }
    io.flush();
}

LCA.cpp

#include"cassert"
#include"vector"
typedef unsigned int I32;
typedef I32* P32;
template <typename T, int beginidx=0> // in case vertices of graph are like 1, 2, 3 ..., beginidx becomes 1
class LCA {
    P32 height, pathno, head, ancestor, log;
    std::vector<I32>* paths;
    const I32 ulim, root;
    const T* const G;
    typedef typename T::const_iterator IT;
    I32 dfsdown(I32 r, I32 p, I32 pre) {
        pathno[r] = pre;
        I32 l = pre&-pre, ht = height[r]+1;
        pre++;
        for(IT it = G[r].begin(); it!=G[r].end(); it++) {
            if(it->v == p) continue;
            height[it->v] = ht;
            pre = dfsdown(it->v, r, pre);
            I32 tmp = pathno[it->v]&-pathno[it->v];
            if(l<tmp)
                pathno[r] = pathno[it->v], l = tmp;
        }
        return pre;
    }
    void dfsup(I32 r, I32 p) {
        const I32 my_pth=pathno[r];
        paths[my_pth].push_back(r);
        for(IT it = G[r].begin(); it!=G[r].end(); it++) {
            if(p==it->v) continue;
            I32 pth = pathno[it->v];
            if(pth!=my_pth) {
                head[pth] = r,
                ancestor[pth] = ancestor[my_pth] | (pth&-pth);
            }
            dfsup(it->v, r);
        }
    }
    inline I32 trivial(const I32 x, const I32 y) const {
        return height[x]<height[y]?x:y;
    }
    public:
    LCA(const T* g, const I32 n, const I32 root): ulim(beginidx+n), root(root), G(g) {
        assert(n);
        height = new I32[n];
        pathno = new I32[n];
        head = new I32[n];
        ancestor = new I32[n];
        paths = new std::vector<I32>[n];
        I32 m = n;
        m |= m>>1; m |= m>>2; m |= m>>4; m |= m>>8; m |= m>>16;
        log = new I32[m+1];
        log[0] = 0, log[1] = 1;
        for(int i=2; i<=m; i++) log[i] = log[i-1]<<((i&(i-1))?0:1); // log[i] = 1<<floor(lg i)
        if(beginidx) height-=beginidx, pathno-=beginidx;
        head--, ancestor--, paths--;
        height[root] = 0;
        dfsdown(root, -1, 1);
        ancestor[pathno[root]] = pathno[root];
        dfsup(root, -1);
        head[pathno[root]] = root;
    }
    inline I32 operator()(I32 x, I32 y) const { // lca of x and y
        assert(x>=beginidx and x<ulim and y>=beginidx and y<ulim);
        const I32 px = pathno[x], py = pathno[y];
        if(px==py) return trivial(x,y);
        I32 k, j = ancestor[py]&ancestor[px]&-log[px^py];
        j &= -j;
        if((k = log[ancestor[px]&(j-1)]))
          x = head[(px&-k)|k];
        if((k = log[ancestor[py]&(j-1)]))
          y = head[(py&-k)|k];
        return trivial(x, y);
    }
    inline I32 ht(I32 x) const { // height of x
       assert(x>=beginidx and x<ulim);
       return height[x];
    }
    inline I32 parent(I32 x, I32 k) const { // kth ancestor of x in log N time
        assert(x>=beginidx and x<ulim);
        assert(k<=height[x]);
        k = height[x] - k;
        I32 px = pathno[x], tmp;
        while(height[tmp=head[px]]>k)
            px=pathno[x=tmp];
        if(height[tmp]==k) return tmp;
        if(px!=pathno[root])
            k = k-(height[tmp]+1);
        return paths[px][k]; // return kth vertex on current path
    }
    ~LCA() {
        if(beginidx) height+=beginidx, pathno+=beginidx;
        head++, ancestor++, paths++;
        for(I32 i=0; i<ulim-beginidx; i++) paths[i].clear();
        delete[] height;
        delete[] pathno;
        delete[] head;
        delete[] ancestor;
        delete[] log;
        delete[] paths;
    }
};

online-suffix-tree.cpp

#include"stdio.h"
#include"iostream"
#include"cassert"
#include"string.h"
#include"string"
using namespace std;
template<int SIGMA=256, typename alphabet=unsigned char>
class Ukkonen {
#define INF 1000000000
    struct Link {
        int start, end, nxt;
        inline int len() const { return end-start; }
        inline void set(int st, int ed, int nx) { start = st, end = ed, nxt = nx; }
        inline void split(int depth, Link& intermediate, int new_idx) {
            intermediate.nxt = nxt;
            intermediate.end = end;
            intermediate.start = start+depth;
            end = intermediate.start;
            nxt = new_idx;
        }
    };
    struct Node {
        int suffix_link;
        int children[SIGMA];
        Node() { suffix_link = 0; memset(children, 0, sizeof(children)); }
    };
    inline Link& get_link(int n_idx, const alphabet i) {
        int& c = all_nodes[n_idx].children[i];
        if(c) return all_links[c];
        return all_links[c=++last_used_link];
    }
    Node* all_nodes;
    Link* all_links;
    int last_used_node, last_used_link;
    int iL, j, N;
    int active_node, active_depth, MAX_int_nodes, MAX_links;
    alphabet active_child;
    alphabet* str;
    int* leaf_parent_indices;
    public:
    long long distinct_substr_count;
    Ukkonen(int n, alphabet first) {
        N = n;
        iL = 0;
        j = -1;
        leaf_parent_indices = new int[N];
        MAX_int_nodes = N+1;
        MAX_links = MAX_int_nodes + N + 1;
        all_nodes = new Node[MAX_int_nodes];
        all_links = new Link[MAX_links];
        last_used_node = 0;
        last_used_link = 0;
        active_node = 0, active_depth = 0;
        str = new alphabet[N+1];
        get_link(0,first).set(iL, INF, iL);
        iL++;
        str[++j] = first;
        distinct_substr_count=1;
    }
    ~Ukkonen() {
        delete[] leaf_parent_indices;
        delete[] all_nodes;
        delete[] all_links;
        delete[] str;
    }
    bool next(alphabet c, int& parent, int& parent_depth) {
        int l = all_nodes[active_node].children[active_child];
        parent_depth = active_depth;
        parent = active_node;
        while(active_depth and all_links[l=all_nodes[parent=active_node].children[active_child]].len()<=(parent_depth=active_depth))
            active_node = all_links[l].nxt,
                        active_depth -= all_links[l].len(),
                        active_child = str[j-active_depth];
        l = all_nodes[active_node].children[active_child];
        if (l==0) return false;
        alphabet c2 = str[all_links[l].start+active_depth];
        if(c2==c)
            return true; // next exists
        assert(parent_depth and ++last_used_node<MAX_int_nodes);
        active_node = last_used_node;
        all_links[l].split(active_depth, get_link(active_node, c2), last_used_node);
        active_depth = 0;
        active_child = c;
        return false;
    }
    void insert(alphabet c) {
        assert(c<SIGMA);
        str[++j] = c;
        assert(j<N);
        active_child = str[j-active_depth];
        int last = -1, parent, parent_depth;
        while(iL<=j and not next(c, parent, parent_depth)) {
            if(last>=0)
                all_nodes[last].suffix_link = active_node;
            last = active_node;
            get_link(active_node, active_child).set(j-active_depth, INF, iL);
            iL++;
            active_node = parent = all_nodes[parent].suffix_link;
            if(active_node==0)
                parent_depth = j>=iL? j - iL:0;
            active_depth = parent_depth;
            active_child = str[j-active_depth];
        }
        if(last>=0)
            all_nodes[last].suffix_link = active_node;
        if(iL<=j)
            active_depth++;
        distinct_substr_count += iL;
        /*      cerr<< "after insertion active (node = "<<active_node << " , depth = "<<active_depth<<" , child = "<<active_child <<") iL " <<iL<< " j "<<j << " \n";
                print();
                cerr << "-----------------------------------------------------------------------------------------------------------------------------------\n";*/
    }
    void print(int node = 0, string prefix="") {
        if(node<0) return;
        cerr << prefix << "node : "<<node << " suffix_link " << all_nodes[node].suffix_link <<"\n";
        for(int i=0; i<SIGMA; i++)
            if(all_nodes[node].children[i]) {
                cerr << prefix << node << " ---" << string(str+get_link(node,i).start, str+min(j+1, get_link(node,i).end)) << "---> " << get_link(node,i).nxt <<"\n";
                print(get_link(node,i).nxt, prefix+"\t");
            }
    }
    unsigned int getSA(unsigned int* SA, int node=0) {
        if(node<0) return;
        unsigned int l, ret=0;
        for(int i=0; i<SIGMA; i++)
            if(l=all_nodes[node].children[i]) {
                Link& lnk = all_links[l];
                if(lnk.end>=INF)
                    SA[ret++] = lnk.nxt;
                else
                    ret+= getSA(SA+ret, lnk.nxt);
            }
        return ret;
    }
};

RMQ.cpp

#include"cassert"
#include"vector"
#include"stack"
#include"LCA.cpp"
typedef unsigned int I32;
typedef I32* P32;
template<typename T, typename less = std::less<T>> // RMQ over T
class RMQ {
    T* values;
    I32 N;
    struct ed{I32 v;ed(I32 x){v=x;}};
    LCA<std::vector<ed>,0>* lca;
    public:
    template<typename IT> RMQ(IT beg, const IT end) {
        N = end - beg;
        if(N<1) return;
        // build cartesian tree
        P32 parent = new I32[N];
        values = new T[N];
        parent[0] = -1;
        std::stack<I32> s;
        s.push(0);
        values[0] = *beg++;
        for(I32 i=1; i<N; i++, beg++) {
            values[i] = *beg;
            I32 last=-1;
            while((not s.empty()) and less()(*beg, values[s.top()]))
                last=s.top(), s.pop();
            if(last+1)
                parent[i] = parent[last], parent[last] = i;
            else
                parent[i] = s.top();
            s.push(i);
        }
        std::vector<ed> G[N];
        I32 root=-1;
        for(I32 i=0,p; i<N; i++)
            if((p=parent[i])+1)
                G[p].push_back(ed(i));
            else root = i;
        assert(root+1);
        lca = new LCA<std::vector<ed>,0>(G, N, root);
        // build LCA
    }
    T operator()(const I32 i, const I32 j) { // index of min
        return (*lca)(i, j);
    }
    T MIN(const I32 i, const I32 j) {
        return values[(*lca)(i,j)];
    }
    ~RMQ() {
        delete[] values;
        delete lca;
    }
};

segtree.cpp

#include"assert.h"
struct segtree_node{/*{{{*/
public:
  void merge(segtree_node&, segtree_node&){}
  void split(segtree_node&, segtree_node&){}
};/*}}}*/
template<class node>
class segtree{/*{{{*/
	template<bool b>class param{};
	inline void spltdwn(int idx,param<true>){splt(idx);}
	inline void splt(int idx){/*{{{*/
		idx>>=1;
		if(idx>0)splt(idx);
		tree[idx].split(tree[idx<<1],tree[(idx<<1)|1]);
	}/*}}}*/
	inline void spltdwn(int,param<false>){};
	inline void split(node& a, node& b, node& c, param<true> ){return a.split(b,c);}
	inline void split(node&, node&, node&, param<false>){}
	template<typename t,void (t::*)(t&,t&)> class T{};
	template<typename t> static char test(T<t,&t::split>*){return 0;}
	template<typename t> static long double test(...){return 0;}
	int u,v;
	node query(int root, int left_range, int right_range){/*{{{*/
		if(u<=left_range && right_range<=v)
			return tree[root];
		int mid = (left_range + right_range)>>1,
			l = root<<1,
			r = l|1;
		if(has_split)split(tree[root],tree[l],tree[r],param<has_split>());
		node res;
		if(u>=mid)res=query(r,mid,right_range);
		else if(v<=mid)res=query(l,left_range,mid);
		else{
			node n1 = query(l,left_range,mid),
				 n2 = query(r,mid,right_range);
			res.merge(n1,n2);
		}
                if(has_split) tree[root].merge(tree[l],tree[r]);
		return res;
	}/*}}}*/
 	template<void(*fn)(node&)>
	void local_update(int root, int left_range,int right_range){/*{{{*/
		if(u<=left_range && right_range<=v){
			return fn(tree[root]);
		}
		int mid = (left_range + right_range)>>1,
			l = root<<1,
			r = l|1;
		if(has_split)split(tree[root],tree[l],tree[r],param<has_split>());
		if(v>mid)local_update<fn>(r,mid,right_range);
		if(u<mid)local_update<fn>(l,left_range,mid);
		tree[root].merge(tree[l],tree[r]);
	}/*}}}*/
	void mrgup(int idx){/*{{{*/
		idx>>=1;
		while(idx>0)
			tree[idx].merge(tree[idx<<1],tree[(idx<<1)|1]),
			idx>>=1;
	}/*}}}*/
public:
	static bool const has_split = (sizeof(test<node>(0))==sizeof(char));
	int N;
	int leftmost_leaf, rightmost_leaf;
	node* tree;
	node identity;
	~segtree(){
		delete tree;
	}
	void init(int n, const node a[], const node& identity){/*{{{*/
		this->identity = identity;
		N=0;
		while((1<<N)<n)N++;
		leftmost_leaf = 1<<N;
		rightmost_leaf = leftmost_leaf<<1;
		tree = new node[rightmost_leaf];
		for(int i=0;i<n;i++)
			tree[i+leftmost_leaf] = a[i];
		for(int i=n+leftmost_leaf;i<rightmost_leaf;i++)
			tree[i]=identity;
		for(int i=leftmost_leaf-1;i;i--)
			tree[i].merge(tree[i<<1],tree[(i<<1)|1]);
	}/*}}}*/
	node query(int u, int v){//[u,v]/*{{{*/
		this->u=u+leftmost_leaf;
		this->v=v+leftmost_leaf+1;
		return query(1,leftmost_leaf,rightmost_leaf);
	}/*}}}*/
	node query(int u){//faster version of query(u,u)/*{{{*/
		//indexing starts from 0
		u+=leftmost_leaf;
		spltdwn(u,param<has_split>());
		return tree[u];
	}/*}}}*/
	template<void(*fn)(node&)>
	void update(int u, int v){/*{{{*/
		//0-indexed
		this->u=u+leftmost_leaf;
		this->v=v+leftmost_leaf+1;
		return local_update<fn>(1,leftmost_leaf,rightmost_leaf);
	}/*}}}*/
	template<void(*fn)(node&)>
	void update(int u){//faster version of update(u,u)/*{{{*/
		//indexing starts from 0
		u+=leftmost_leaf;
		spltdwn(u,param<has_split>());
		fn(tree[u]);
		mrgup(u);
	}/*}}}*/
	void split_down(int leaf_idx){/*{{{*/
		spltdwn(leaf_idx+leftmost_leaf,param<has_split>());
	}/*}}}*/
	void merge_up(int leaf_idx){/*{{{*/
		mrgup(leaf_idx+leftmost_leaf);
	}/*}}}*/
	bool is_leaf(int tree_idx){return tree_idx>=leftmost_leaf;}
	int binary_search(node k){/*{{{*/
	//search the last place i, such that merge( everyting to the left of i(including i) ) compares less than k
        int root = 1;
        node n=identity;
		//identity satisfies merge(identity,y) = merge(y,identity) = y for all y.
		assert(!(k<identity));
        while(!is_leaf(root)){
                int left_child = root<<1,
					right_child = left_child|1;
                if(has_split)
					split(tree[root],tree[left_child],tree[right_child],param<has_split>());
                node m;
                m.merge(n,tree[left_child]);
                if(m<k){//go to right side
                        n=m;
                        root=right_child;
                }else root=left_child;
        }
        node m;
        m.merge(n,tree[root]);
		mrgup(root);
        if(m<k)return root-leftmost_leaf;
        else return root-1-leftmost_leaf;
	}/*}}}*/
};/*}}}*/

suffix_array.cpp

template<bool LCP_NEEDED=0>
class SuffixArray {
    typedef const int ci;
    typedef const unsigned int cui;
    typedef unsigned int ui;
    inline bool leq(cui a1, cui a2, cui b1, cui b2) {
        return (a1==b1? a2<=b2: a1<b1);
    }
    inline bool leq(cui a1, cui a2, cui a3, cui b1, cui b2, cui b3) {
        return (a1==b1? leq(a2,a3,b2,b3): a1<b1); 
    }
    void RadixPass(ui *a, ui *b, ui *r, cui n, cui K) {
        ui* cnt=new ui[K+1];
        memset(cnt,0,(K+1)*sizeof(ui));
        for (ui i=n;i--;) cnt[r[a[i]]]++;
        for (ui i=1;i<=K;i++) cnt[i]+=cnt[i-1];
        for (ui i=n;i--;) b[--cnt[r[a[i]]]]=a[i];
        delete[] cnt;
    }
    void GetSuffixArray(ui *s, ui *SA, cui n, cui K, ui* srtd) {
        if (n<=8) {
            bool c[8][8];
            for (ui i=n;i--;) for (ui j=i+1;j<n;j++) {
                if (s[i]==s[j]) c[i][j]=(j+1<n && c[i+1][j+1]);
                else c[i][j]=(s[i]<s[j]);
                c[j][i]=!c[i][j];
            }
            for (int i=n;i--;) SA[i]=i;
            for (ui i=0;i<n;i++) for (ui j=i+1;j<n;j++) if (c[SA[j]][SA[i]]) swap(SA[i],SA[j]);
            return;
        }
        cui n0=(n+2)/3,n1=(n+1)/3,n2=n/3,n02=n0+n2;
        ui *s12=new ui[n02+3];
        s12[n02]=s12[n02+1]=s12[n02+2]=0; 
        ui *SA12=new ui[n02+3];
        SA12[n02]=SA12[n02+1]=SA12[n02+2]=0;
        ui *s0=new ui[n0];
        ui *SA0=new ui[n0]; {
            ui j=0;
            if(n0!=n1)SA12[j++]=n;
            if((n-1)%3)SA12[j++]=n-1;
            if((n-2)%3)SA12[j++]=n-2;
            for(ui i=0;i<n;i++)
                if(srtd[i]>1 and srtd[i]%3!=2) SA12[j++]=srtd[i]-2;
        }
        //SA12 is indices sorted by s[i+2]
        RadixPass(SA12,s12,s+1,n02,K);  
        RadixPass(s12,SA12,s,n02,K);
        ui name=0,c0=-1,c1=-1,c2=-1;
        for (ui i=0,j=0;i<n02;i++) {
            if (s[SA12[i]]!=c0 || s[SA12[i]+1]!=c1 || s[SA12[i]+2]!=c2)
                name++,c0=s[SA12[i]],c1=s[SA12[i]+1],c2=s[SA12[i]+2];
            if (SA12[i]%3==1)
                s12[SA[j++]=SA12[i]/3]=name;
            else 
                s12[SA[j++]=SA12[i]/3+n0]=name;
        }
        if (name<n02) {
            GetSuffixArray(s12,SA12,n02,name,SA);
            for (ui i=n02;i--;) s12[SA12[i]]=i+1;
        }
        else
            for (ui i=n02;i--;) SA12[s12[i]-1]=i;
        for (ui i=0,j=0;i<n02;i++) if (SA12[i]<n0) s0[j++]=3*SA12[i];
        RadixPass(s0,SA0,s,n0,K);
        ui p=0,t=n0-n1,k=0,i,j;
        i=(SA12[t]<n0?SA12[t]*3+1:(SA12[t]-n0)*3+2);
        j=SA0[p];
        for (;k<n;k++) {
            if (SA12[t]<n0?leq(s[i],s12[SA12[t]+n0],s[j],s12[j/3]):
                    leq(s[i],s[i+1],s12[SA12[t]-n0+1],s[j],s[j+1],s12[j/3+n0])) {
                SA[k]=i;
                if ((++t)==n02) for (k++;p<n0;p++,k++) SA[k]=SA0[p];
                else i=(SA12[t]<n0?SA12[t]*3+1:(SA12[t]-n0)*3+2);
            }
            else { 
                SA[k]=j;
                if ((++p)==n0) for (k++;t<n02;t++,k++) SA[k]=(SA12[t]<n0?SA12[t]*3+1:(SA12[t]-n0)*3+2); 
                else j=SA0[p];
            }
        }
        delete[] s12;
        delete[] SA12;
        delete[] s0;
        delete[] SA0;
    }
    ui* SA, *Rank, *D, n;
    void PrepareD(const char *s) {
        D = new ui[n+2];
        for (ui k=0,i=0;i<n;i++)
            if (Rank[i]==n-1)
                D[n-1]=k=0;
            else {
                if (k>0) k--;
                ui t=SA[Rank[i]+1];
                for (;i+k<n && i+k<n && s[i+k]==s[t+k];k++);
                D[Rank[i]]=k;
            }
    }
    public:
    SuffixArray(cui n, const char *s) {
        this->n = n;
        SA = new ui[n+2];
        Rank = new ui[n+2];
        ui *A=new ui[n+3];
        for (ui i=0;i<n;i++) A[i]=s[i];
        A[n]=A[n+1]=A[n+2]=0;
        ui* cnt=new ui[256];
        memset(cnt,0,256*sizeof(ui));
        for (ui i=n;i--;) cnt[A[i]]++;
        for (ui i=1;i<256;i++) cnt[i]+=cnt[i-1];
        for (ui i=n;i--;) Rank[--cnt[A[i]]]=i;
        delete[] cnt;
        GetSuffixArray(A,SA,n,256, Rank);
        for (ui i=n;i--;) Rank[SA[i]]=i;
        if(LCP_NEEDED) PrepareD(s);
    }
    ui get_LCP(int i) { // LCP of SA[i], SA[i+1]
        return D[i];
    }
    ui operator()(cui i) { // SA
        return SA[i];
    }
    ui operator[](cui i) { //rank of ith guy
        return Rank[i];
    }
};