    /**
     * Author: Sergey Kopeliovich (Burunduk30@gmail.com)
     * (translated from C++ by Pavel Mavrin)
     */

    class SuffixTree {

        private static final int ALPHA_SIZE = 26;

        int s[], n, vn, root, suf[], dep[], size[];
        int[] edge_st, edge_len, edge_next;

        int newV(int d, int end) {
            assert (vn < suf.length);
            dep[vn] = d;
            size[vn] = end;
            return vn++;
        }

        int split(int v, int c, int i) {
            int a = v * ALPHA_SIZE + c;
            int u = newV(dep[v] + i, 0);
            int b = u * ALPHA_SIZE + s[edge_st[a] + i];
            edge_st[b] = edge_st[a] + i;
            edge_len[b] = edge_len[a] - i;
            edge_next[b] = edge_next[a];
            edge_len[a] = i;
            edge_next[a] = u;
            return u;
        }

        void create(int u, int c, int i) {
            int x = u * ALPHA_SIZE + c;
            edge_st[x] = i;
            edge_len[x] = n - i;
            edge_next[x] = newV(dep[u] + (n - i), 1);
        }

        public SuffixTree(int[] s) {
            this.s = s;
            this.n = s.length;
            int len = 1 + n * 2;
            suf = new int[len];
            dep = new int[len];
            size = new int[len];

            // compressed 2d arrays. e[i][j] -> e[i * ALPHA_SIZE + j]
            edge_st = new int[len * ALPHA_SIZE]; // edge start
            edge_len = new int[len * ALPHA_SIZE]; // edge length
            edge_next = new int[len * ALPHA_SIZE]; // edge destination

            vn = 0;
            root = newV(0, 0);

            int v = 0, cur_c = 0, cur_i = 0;
            for (int i = 0; i < n; i++) {
                if (cur_i > 0 && cur_i == edge_len[v * ALPHA_SIZE + cur_c]) {
                    v = edge_next[v * ALPHA_SIZE + cur_c];
                    cur_i = 0;
                }
                int c = s[i], last = -1;
                int t = edge_st[v * ALPHA_SIZE + cur_c];
                while (cur_i > 0 && s[t + cur_i] != c) {
                    int w = suf[v], u = split(v, cur_c, cur_i);
                    create(u, c, i);
                    if (last != -1)
                        suf[last] = u;
                    last = u;
                    if (v == 0) {
                        t++;
                        cur_i--;
                    }
                    int a;
                    while (cur_i > 0 && edge_len[a = w * ALPHA_SIZE + (cur_c = s[t])] <= cur_i) {
                        cur_i -= edge_len[a];
                        w = edge_next[a];
                        t += edge_len[a];
                    }
                    v = w;
                    if (cur_i == 0)
                        suf[last] = v;
                }
                if (cur_i > 0) {
                    cur_i++;
                } else {
                    cur_i = 1;
                    cur_c = c;
                    while (edge_len[v * ALPHA_SIZE + c] < cur_i) {
                        create(v, c, i);
                        if (v > 0)
                            v = suf[v];
                        else
                            cur_i = 0;
                    }
                }
            }
        }
    }