#include "../data-structure/RangeMinimumQuery.cc"

#include <cstring>

#include <vector>

#include <algorithm>

#define pushS(x) sa[--cur[(int)s[x]]] = x

#define pushL(x) sa[cur[(int)s[x]]++] = x

class SuffixArray {

std::vector<int> sa;

std::vector<int> rank;

std::vector<int> lcp;

SchieberVishkinRMQ<int> lcpRMQ;

template <class T> void build(const T *s, int n);

template <class T> void build(const T *s, int n, int m);

int size() const {

return sa.size() - 1;

}

int computeLCP(int i, int j) const {

if (i == j) return size() - i;

int x = rank[i], y = rank[j];

if (x > y) std::swap(x, y);

return lcp[lcpRMQ.query(x + 1, y)];

}

using SLTypes = std::vector<bool>;

int *buffer, *freq, *cur;

int len;

void buildRankTable();

void buildLCPArrayRMQ();

template <class T> void computeLCPArray(const T *s);

template <class T> void countFrequence(const T *s, int n, int m);

template <class T> void induce(const T *s, int *sa, int m, const SLTypes &t);

template <class T> void sa_is(const T *s, int *sa, int n, int m);

};

template <class T>

void SuffixArray::build(const T *s, int n) {

this->len = n;

int m = *std::max_element(s, s + n) + 1;

build(s, n, m);

buildRankTable();

computeLCPArray(s);

buildLCPArrayRMQ();

}

template <class T>

void SuffixArray::build(const T *s, int n, int m) {

sa.resize(n + 1);

if (n == 0) sa[0] = 0;

else {

// memory usage: sa + buffer + types

// = 4 * (n + max(m * 2, n)) + 2 * n / 8 + O(1) bytes

std::vector<int> buffer((std::max(m, (n + 1) / 2) + 1) * 2);

this->buffer = &buffer[0];

sa_is<T>(s, &sa[0], n + 1, m);

}

}

void SuffixArray::buildRankTable() {

int n = size() + 1;

rank.resize(n);

for (int i = 0; i < n; ++i) rank[sa[i]] = i;

}

void SuffixArray::buildLCPArrayRMQ() {

lcpRMQ.build(&lcp[0], size() + 1);

}

template <class T>

void SuffixArray::computeLCPArray(const T *s) {

const int n = size() + 1;

lcp.resize(n);

for (int i = 0, h = lcp[0] = 0; i < n; ++i) {

int j = sa[rank[i] - 1];

while (i + h < n && j + h < n && s[i + h] == s[j + h]) ++h;

if (lcp[rank[i]] = h) --h;

}

}

template <class T>

void SuffixArray::countFrequence(const T *s, int n, int m) {

memset(freq, 0, sizeof(int) * m);

for (int i = 0; i < n; ++i) ++freq[(int)s[i]];

for (int i = 1; i < m; ++i) freq[i] += freq[i - 1];

memcpy(cur, freq, sizeof(int) * m);

}

template <class T>

void SuffixArray::induce(const T *s, int *sa, int m, const SLTypes &t) {

const int n = t.size();

memcpy(cur + 1, freq, sizeof(int) * (m - 1));

for (int i = 0; i < n; ++i) {

int p = sa[i] - 1;

if (p >= 0 && t[p]) pushL(p);

}

memcpy(cur, freq, sizeof(int) * m);

for (int i = n - 1; i > 0; --i) {

int p = sa[i] - 1;

if (p >= 0 && !t[p]) pushS(p);

}

}

template <class T>

void SuffixArray::sa_is(const T *s, int *sa, int n, int m) {

SLTypes t(n); memset(sa, 0, sizeof(int) * n);

for (int i = n - 2; ~i; --i) {

t[i] = (s[i] == s[i + 1]) ? t[i + 1] : s[i] > s[i + 1];

}

freq = buffer, cur = buffer + m;

countFrequence(s, n, m);

for (int i = 1; i < n; ++i) if (t[i - 1] > t[i]) pushS(i);

induce(s, sa, m, t);

int n1 = 0, order = 0;

for (int i = 0, p; i < n; ++i) {

if ((p = sa[i]) && t[p - 1] > t[p]) sa[n1++] = p;

}

int *s1 = sa + n1;

memset(s1, -1, sizeof(int) * (n - n1));

s1[(sa[0] - 1) / 2] = order++;

for (int i = 1; i < n1; ++i) {

bool diff = true;

for (int x = sa[i - 1], y = sa[i]; ; ++x, ++y) {

if (s[x] != s[y] || t[x] != t[y]) break;

else if (t[x] > t[x + 1] && t[y] > t[y + 1]) {

diff = (s[x + 1] != s[y + 1]); break;

}

}

s1[(sa[i] - 1) / 2] = (order += diff) - 1;

}

for (int i = 0, x = 0; i < n - n1; ++i) {

if (~s1[i]) s1[x++] = s1[i];

}

if (order != n1) {

sa_is<int>(s1, sa, n1, order);

for (int i = 0; i < n1; ++i) s1[sa[i]] = i;

}

for (int i = 1, j = 0; i < n; ++i) {

if (t[i - 1] > t[i]) sa[s1[j++]] = -i;

}

memset(s1, 0, sizeof(int) * (n - n1));

freq = buffer, cur = buffer + m;

countFrequence(s, n, m);

for (int i = n1 - 1; ~i; --i) pushS(-sa[i]);

induce(s, sa, m, t);

}