代码

//Generated at 2021-04-07 20:12:53 UTC+8
//Created by Alphagocc
#ifndef TYPE_HPP
#define TYPE_HPP
#include <type_traits>
#ifndef __cpp_lib_void_t
namespace std
{
template <typename...> using void_t = void;
}
#endif
template <typename T, typename _ = void> struct is_container : std::false_type
{};
template <typename... Ts> struct is_container_helper
{};
template <typename T>
struct is_container<T,
typename std::conditional<false,
is_container_helper<decltype(std::declval<T>().size()),
decltype(std::declval<T>().begin()),
decltype(std::declval<T>().end()),
decltype(std::declval<T>().cbegin()),
decltype(std::declval<T>().cend())>,
void>::type> : public std::true_type
{};
#endif
#include <bits/stdc++.h>
#define FORCE_INLINE __inline__ __attribute__((always_inline))
class IO
{
static const int bufSize = 1 << 18;

char inBuf[bufSize], outBuf[bufSize];
char *ip1 = inBuf, *ip2 = inBuf;
int goodReadBit = 1, op1 = -1, op2 = bufSize - 1;
FORCE_INLINE int gc()
{
return ip1 == ip2
&& (ip2 = (ip1 = inBuf) + fread(inBuf, 1, bufSize, stdin),
ip1 == ip2)
? EOF
: *ip1++;
}
template <typename T> FORCE_INLINE void __RI(T &x)
{
int ch = gc(), neg = 1;
x = 0;
for (; !(isdigit(ch) || ch == '-'); ch = gc()) {}
if (ch == EOF) {
goodReadBit = 0;
return;
}
if (ch == '-') neg = -1, ch = gc();
for (; isdigit(ch); ch = gc()) x = x * 10 + (ch - 48) * neg;
}
template <typename T> FORCE_INLINE void __RC(T &x)
{
int ch;
while (isspace(ch = gc())) {}
if (ch == EOF) {
goodReadBit = 0;
return;
}
x = ch;
}
FORCE_INLINE void __RS(std::string &x)
{
char ch;
x.clear();
for (ch = gc(); isspace(ch); ch = gc()) {}
if (ch == EOF) {
goodReadBit = 0;
return;
}
for (; !isspace(ch) && ch != EOF; ch = gc()) x.push_back(ch);
}

public:
FORCE_INLINE IO &R(char &x) { return __RC(x), (*this); }
FORCE_INLINE IO &R(unsigned char &x) { return __RC(x), (*this); }
FORCE_INLINE IO &R(std::string &x) { return __RS(x), (*this); }
template <typename T1, typename T2> FORCE_INLINE IO &R(std::pair<T1, T2> &x)
{
return R(x.first), R(x.second), (*this);
}
template <typename T, typename... Args> FORCE_INLINE IO &RA(T *a, int n)
{
for (int i = 0; i < n; ++i) R(a[i]);
return (*this);
}
template <typename T, typename... Args>
FORCE_INLINE IO &R(T &x, Args &...args)
{
return R(x), R(args...), (*this);
}
template <typename T, typename... Args>
FORCE_INLINE IO &RA(T *a, int n, Args... args)
{
for (int i = 0; i < n; ++i) RA(a[i], args...);
return (*this);
}
template <typename T>
FORCE_INLINE typename std::enable_if<std::is_integral<T>::value, IO>::type &
R(T &x)
{
return __RI(x), (*this);
}
template <typename T>
FORCE_INLINE typename std::enable_if<is_container<T>::value, IO>::type &R(
T &x)
{
for (auto &i : x) R(i);
return (*this);
}
template <typename T>
FORCE_INLINE typename std::enable_if<
std::is_void<std::void_t<decltype(std::declval<T>().read())>>::value,
IO>::type &
R(T &x)
{
return x.read(), (*this);
}

private:
char space;
FORCE_INLINE void pc(const char &x)
{
if (op1 == op2) flush();
outBuf[++op1] = x;
}
template <typename T> FORCE_INLINE void __WI(T x)
{
static char buf[64];
static int len = -1;
if (x >= 0) {
do {
buf[++len] = x % 10 + 48, x /= 10;
} while (x);
} else {
pc('-');
do {
buf[++len] = -(x % 10) + 48, x /= 10;
} while (x);
}
while (len >= 0) { pc(buf[len]), --len; }
}

public:
FORCE_INLINE void flush() { fwrite(outBuf, 1, op1 + 1, stdout), op1 = -1; }
FORCE_INLINE IO &W(const char &x) { return pc(x), (*this); }
FORCE_INLINE IO &W(const char *x)
{
while (*x != '\0') pc(*(x++));
return (*this);
}
FORCE_INLINE IO &W(const std::string &x) { return W(x.c_str()), (*this); }
template <typename T1, typename T2>
FORCE_INLINE IO &W(const std::pair<T1, T2> &x)
{
WS(x.first);
W(x.second);
return (*this);
}
FORCE_INLINE IO &WL() { return W('\n'), (*this); }
template <typename T> FORCE_INLINE IO &WL(const T &x)
{
return W(x), W('\n'), (*this);
}
FORCE_INLINE IO &WS() { return W(space), (*this); }
template <typename T> FORCE_INLINE IO &WS(const T &x)
{
return W(x), W(space), (*this);
}
template <typename T> FORCE_INLINE IO &WA(T *a, int n)
{
for (int i = 0; i < n; i++) WS(a[i]);
WL();
return (*this);
}
template <typename T, typename... Args>
FORCE_INLINE IO &W(const T &x, const Args &...args)
{
W(x), W(space), W(args...);
return (*this);
}
template <typename T, typename... Args>
FORCE_INLINE IO &WS(const T &x, const Args &...args)
{
return W(x), W(space), W(args...), W(space), (*this);
}
template <typename... Args> FORCE_INLINE IO &WL(const Args &...args)
{
return W(args...), W('\n'), (*this);
}
template <typename T, typename... Args>
FORCE_INLINE IO &WA(T *a, int n, Args... args)
{
for (int i = 0; i < n; i++) WA(a[i], args...);
return (*this);
}
template <typename T>
FORCE_INLINE typename std::enable_if<std::is_integral<T>::value, IO>::type &
W(const T &x)
{
return __WI(x), (*this);
}
template <typename T>
FORCE_INLINE typename std::enable_if<is_container<T>::value, IO>::type &W(
const T &x)
{

for (auto &i : x) WS(i);
WL();
return (*this);
}
template <typename T>
FORCE_INLINE typename std::enable_if<
std::is_void<std::void_t<decltype(std::declval<T>().write())>>::value,
IO>::type &
W(const T &x)
{
return x.write(), (*this);
}
template <typename T> FORCE_INLINE IO &operator>>(T &x)
{
R(x);
return (*this);
}
template <typename T> FORCE_INLINE IO &operator<<(const T &x)
{
W(x);
return (*this);
}
IO() { space = ' '; }
~IO() { flush(); }
} io;
#undef FORCE_INLINE

namespace DIVSUFSORTSA
{
/*
 * Copyright (c) 2003-2008 Yuta Mori All Rights Reserved.
 *
 * Permission is hereby granted, free of charge, to any person
 * obtaining a copy of this software and associated documentation
 * files (the "Software"), to deal in the Software without
 * restriction, including without limitation the rights to use,
 * copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following
 * conditions:
 *
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
 * OTHER DEALINGS IN THE SOFTWARE.
 */

#ifndef SAUCHAR_T
#define SAUCHAR_T
typedef uint8_t sauchar_t;
#endif
#ifndef SAINT_T
#define SAINT_T
typedef int32_t saint_t;
#endif
#ifndef SAIDX_T
#define SAIDX_T
typedef int32_t saidx_t;
#endif
#ifndef PRIdSAINT_T
#define PRIdSAINT_T PRId32
#endif
#ifndef PRIdSAIDX_T
#define PRIdSAIDX_T PRId32
#endif

#if !defined(UINT8_MAX)
#define UINT8_MAX (255)
#endif
#if defined(ALPHABET_SIZE) && (ALPHABET_SIZE < 1)
#undef ALPHABET_SIZE
#endif
#if !defined(ALPHABET_SIZE)
#define ALPHABET_SIZE (UINT8_MAX + 1)
#endif

#define BUCKET_A_SIZE (ALPHABET_SIZE)
#define BUCKET_B_SIZE (ALPHABET_SIZE * ALPHABET_SIZE)

#if defined(SS_INSERTIONSORT_THRESHOLD)
#if SS_INSERTIONSORT_THRESHOLD < 1
#undef SS_INSERTIONSORT_THRESHOLD
#define SS_INSERTIONSORT_THRESHOLD (1)
#endif
#else
#define SS_INSERTIONSORT_THRESHOLD (8)
#endif
#if defined(SS_BLOCKSIZE)
#if SS_BLOCKSIZE < 0
#undef SS_BLOCKSIZE
#define SS_BLOCKSIZE (0)
#elif 32768 <= SS_BLOCKSIZE
#undef SS_BLOCKSIZE
#define SS_BLOCKSIZE (32767)
#endif
#else
#define SS_BLOCKSIZE (1024)
#endif

#if SS_BLOCKSIZE == 0
#if defined(BUILD_DIVSUFSORT64)
#define SS_MISORT_STACKSIZE (96)
#else
#define SS_MISORT_STACKSIZE (64)
#endif
#elif SS_BLOCKSIZE <= 4096
#define SS_MISORT_STACKSIZE (16)
#else
#define SS_MISORT_STACKSIZE (24)
#endif
#if defined(BUILD_DIVSUFSORT64)
#define SS_SMERGE_STACKSIZE (64)
#else
#define SS_SMERGE_STACKSIZE (32)
#endif
#define TR_INSERTIONSORT_THRESHOLD (8)
#if defined(BUILD_DIVSUFSORT64)
#define TR_STACKSIZE (96)
#else
#define TR_STACKSIZE (64)
#endif

#ifndef SWAP
#define SWAP(_a, _b)   \
do {   \
t = (_a);  \
(_a) = (_b);   \
(_b) = t;  \
} while (0)
#endif
#ifndef MIN
#define MIN(_a, _b) (((_a) < (_b)) ? (_a) : (_b))
#endif
#ifndef MAX
#define MAX(_a, _b) (((_a) > (_b)) ? (_a) : (_b))
#endif
#define STACK_PUSH(_a, _b, _c, _d) \
do {   \
assert(ssize < STACK_SIZE);\
stack[ssize].a = (_a), stack[ssize].b = (_b), stack[ssize].c = (_c),   \
stack[ssize++].d = (_d);   \
} while (0)
#define STACK_PUSH5(_a, _b, _c, _d, _e)\
do {   \
assert(ssize < STACK_SIZE);\
stack[ssize].a = (_a), stack[ssize].b = (_b), stack[ssize].c = (_c),   \
stack[ssize].d = (_d), stack[ssize++].e = (_e);\
} while (0)
#define STACK_POP(_a, _b, _c, _d)  \
do {   \
assert(0 <= ssize);\
if (ssize == 0) { return; }\
(_a) = stack[--ssize].a, (_b) = stack[ssize].b, (_c) = stack[ssize].c, \
(_d) = stack[ssize].d; \
} while (0)
#define STACK_POP5(_a, _b, _c, _d, _e) \
do {   \
assert(0 <= ssize);\
if (ssize == 0) { return; }\
(_a) = stack[--ssize].a, (_b) = stack[ssize].b, (_c) = stack[ssize].c, \
(_d) = stack[ssize].d, (_e) = stack[ssize].e;  \
} while (0)

#define BUCKET_A(_c0) bucket_A[(_c0)]
#if ALPHABET_SIZE == 256
#define BUCKET_B(_c0, _c1) (bucket_B[((_c1) << 8) | (_c0)])
#define BUCKET_BSTAR(_c0, _c1) (bucket_B[((_c0) << 8) | (_c1)])
#else
#define BUCKET_B(_c0, _c1) (bucket_B[(_c1)*ALPHABET_SIZE + (_c0)])
#define BUCKET_BSTAR(_c0, _c1) (bucket_B[(_c0)*ALPHABET_SIZE + (_c1)])
#endif
void sssort(const sauchar_t *Td, const saidx_t *PA, saidx_t *first,
saidx_t *last, saidx_t *buf, saidx_t bufsize, saidx_t depth, saidx_t n,
saint_t lastsuffix);
void trsort(saidx_t *ISA, saidx_t *SA, saidx_t n, saidx_t depth);

static saidx_t sort_typeBstar(const sauchar_t *T, saidx_t *SA,
saidx_t *bucket_A, saidx_t *bucket_B, saidx_t n)
{
saidx_t *PAb, *ISAb, *buf;
saidx_t i, j, k, t, m, bufsize;
saint_t c0, c1;

for (i = 0; i < BUCKET_A_SIZE; ++i) { bucket_A[i] = 0; }
for (i = 0; i < BUCKET_B_SIZE; ++i) { bucket_B[i] = 0; }
for (i = n - 1, m = n, c0 = T[n - 1]; 0 <= i;) {

do {
++BUCKET_A(c1 = c0);
} while ((0 <= --i) && ((c0 = T[i]) >= c1));
if (0 <= i) {

++BUCKET_BSTAR(c0, c1);
SA[--m] = i;

for (--i, c1 = c0; (0 <= i) && ((c0 = T[i]) <= c1); --i, c1 = c0) {
++BUCKET_B(c0, c1);
}
}
}
m = n - m;
for (c0 = 0, i = 0, j = 0; c0 < ALPHABET_SIZE; ++c0) {
t = i + BUCKET_A(c0);
BUCKET_A(c0) = i + j;
i = t + BUCKET_B(c0, c0);
for (c1 = c0 + 1; c1 < ALPHABET_SIZE; ++c1) {
j += BUCKET_BSTAR(c0, c1);
BUCKET_BSTAR(c0, c1) = j;
i += BUCKET_B(c0, c1);
}
}

if (0 < m) {
PAb = SA + n - m;
ISAb = SA + m;
for (i = m - 2; 0 <= i; --i) {
t = PAb[i], c0 = T[t], c1 = T[t + 1];
SA[--BUCKET_BSTAR(c0, c1)] = i;
}
t = PAb[m - 1], c0 = T[t], c1 = T[t + 1];
SA[--BUCKET_BSTAR(c0, c1)] = m - 1;

buf = SA + m, bufsize = n - (2 * m);
for (c0 = ALPHABET_SIZE - 2, j = m; 0 < j; --c0) {
for (c1 = ALPHABET_SIZE - 1; c0 < c1; j = i, --c1) {
i = BUCKET_BSTAR(c0, c1);
if (1 < (j - i)) {
sssort(T, PAb, SA + i, SA + j, buf, bufsize, 2, n,
*(SA + i) == (m - 1));
}
}
}

for (i = m - 1; 0 <= i; --i) {
if (0 <= SA[i]) {
j = i;
do {
ISAb[SA[i]] = i;
} while ((0 <= --i) && (0 <= SA[i]));
SA[i + 1] = i - j;
if (i <= 0) { break; }
}
j = i;
do {
ISAb[SA[i] = ~SA[i]] = j;
} while (SA[--i] < 0);
ISAb[SA[i]] = j;
}

/* Construct the inverse suffix array of type B* suffixes using trsort.
 */
trsort(ISAb, SA, m, 1);

for (i = n - 1, j = m, c0 = T[n - 1]; 0 <= i;) {
for (--i, c1 = c0; (0 <= i) && ((c0 = T[i]) >= c1); --i, c1 = c0) {}
if (0 <= i) {
t = i;
for (--i, c1 = c0; (0 <= i) && ((c0 = T[i]) <= c1);
 --i, c1 = c0) {}
SA[ISAb[--j]] = ((t == 0) || (1 < (t - i))) ? t : ~t;
}
}

BUCKET_B(ALPHABET_SIZE - 1, ALPHABET_SIZE - 1) = n;
for (c0 = ALPHABET_SIZE - 2, k = m - 1; 0 <= c0; --c0) {
i = BUCKET_A(c0 + 1) - 1;
for (c1 = ALPHABET_SIZE - 1; c0 < c1; --c1) {
t = i - BUCKET_B(c0, c1);
BUCKET_B(c0, c1) = i;

for (i = t, j = BUCKET_BSTAR(c0, c1); j <= k; --i, --k) {
SA[i] = SA[k];
}
}
BUCKET_BSTAR(c0, c0 + 1) = i - BUCKET_B(c0, c0) + 1;
BUCKET_B(c0, c0) = i;
}
}

return m;
}

static void construct_SA(const sauchar_t *T, saidx_t *SA, saidx_t *bucket_A,
saidx_t *bucket_B, saidx_t n, saidx_t m)
{
saidx_t *i, *j, *k;
saidx_t s;
saint_t c0, c1, c2;

if (0 < m) {
/* Construct the sorted order of type B suffixes by using
   the sorted order of type B* suffixes. */
for (c1 = ALPHABET_SIZE - 2; 0 <= c1; --c1) {

for (i = SA + BUCKET_BSTAR(c1, c1 + 1),
j = SA + BUCKET_A(c1 + 1) - 1, k = NULL, c2 = -1;
 i <= j; --j) {
if (0 < (s = *j)) {
assert(T[s] == c1);
assert(((s + 1) < n) && (T[s] <= T[s + 1]));
assert(T[s - 1] <= T[s]);
*j = ~s;
c0 = T[--s];
if ((0 < s) && (T[s - 1] > c0)) { s = ~s; }
if (c0 != c2) {
if (0 <= c2) { BUCKET_B(c2, c1) = k - SA; }
k = SA + BUCKET_B(c2 = c0, c1);
}
assert(k < j);
*k-- = s;
} else {
assert(((s == 0) && (T[s] == c1)) || (s < 0));
*j = ~s;
}
}
}
}
k = SA + BUCKET_A(c2 = T[n - 1]);
*k++ = (T[n - 2] < c2) ? ~(n - 1) : (n - 1);
for (i = SA, j = SA + n; i < j; ++i) {
if (0 < (s = *i)) {
assert(T[s - 1] >= T[s]);
c0 = T[--s];
if ((s == 0) || (T[s - 1] < c0)) { s = ~s; }
if (c0 != c2) {
BUCKET_A(c2) = k - SA;
k = SA + BUCKET_A(c2 = c0);
}
assert(i < k);
*k++ = s;
} else {
assert(s < 0);
*i = ~s;
}
}
}

saint_t divsufsort(const sauchar_t *T, saidx_t *SA, saidx_t n)
{
saidx_t *bucket_A, *bucket_B;
saidx_t m;
saint_t err = 0;

if ((T == NULL) || (SA == NULL) || (n < 0)) {
return -1;
} else if (n == 0) {
return 0;
} else if (n == 1) {
SA[0] = 0;
return 0;
} else if (n == 2) {
m = (T[0] < T[1]);
SA[m ^ 1] = 0, SA[m] = 1;
return 0;
}

bucket_A = (saidx_t *)malloc(BUCKET_A_SIZE * sizeof(saidx_t));
bucket_B = (saidx_t *)malloc(BUCKET_B_SIZE * sizeof(saidx_t));

if ((bucket_A != NULL) && (bucket_B != NULL)) {
m = sort_typeBstar(T, SA, bucket_A, bucket_B, n);
construct_SA(T, SA, bucket_A, bucket_B, n, m);
} else {
err = -2;
}

free(bucket_B);
free(bucket_A);

return err;
}

static const saint_t lg_table[256] = { -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3,
3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5,
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7 };

#if (SS_BLOCKSIZE == 0) || (SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE)
#define INLINE inline
static INLINE saint_t ss_ilg(saidx_t n)
{
#if SS_BLOCKSIZE == 0
#if defined(BUILD_DIVSUFSORT64)
return (n >> 32)
? ((n >> 48) ? ((n >> 56) ? 56 + lg_table[(n >> 56) & 0xff]
  : 48 + lg_table[(n >> 48) & 0xff])
 : ((n >> 40) ? 40 + lg_table[(n >> 40) & 0xff]
  : 32 + lg_table[(n >> 32) & 0xff]))
: ((n & 0xffff0000)
? ((n & 0xff000000) ? 24 + lg_table[(n >> 24) & 0xff]
: 16 + lg_table[(n >> 16) & 0xff])
: ((n & 0x0000ff00) ? 8 + lg_table[(n >> 8) & 0xff]
: 0 + lg_table[(n >> 0) & 0xff]));
#else
return (n & 0xffff0000)
? ((n & 0xff000000) ? 24 + lg_table[(n >> 24) & 0xff]
: 16 + lg_table[(n >> 16) & 0xff])
: ((n & 0x0000ff00) ? 8 + lg_table[(n >> 8) & 0xff]
: 0 + lg_table[(n >> 0) & 0xff]);
#endif
#elif SS_BLOCKSIZE < 256
return lg_table[n];
#else
return (n & 0xff00) ? 8 + lg_table[(n >> 8) & 0xff]
: 0 + lg_table[(n >> 0) & 0xff];
#endif
}

#endif /* (SS_BLOCKSIZE == 0) || (SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE)   \
*/

#if SS_BLOCKSIZE != 0

static const saint_t sqq_table[256] = { 0, 16, 22, 27, 32, 35, 39, 42, 45, 48,
50, 53, 55, 57, 59, 61, 64, 65, 67, 69, 71, 73, 75, 76, 78, 80, 81, 83, 84,
86, 87, 89, 90, 91, 93, 94, 96, 97, 98, 99, 101, 102, 103, 104, 106, 107,
108, 109, 110, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123,
124, 125, 126, 128, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138,
139, 140, 141, 142, 143, 144, 144, 145, 146, 147, 148, 149, 150, 150, 151,
152, 153, 154, 155, 155, 156, 157, 158, 159, 160, 160, 161, 162, 163, 163,
164, 165, 166, 167, 167, 168, 169, 170, 170, 171, 172, 173, 173, 174, 175,
176, 176, 177, 178, 178, 179, 180, 181, 181, 182, 183, 183, 184, 185, 185,
186, 187, 187, 188, 189, 189, 190, 191, 192, 192, 193, 193, 194, 195, 195,
196, 197, 197, 198, 199, 199, 200, 201, 201, 202, 203, 203, 204, 204, 205,
206, 206, 207, 208, 208, 209, 209, 210, 211, 211, 212, 212, 213, 214, 214,
215, 215, 216, 217, 217, 218, 218, 219, 219, 220, 221, 221, 222, 222, 223,
224, 224, 225, 225, 226, 226, 227, 227, 228, 229, 229, 230, 230, 231, 231,
232, 232, 233, 234, 234, 235, 235, 236, 236, 237, 237, 238, 238, 239, 240,
240, 241, 241, 242, 242, 243, 243, 244, 244, 245, 245, 246, 246, 247, 247,
248, 248, 249, 249, 250, 250, 251, 251, 252, 252, 253, 253, 254, 254, 255 };

static INLINE saidx_t ss_isqrt(saidx_t x)
{
saidx_t y, e;

if (x >= (SS_BLOCKSIZE * SS_BLOCKSIZE)) { return SS_BLOCKSIZE; }
e = (x & 0xffff0000) ? ((x & 0xff000000) ? 24 + lg_table[(x >> 24) & 0xff]
 : 16 + lg_table[(x >> 16) & 0xff])
 : ((x & 0x0000ff00) ? 8 + lg_table[(x >> 8) & 0xff]
 : 0 + lg_table[(x >> 0) & 0xff]);

if (e >= 16) {
y = sqq_table[x >> ((e - 6) - (e & 1))] << ((e >> 1) - 7);
if (e >= 24) { y = (y + 1 + x / y) >> 1; }
y = (y + 1 + x / y) >> 1;
} else if (e >= 8) {
y = (sqq_table[x >> ((e - 6) - (e & 1))] >> (7 - (e >> 1))) + 1;
} else {
return sqq_table[x] >> 4;
}

return (x < (y * y)) ? y - 1 : y;
}

#endif

static INLINE saint_t ss_compare(
const sauchar_t *T, const saidx_t *p1, const saidx_t *p2, saidx_t depth)
{
const sauchar_t *U1, *U2, *U1n, *U2n;

for (U1 = T + depth + *p1, U2 = T + depth + *p2, U1n = T + *(p1 + 1) + 2,
U2n = T + *(p2 + 1) + 2;
 (U1 < U1n) && (U2 < U2n) && (*U1 == *U2); ++U1, ++U2) {}

return U1 < U1n ? (U2 < U2n ? *U1 - *U2 : 1) : (U2 < U2n ? -1 : 0);
}

#if (SS_BLOCKSIZE != 1) && (SS_INSERTIONSORT_THRESHOLD != 1)

static void ss_insertionsort(const sauchar_t *T, const saidx_t *PA,
saidx_t *first, saidx_t *last, saidx_t depth)
{
saidx_t *i, *j;
saidx_t t;
saint_t r;

for (i = last - 2; first <= i; --i) {
for (t = *i, j = i + 1;
 0 < (r = ss_compare(T, PA + t, PA + *j, depth));) {
do {
*(j - 1) = *j;
} while ((++j < last) && (*j < 0));
if (last <= j) { break; }
}
if (r == 0) { *j = ~*j; }
*(j - 1) = t;
}
}

#endif

#if (SS_BLOCKSIZE == 0) || (SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE)

static INLINE void ss_fixdown(const sauchar_t *Td, const saidx_t *PA,
saidx_t *SA, saidx_t i, saidx_t size)
{
saidx_t j, k;
saidx_t v;
saint_t c, d, e;

for (v = SA[i], c = Td[PA[v]]; (j = 2 * i + 1) < size;
 SA[i] = SA[k], i = k) {
d = Td[PA[SA[k = j++]]];
if (d < (e = Td[PA[SA[j]]])) {
k = j;
d = e;
}
if (d <= c) { break; }
}
SA[i] = v;
}

static void ss_heapsort(
const sauchar_t *Td, const saidx_t *PA, saidx_t *SA, saidx_t size)
{
saidx_t i, m;
saidx_t t;

m = size;
if ((size % 2) == 0) {
m--;
if (Td[PA[SA[m / 2]]] < Td[PA[SA[m]]]) { SWAP(SA[m], SA[m / 2]); }
}

for (i = m / 2 - 1; 0 <= i; --i) { ss_fixdown(Td, PA, SA, i, m); }
if ((size % 2) == 0) {
SWAP(SA[0], SA[m]);
ss_fixdown(Td, PA, SA, 0, m);
}
for (i = m - 1; 0 < i; --i) {
t = SA[0], SA[0] = SA[i];
ss_fixdown(Td, PA, SA, 0, i);
SA[i] = t;
}
}

static INLINE saidx_t *ss_median3(const sauchar_t *Td, const saidx_t *PA,
saidx_t *v1, saidx_t *v2, saidx_t *v3)
{
saidx_t *t;
if (Td[PA[*v1]] > Td[PA[*v2]]) { SWAP(v1, v2); }
if (Td[PA[*v2]] > Td[PA[*v3]]) {
if (Td[PA[*v1]] > Td[PA[*v3]]) {
return v1;
} else {
return v3;
}
}
return v2;
}

static INLINE saidx_t *ss_median5(const sauchar_t *Td, const saidx_t *PA,
saidx_t *v1, saidx_t *v2, saidx_t *v3, saidx_t *v4, saidx_t *v5)
{
saidx_t *t;
if (Td[PA[*v2]] > Td[PA[*v3]]) { SWAP(v2, v3); }
if (Td[PA[*v4]] > Td[PA[*v5]]) { SWAP(v4, v5); }
if (Td[PA[*v2]] > Td[PA[*v4]]) {
SWAP(v2, v4);
SWAP(v3, v5);
}
if (Td[PA[*v1]] > Td[PA[*v3]]) { SWAP(v1, v3); }
if (Td[PA[*v1]] > Td[PA[*v4]]) {
SWAP(v1, v4);
SWAP(v3, v5);
}
if (Td[PA[*v3]] > Td[PA[*v4]]) { return v4; }
return v3;
}

static INLINE saidx_t *ss_pivot(
const sauchar_t *Td, const saidx_t *PA, saidx_t *first, saidx_t *last)
{
saidx_t *middle;
saidx_t t;

t = last - first;
middle = first + t / 2;

if (t <= 512) {
if (t <= 32) {
return ss_median3(Td, PA, first, middle, last - 1);
} else {
t >>= 2;
return ss_median5(
Td, PA, first, first + t, middle, last - 1 - t, last - 1);
}
}
t >>= 3;
first = ss_median3(Td, PA, first, first + t, first + (t << 1));
middle = ss_median3(Td, PA, middle - t, middle, middle + t);
last = ss_median3(Td, PA, last - 1 - (t << 1), last - 1 - t, last - 1);
return ss_median3(Td, PA, first, middle, last);
}

static INLINE saidx_t *ss_partition(
const saidx_t *PA, saidx_t *first, saidx_t *last, saidx_t depth)
{
saidx_t *a, *b;
saidx_t t;
for (a = first - 1, b = last;;) {
for (; (++a < b) && ((PA[*a] + depth) >= (PA[*a + 1] + 1));) {
*a = ~*a;
}
for (; (a < --b) && ((PA[*b] + depth) < (PA[*b + 1] + 1));) {}
if (b <= a) { break; }
t = ~*b;
*b = *a;
*a = t;
}
if (first < a) { *first = ~*first; }
return a;
}

static void ss_mintrosort(const sauchar_t *T, const saidx_t *PA, saidx_t *first,
saidx_t *last, saidx_t depth)
{
#define STACK_SIZE SS_MISORT_STACKSIZE
struct
{
saidx_t *a, *b, c;
saint_t d;
} stack[STACK_SIZE];
const sauchar_t *Td;
saidx_t *a, *b, *c, *d, *e, *f;
saidx_t s, t;
saint_t ssize;
saint_t limit;
saint_t v, x = 0;

for (ssize = 0, limit = ss_ilg(last - first);;) {

if ((last - first) <= SS_INSERTIONSORT_THRESHOLD) {
#if 1 < SS_INSERTIONSORT_THRESHOLD
if (1 < (last - first)) {
ss_insertionsort(T, PA, first, last, depth);
}
#endif
STACK_POP(first, last, depth, limit);
continue;
}

Td = T + depth;
if (limit-- == 0) { ss_heapsort(Td, PA, first, last - first); }
if (limit < 0) {
for (a = first + 1, v = Td[PA[*first]]; a < last; ++a) {
if ((x = Td[PA[*a]]) != v) {
if (1 < (a - first)) { break; }
v = x;
first = a;
}
}
if (Td[PA[*first] - 1] < v) {
first = ss_partition(PA, first, a, depth);
}
if ((a - first) <= (last - a)) {
if (1 < (a - first)) {
STACK_PUSH(a, last, depth, -1);
last = a, depth += 1, limit = ss_ilg(a - first);
} else {
first = a, limit = -1;
}
} else {
if (1 < (last - a)) {
STACK_PUSH(first, a, depth + 1, ss_ilg(a - first));
first = a, limit = -1;
} else {
last = a, depth += 1, limit = ss_ilg(a - first);
}
}
continue;
}

a = ss_pivot(Td, PA, first, last);
v = Td[PA[*a]];
SWAP(*first, *a);

for (b = first; (++b < last) && ((x = Td[PA[*b]]) == v);) {}
if (((a = b) < last) && (x < v)) {
for (; (++b < last) && ((x = Td[PA[*b]]) <= v);) {
if (x == v) {
SWAP(*b, *a);
++a;
}
}
}
for (c = last; (b < --c) && ((x = Td[PA[*c]]) == v);) {}
if ((b < (d = c)) && (x > v)) {
for (; (b < --c) && ((x = Td[PA[*c]]) >= v);) {
if (x == v) {
SWAP(*c, *d);
--d;
}
}
}
for (; b < c;) {
SWAP(*b, *c);
for (; (++b < c) && ((x = Td[PA[*b]]) <= v);) {
if (x == v) {
SWAP(*b, *a);
++a;
}
}
for (; (b < --c) && ((x = Td[PA[*c]]) >= v);) {
if (x == v) {
SWAP(*c, *d);
--d;
}
}
}

if (a <= d) {
c = b - 1;

if ((s = a - first) > (t = b - a)) { s = t; }
for (e = first, f = b - s; 0 < s; --s, ++e, ++f) { SWAP(*e, *f); }
if ((s = d - c) > (t = last - d - 1)) { s = t; }
for (e = b, f = last - s; 0 < s; --s, ++e, ++f) { SWAP(*e, *f); }

a = first + (b - a), c = last - (d - c);
b = (v <= Td[PA[*a] - 1]) ? a : ss_partition(PA, a, c, depth);

if ((a - first) <= (last - c)) {
if ((last - c) <= (c - b)) {
STACK_PUSH(b, c, depth + 1, ss_ilg(c - b));
STACK_PUSH(c, last, depth, limit);
last = a;
} else if ((a - first) <= (c - b)) {
STACK_PUSH(c, last, depth, limit);
STACK_PUSH(b, c, depth + 1, ss_ilg(c - b));
last = a;
} else {
STACK_PUSH(c, last, depth, limit);
STACK_PUSH(first, a, depth, limit);
first = b, last = c, depth += 1, limit = ss_ilg(c - b);
}
} else {
if ((a - first) <= (c - b)) {
STACK_PUSH(b, c, depth + 1, ss_ilg(c - b));
STACK_PUSH(first, a, depth, limit);
first = c;
} else if ((last - c) <= (c - b)) {
STACK_PUSH(first, a, depth, limit);
STACK_PUSH(b, c, depth + 1, ss_ilg(c - b));
first = c;
} else {
STACK_PUSH(first, a, depth, limit);
STACK_PUSH(c, last, depth, limit);
first = b, last = c, depth += 1, limit = ss_ilg(c - b);
}
}
} else {
limit += 1;
if (Td[PA[*first] - 1] < v) {
first = ss_partition(PA, first, last, depth);
limit = ss_ilg(last - first);
}
depth += 1;
}
}
#undef STACK_SIZE
}

#endif /* (SS_BLOCKSIZE == 0) || (SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE)   \
*/

#if SS_BLOCKSIZE != 0

static INLINE void ss_blockswap(saidx_t *a, saidx_t *b, saidx_t n)
{
saidx_t t;
for (; 0 < n; --n, ++a, ++b) { t = *a, *a = *b, *b = t; }
}

static INLINE void ss_rotate(saidx_t *first, saidx_t *middle, saidx_t *last)
{
saidx_t *a, *b, t;
saidx_t l, r;
l = middle - first, r = last - middle;
for (; (0 < l) && (0 < r);) {
if (l == r) {
ss_blockswap(first, middle, l);
break;
}
if (l < r) {
a = last - 1, b = middle - 1;
t = *a;
do {
*a-- = *b, *b-- = *a;
if (b < first) {
*a = t;
last = a;
if ((r -= l + 1) <= l) { break; }
a -= 1, b = middle - 1;
t = *a;
}
} while (1);
} else {
a = first, b = middle;
t = *a;
do {
*a++ = *b, *b++ = *a;
if (last <= b) {
*a = t;
first = a + 1;
if ((l -= r + 1) <= r) { break; }
a += 1, b = middle;
t = *a;
}
} while (1);
}
}
}

static void ss_inplacemerge(const sauchar_t *T, const saidx_t *PA,
saidx_t *first, saidx_t *middle, saidx_t *last, saidx_t depth)
{
const saidx_t *p;
saidx_t *a, *b;
saidx_t len, half;
saint_t q, r;
saint_t x;

for (;;) {
if (*(last - 1) < 0) {
x = 1;
p = PA + ~*(last - 1);
} else {
x = 0;
p = PA + *(last - 1);
}
for (a = first, len = middle - first, half = len >> 1, r = -1; 0 < len;
 len = half, half >>= 1) {
b = a + half;
q = ss_compare(T, PA + ((0 <= *b) ? *b : ~*b), p, depth);
if (q < 0) {
a = b + 1;
half -= (len & 1) ^ 1;
} else {
r = q;
}
}
if (a < middle) {
if (r == 0) { *a = ~*a; }
ss_rotate(a, middle, last);
last -= middle - a;
middle = a;
if (first == middle) { break; }
}
--last;
if (x != 0) {
while (*--last < 0) {}
}
if (middle == last) { break; }
}
}

static void ss_mergeforward(const sauchar_t *T, const saidx_t *PA,
saidx_t *first, saidx_t *middle, saidx_t *last, saidx_t *buf, saidx_t depth)
{
saidx_t *a, *b, *c, *bufend;
saidx_t t;
saint_t r;

bufend = buf + (middle - first) - 1;
ss_blockswap(buf, first, middle - first);

for (t = *(a = first), b = buf, c = middle;;) {
r = ss_compare(T, PA + *b, PA + *c, depth);
if (r < 0) {
do {
*a++ = *b;
if (bufend <= b) {
*bufend = t;
return;
}
*b++ = *a;
} while (*b < 0);
} else if (r > 0) {
do {
*a++ = *c, *c++ = *a;
if (last <= c) {
while (b < bufend) { *a++ = *b, *b++ = *a; }
*a = *b, *b = t;
return;
}
} while (*c < 0);
} else {
*c = ~*c;
do {
*a++ = *b;
if (bufend <= b) {
*bufend = t;
return;
}
*b++ = *a;
} while (*b < 0);

do {
*a++ = *c, *c++ = *a;
if (last <= c) {
while (b < bufend) { *a++ = *b, *b++ = *a; }
*a = *b, *b = t;
return;
}
} while (*c < 0);
}
}
}

static void ss_mergebackward(const sauchar_t *T, const saidx_t *PA,
saidx_t *first, saidx_t *middle, saidx_t *last, saidx_t *buf, saidx_t depth)
{
const saidx_t *p1, *p2;
saidx_t *a, *b, *c, *bufend;
saidx_t t;
saint_t r;
saint_t x;

bufend = buf + (last - middle) - 1;
ss_blockswap(buf, middle, last - middle);

x = 0;
if (*bufend < 0) {
p1 = PA + ~*bufend;
x |= 1;
} else {
p1 = PA + *bufend;
}
if (*(middle - 1) < 0) {
p2 = PA + ~*(middle - 1);
x |= 2;
} else {
p2 = PA + *(middle - 1);
}
for (t = *(a = last - 1), b = bufend, c = middle - 1;;) {
r = ss_compare(T, p1, p2, depth);
if (0 < r) {
if (x & 1) {
do {
*a-- = *b, *b-- = *a;
} while (*b < 0);
x ^= 1;
}
*a-- = *b;
if (b <= buf) {
*buf = t;
break;
}
*b-- = *a;
if (*b < 0) {
p1 = PA + ~*b;
x |= 1;
} else {
p1 = PA + *b;
}
} else if (r < 0) {
if (x & 2) {
do {
*a-- = *c, *c-- = *a;
} while (*c < 0);
x ^= 2;
}
*a-- = *c, *c-- = *a;
if (c < first) {
while (buf < b) { *a-- = *b, *b-- = *a; }
*a = *b, *b = t;
break;
}
if (*c < 0) {
p2 = PA + ~*c;
x |= 2;
} else {
p2 = PA + *c;
}
} else {
if (x & 1) {
do {
*a-- = *b, *b-- = *a;
} while (*b < 0);
x ^= 1;
}
*a-- = ~*b;
if (b <= buf) {
*buf = t;
break;
}
*b-- = *a;
if (x & 2) {
do {
*a-- = *c, *c-- = *a;
} while (*c < 0);
x ^= 2;
}
*a-- = *c, *c-- = *a;
if (c < first) {
while (buf < b) { *a-- = *b, *b-- = *a; }
*a = *b, *b = t;
break;
}
if (*b < 0) {
p1 = PA + ~*b;
x |= 1;
} else {
p1 = PA + *b;
}
if (*c < 0) {
p2 = PA + ~*c;
x |= 2;
} else {
p2 = PA + *c;
}
}
}
}

static void ss_swapmerge(const sauchar_t *T, const saidx_t *PA, saidx_t *first,
saidx_t *middle, saidx_t *last, saidx_t *buf, saidx_t bufsize,
saidx_t depth)
{
#define STACK_SIZE SS_SMERGE_STACKSIZE
#define GETIDX(a) ((0 <= (a)) ? (a) : (~(a)))
#define MERGE_CHECK(a, b, c)   \
do {   \
if (((c)&1)\
|| (((c)&2)\
&& (ss_compare(T, PA + GETIDX(*((a)-1)), PA + *(a), depth) \
== 0))) {  \
*(a) = ~*(a);  \
}  \
if (((c)&4)\
&& ((ss_compare(T, PA + GETIDX(*((b)-1)), PA + *(b), depth)\
== 0))) {  \
*(b) = ~*(b);  \
}  \
} while (0)
struct
{
saidx_t *a, *b, *c;
saint_t d;
} stack[STACK_SIZE];
saidx_t *l, *r, *lm, *rm;
saidx_t m, len, half;
saint_t ssize;
saint_t check, next;

for (check = 0, ssize = 0;;) {
if ((last - middle) <= bufsize) {
if ((first < middle) && (middle < last)) {
ss_mergebackward(T, PA, first, middle, last, buf, depth);
}
MERGE_CHECK(first, last, check);
STACK_POP(first, middle, last, check);
continue;
}

if ((middle - first) <= bufsize) {
if (first < middle) {
ss_mergeforward(T, PA, first, middle, last, buf, depth);
}
MERGE_CHECK(first, last, check);
STACK_POP(first, middle, last, check);
continue;
}

for (m = 0, len = MIN(middle - first, last - middle), half = len >> 1;
 0 < len; len = half, half >>= 1) {
if (ss_compare(T, PA + GETIDX(*(middle + m + half)),
PA + GETIDX(*(middle - m - half - 1)), depth)
< 0) {
m += half + 1;
half -= (len & 1) ^ 1;
}
}

if (0 < m) {
lm = middle - m, rm = middle + m;
ss_blockswap(lm, middle, m);
l = r = middle, next = 0;
if (rm < last) {
if (*rm < 0) {
*rm = ~*rm;
if (first < lm) {
for (; *--l < 0;) {}
next |= 4;
}
next |= 1;
} else if (first < lm) {
for (; *r < 0; ++r) {}
next |= 2;
}
}

if ((l - first) <= (last - r)) {
STACK_PUSH(r, rm, last, (next & 3) | (check & 4));
middle = lm, last = l, check = (check & 3) | (next & 4);
} else {
if ((next & 2) && (r == middle)) { next ^= 6; }
STACK_PUSH(first, lm, l, (check & 3) | (next & 4));
first = r, middle = rm, check = (next & 3) | (check & 4);
}
} else {
if (ss_compare(T, PA + GETIDX(*(middle - 1)), PA + *middle, depth)
== 0) {
*middle = ~*middle;
}
MERGE_CHECK(first, last, check);
STACK_POP(first, middle, last, check);
}
}
#undef STACK_SIZE
}

#endif

void sssort(const sauchar_t *T, const saidx_t *PA, saidx_t *first,
saidx_t *last, saidx_t *buf, saidx_t bufsize, saidx_t depth, saidx_t n,
saint_t lastsuffix)
{
saidx_t *a;
#if SS_BLOCKSIZE != 0
saidx_t *b, *middle, *curbuf;
saidx_t j, k, curbufsize, limit;
#endif
saidx_t i;

if (lastsuffix != 0) { ++first; }

#if SS_BLOCKSIZE == 0
ss_mintrosort(T, PA, first, last, depth);
#else
if ((bufsize < SS_BLOCKSIZE) && (bufsize < (last - first))
&& (bufsize < (limit = ss_isqrt(last - first)))) {
if (SS_BLOCKSIZE < limit) { limit = SS_BLOCKSIZE; }
buf = middle = last - limit, bufsize = limit;
} else {
middle = last, limit = 0;
}
for (a = first, i = 0; SS_BLOCKSIZE < (middle - a);
 a += SS_BLOCKSIZE, ++i) {
#if SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE
ss_mintrosort(T, PA, a, a + SS_BLOCKSIZE, depth);
#elif 1 < SS_BLOCKSIZE
ss_insertionsort(T, PA, a, a + SS_BLOCKSIZE, depth);
#endif
curbufsize = last - (a + SS_BLOCKSIZE);
curbuf = a + SS_BLOCKSIZE;
if (curbufsize <= bufsize) { curbufsize = bufsize, curbuf = buf; }
for (b = a, k = SS_BLOCKSIZE, j = i; j & 1; b -= k, k <<= 1, j >>= 1) {
ss_swapmerge(T, PA, b - k, b, b + k, curbuf, curbufsize, depth);
}
}
#if SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE
ss_mintrosort(T, PA, a, middle, depth);
#elif 1 < SS_BLOCKSIZE
ss_insertionsort(T, PA, a, middle, depth);
#endif
for (k = SS_BLOCKSIZE; i != 0; k <<= 1, i >>= 1) {
if (i & 1) {
ss_swapmerge(T, PA, a - k, a, middle, buf, bufsize, depth);
a -= k;
}
}
if (limit != 0) {
#if SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE
ss_mintrosort(T, PA, middle, last, depth);
#elif 1 < SS_BLOCKSIZE
ss_insertionsort(T, PA, middle, last, depth);
#endif
ss_inplacemerge(T, PA, first, middle, last, depth);
}
#endif

if (lastsuffix != 0) {

saidx_t PAi[2];
PAi[0] = PA[*(first - 1)], PAi[1] = n - 2;
for (a = first, i = *(first - 1); (a < last)
 && ((*a < 0) || (0 < ss_compare(T, &(PAi[0]), PA + *a, depth)));
 ++a) {
*(a - 1) = *a;
}
*(a - 1) = i;
}
}

static INLINE saint_t tr_ilg(saidx_t n)
{
#if defined(BUILD_DIVSUFSORT64)
return (n >> 32)
? ((n >> 48) ? ((n >> 56) ? 56 + lg_table[(n >> 56) & 0xff]
  : 48 + lg_table[(n >> 48) & 0xff])
 : ((n >> 40) ? 40 + lg_table[(n >> 40) & 0xff]
  : 32 + lg_table[(n >> 32) & 0xff]))
: ((n & 0xffff0000)
? ((n & 0xff000000) ? 24 + lg_table[(n >> 24) & 0xff]
: 16 + lg_table[(n >> 16) & 0xff])
: ((n & 0x0000ff00) ? 8 + lg_table[(n >> 8) & 0xff]
: 0 + lg_table[(n >> 0) & 0xff]));
#else
return (n & 0xffff0000)
? ((n & 0xff000000) ? 24 + lg_table[(n >> 24) & 0xff]
: 16 + lg_table[(n >> 16) & 0xff])
: ((n & 0x0000ff00) ? 8 + lg_table[(n >> 8) & 0xff]
: 0 + lg_table[(n >> 0) & 0xff]);
#endif
}

static void tr_insertionsort(const saidx_t *ISAd, saidx_t *first, saidx_t *last)
{
saidx_t *a, *b;
saidx_t t, r;

for (a = first + 1; a < last; ++a) {
for (t = *a, b = a - 1; 0 > (r = ISAd[t] - ISAd[*b]);) {
do {
*(b + 1) = *b;
} while ((first <= --b) && (*b < 0));
if (b < first) { break; }
}
if (r == 0) { *b = ~*b; }
*(b + 1) = t;
}
}

static INLINE void tr_fixdown(
const saidx_t *ISAd, saidx_t *SA, saidx_t i, saidx_t size)
{
saidx_t j, k;
saidx_t v;
saidx_t c, d, e;

for (v = SA[i], c = ISAd[v]; (j = 2 * i + 1) < size; SA[i] = SA[k], i = k) {
d = ISAd[SA[k = j++]];
if (d < (e = ISAd[SA[j]])) {
k = j;
d = e;
}
if (d <= c) { break; }
}
SA[i] = v;
}

static void tr_heapsort(const saidx_t *ISAd, saidx_t *SA, saidx_t size)
{
saidx_t i, m;
saidx_t t;

m = size;
if ((size % 2) == 0) {
m--;
if (ISAd[SA[m / 2]] < ISAd[SA[m]]) { SWAP(SA[m], SA[m / 2]); }
}

for (i = m / 2 - 1; 0 <= i; --i) { tr_fixdown(ISAd, SA, i, m); }
if ((size % 2) == 0) {
SWAP(SA[0], SA[m]);
tr_fixdown(ISAd, SA, 0, m);
}
for (i = m - 1; 0 < i; --i) {
t = SA[0], SA[0] = SA[i];
tr_fixdown(ISAd, SA, 0, i);
SA[i] = t;
}
}

static INLINE saidx_t *tr_median3(
const saidx_t *ISAd, saidx_t *v1, saidx_t *v2, saidx_t *v3)
{
saidx_t *t;
if (ISAd[*v1] > ISAd[*v2]) { SWAP(v1, v2); }
if (ISAd[*v2] > ISAd[*v3]) {
if (ISAd[*v1] > ISAd[*v3]) {
return v1;
} else {
return v3;
}
}
return v2;
}

static INLINE saidx_t *tr_median5(const saidx_t *ISAd, saidx_t *v1, saidx_t *v2,
saidx_t *v3, saidx_t *v4, saidx_t *v5)
{
saidx_t *t;
if (ISAd[*v2] > ISAd[*v3]) { SWAP(v2, v3); }
if (ISAd[*v4] > ISAd[*v5]) { SWAP(v4, v5); }
if (ISAd[*v2] > ISAd[*v4]) {
SWAP(v2, v4);
SWAP(v3, v5);
}
if (ISAd[*v1] > ISAd[*v3]) { SWAP(v1, v3); }
if (ISAd[*v1] > ISAd[*v4]) {
SWAP(v1, v4);
SWAP(v3, v5);
}
if (ISAd[*v3] > ISAd[*v4]) { return v4; }
return v3;
}

static INLINE saidx_t *tr_pivot(
const saidx_t *ISAd, saidx_t *first, saidx_t *last)
{
saidx_t *middle;
saidx_t t;

t = last - first;
middle = first + t / 2;

if (t <= 512) {
if (t <= 32) {
return tr_median3(ISAd, first, middle, last - 1);
} else {
t >>= 2;
return tr_median5(
ISAd, first, first + t, middle, last - 1 - t, last - 1);
}
}
t >>= 3;
first = tr_median3(ISAd, first, first + t, first + (t << 1));
middle = tr_median3(ISAd, middle - t, middle, middle + t);
last = tr_median3(ISAd, last - 1 - (t << 1), last - 1 - t, last - 1);
return tr_median3(ISAd, first, middle, last);
}

typedef struct _trbudget_t trbudget_t;
struct _trbudget_t
{
saidx_t chance;
saidx_t remain;
saidx_t incval;
saidx_t count;
};

static INLINE void trbudget_init(
trbudget_t *budget, saidx_t chance, saidx_t incval)
{
budget->chance = chance;
budget->remain = budget->incval = incval;
}

static INLINE saint_t trbudget_check(trbudget_t *budget, saidx_t size)
{
if (size <= budget->remain) {
budget->remain -= size;
return 1;
}
if (budget->chance == 0) {
budget->count += size;
return 0;
}
budget->remain += budget->incval - size;
budget->chance -= 1;
return 1;
}

static INLINE void tr_partition(const saidx_t *ISAd, saidx_t *first,
saidx_t *middle, saidx_t *last, saidx_t **pa, saidx_t **pb, saidx_t v)
{
saidx_t *a, *b, *c, *d, *e, *f;
saidx_t t, s;
saidx_t x = 0;

for (b = middle - 1; (++b < last) && ((x = ISAd[*b]) == v);) {}
if (((a = b) < last) && (x < v)) {
for (; (++b < last) && ((x = ISAd[*b]) <= v);) {
if (x == v) {
SWAP(*b, *a);
++a;
}
}
}
for (c = last; (b < --c) && ((x = ISAd[*c]) == v);) {}
if ((b < (d = c)) && (x > v)) {
for (; (b < --c) && ((x = ISAd[*c]) >= v);) {
if (x == v) {
SWAP(*c, *d);
--d;
}
}
}
for (; b < c;) {
SWAP(*b, *c);
for (; (++b < c) && ((x = ISAd[*b]) <= v);) {
if (x == v) {
SWAP(*b, *a);
++a;
}
}
for (; (b < --c) && ((x = ISAd[*c]) >= v);) {
if (x == v) {
SWAP(*c, *d);
--d;
}
}
}

if (a <= d) {
c = b - 1;
if ((s = a - first) > (t = b - a)) { s = t; }
for (e = first, f = b - s; 0 < s; --s, ++e, ++f) { SWAP(*e, *f); }
if ((s = d - c) > (t = last - d - 1)) { s = t; }
for (e = b, f = last - s; 0 < s; --s, ++e, ++f) { SWAP(*e, *f); }
first += (b - a), last -= (d - c);
}
*pa = first, *pb = last;
}

static void tr_copy(saidx_t *ISA, const saidx_t *SA, saidx_t *first, saidx_t *a,
saidx_t *b, saidx_t *last, saidx_t depth)
{
/* sort suffixes of middle partition
   by using sorted order of suffixes of left and right partition. */
saidx_t *c, *d, *e;
saidx_t s, v;

v = b - SA - 1;
for (c = first, d = a - 1; c <= d; ++c) {
if ((0 <= (s = *c - depth)) && (ISA[s] == v)) {
*++d = s;
ISA[s] = d - SA;
}
}
for (c = last - 1, e = d + 1, d = b; e < d; --c) {
if ((0 <= (s = *c - depth)) && (ISA[s] == v)) {
*--d = s;
ISA[s] = d - SA;
}
}
}

static void tr_partialcopy(saidx_t *ISA, const saidx_t *SA, saidx_t *first,
saidx_t *a, saidx_t *b, saidx_t *last, saidx_t depth)
{
saidx_t *c, *d, *e;
saidx_t s, v;
saidx_t rank, lastrank, newrank = -1;

v = b - SA - 1;
lastrank = -1;
for (c = first, d = a - 1; c <= d; ++c) {
if ((0 <= (s = *c - depth)) && (ISA[s] == v)) {
*++d = s;
rank = ISA[s + depth];
if (lastrank != rank) {
lastrank = rank;
newrank = d - SA;
}
ISA[s] = newrank;
}
}

lastrank = -1;
for (e = d; first <= e; --e) {
rank = ISA[*e];
if (lastrank != rank) {
lastrank = rank;
newrank = e - SA;
}
if (newrank != rank) { ISA[*e] = newrank; }
}

lastrank = -1;
for (c = last - 1, e = d + 1, d = b; e < d; --c) {
if ((0 <= (s = *c - depth)) && (ISA[s] == v)) {
*--d = s;
rank = ISA[s + depth];
if (lastrank != rank) {
lastrank = rank;
newrank = d - SA;
}
ISA[s] = newrank;
}
}
}

static void tr_introsort(saidx_t *ISA, const saidx_t *ISAd, saidx_t *SA,
saidx_t *first, saidx_t *last, trbudget_t *budget)
{
#define STACK_SIZE TR_STACKSIZE
struct
{
const saidx_t *a;
saidx_t *b, *c;
saint_t d, e;
} stack[STACK_SIZE];
saidx_t *a, *b, *c;
saidx_t t;
saidx_t v, x = 0;
saidx_t incr = ISAd - ISA;
saint_t limit, next;
saint_t ssize, trlink = -1;

for (ssize = 0, limit = tr_ilg(last - first);;) {

if (limit < 0) {
if (limit == -1) {

tr_partition(
ISAd - incr, first, first, last, &a, &b, last - SA - 1);

if (a < last) {
for (c = first, v = a - SA - 1; c < a; ++c) { ISA[*c] = v; }
}
if (b < last) {
for (c = a, v = b - SA - 1; c < b; ++c) { ISA[*c] = v; }
}

if (1 < (b - a)) {
STACK_PUSH5(NULL, a, b, 0, 0);
STACK_PUSH5(ISAd - incr, first, last, -2, trlink);
trlink = ssize - 2;
}
if ((a - first) <= (last - b)) {
if (1 < (a - first)) {
STACK_PUSH5(ISAd, b, last, tr_ilg(last - b), trlink);
last = a, limit = tr_ilg(a - first);
} else if (1 < (last - b)) {
first = b, limit = tr_ilg(last - b);
} else {
STACK_POP5(ISAd, first, last, limit, trlink);
}
} else {
if (1 < (last - b)) {
STACK_PUSH5(ISAd, first, a, tr_ilg(a - first), trlink);
first = b, limit = tr_ilg(last - b);
} else if (1 < (a - first)) {
last = a, limit = tr_ilg(a - first);
} else {
STACK_POP5(ISAd, first, last, limit, trlink);
}
}
} else if (limit == -2) {

a = stack[--ssize].b, b = stack[ssize].c;
if (stack[ssize].d == 0) {
tr_copy(ISA, SA, first, a, b, last, ISAd - ISA);
} else {
if (0 <= trlink) { stack[trlink].d = -1; }
tr_partialcopy(ISA, SA, first, a, b, last, ISAd - ISA);
}
STACK_POP5(ISAd, first, last, limit, trlink);
} else {

if (0 <= *first) {
a = first;
do {
ISA[*a] = a - SA;
} while ((++a < last) && (0 <= *a));
first = a;
}
if (first < last) {
a = first;
do {
*a = ~*a;
} while (*++a < 0);
next = (ISA[*a] != ISAd[*a]) ? tr_ilg(a - first + 1) : -1;
if (++a < last) {
for (b = first, v = a - SA - 1; b < a; ++b) {
ISA[*b] = v;
}
}

if (trbudget_check(budget, a - first)) {
if ((a - first) <= (last - a)) {
STACK_PUSH5(ISAd, a, last, -3, trlink);
ISAd += incr, last = a, limit = next;
} else {
if (1 < (last - a)) {
STACK_PUSH5(
ISAd + incr, first, a, next, trlink);
first = a, limit = -3;
} else {
ISAd += incr, last = a, limit = next;
}
}
} else {
if (0 <= trlink) { stack[trlink].d = -1; }
if (1 < (last - a)) {
first = a, limit = -3;
} else {
STACK_POP5(ISAd, first, last, limit, trlink);
}
}
} else {
STACK_POP5(ISAd, first, last, limit, trlink);
}
}
continue;
}

if ((last - first) <= TR_INSERTIONSORT_THRESHOLD) {
tr_insertionsort(ISAd, first, last);
limit = -3;
continue;
}

if (limit-- == 0) {
tr_heapsort(ISAd, first, last - first);
for (a = last - 1; first < a; a = b) {
for (x = ISAd[*a], b = a - 1; (first <= b) && (ISAd[*b] == x);
 --b) {
*b = ~*b;
}
}
limit = -3;
continue;
}

a = tr_pivot(ISAd, first, last);
SWAP(*first, *a);
v = ISAd[*first];

tr_partition(ISAd, first, first + 1, last, &a, &b, v);
if ((last - first) != (b - a)) {
next = (ISA[*a] != v) ? tr_ilg(b - a) : -1;

for (c = first, v = a - SA - 1; c < a; ++c) { ISA[*c] = v; }
if (b < last) {
for (c = a, v = b - SA - 1; c < b; ++c) { ISA[*c] = v; }
}

if ((1 < (b - a)) && (trbudget_check(budget, b - a))) {
if ((a - first) <= (last - b)) {
if ((last - b) <= (b - a)) {
if (1 < (a - first)) {
STACK_PUSH5(ISAd + incr, a, b, next, trlink);
STACK_PUSH5(ISAd, b, last, limit, trlink);
last = a;
} else if (1 < (last - b)) {
STACK_PUSH5(ISAd + incr, a, b, next, trlink);
first = b;
} else {
ISAd += incr, first = a, last = b, limit = next;
}
} else if ((a - first) <= (b - a)) {
if (1 < (a - first)) {
STACK_PUSH5(ISAd, b, last, limit, trlink);
STACK_PUSH5(ISAd + incr, a, b, next, trlink);
last = a;
} else {
STACK_PUSH5(ISAd, b, last, limit, trlink);
ISAd += incr, first = a, last = b, limit = next;
}
} else {
STACK_PUSH5(ISAd, b, last, limit, trlink);
STACK_PUSH5(ISAd, first, a, limit, trlink);
ISAd += incr, first = a, last = b, limit = next;
}
} else {
if ((a - first) <= (b - a)) {
if (1 < (last - b)) {
STACK_PUSH5(ISAd + incr, a, b, next, trlink);
STACK_PUSH5(ISAd, first, a, limit, trlink);
first = b;
} else if (1 < (a - first)) {
STACK_PUSH5(ISAd + incr, a, b, next, trlink);
last = a;
} else {
ISAd += incr, first = a, last = b, limit = next;
}
} else if ((last - b) <= (b - a)) {
if (1 < (last - b)) {
STACK_PUSH5(ISAd, first, a, limit, trlink);
STACK_PUSH5(ISAd + incr, a, b, next, trlink);
first = b;
} else {
STACK_PUSH5(ISAd, first, a, limit, trlink);
ISAd += incr, first = a, last = b, limit = next;
}
} else {
STACK_PUSH5(ISAd, first, a, limit, trlink);
STACK_PUSH5(ISAd, b, last, limit, trlink);
ISAd += incr, first = a, last = b, limit = next;
}
}
} else {
if ((1 < (b - a)) && (0 <= trlink)) { stack[trlink].d = -1; }
if ((a - first) <= (last - b)) {
if (1 < (a - first)) {
STACK_PUSH5(ISAd, b, last, limit, trlink);
last = a;
} else if (1 < (last - b)) {
first = b;
} else {
STACK_POP5(ISAd, first, last, limit, trlink);
}
} else {
if (1 < (last - b)) {
STACK_PUSH5(ISAd, first, a, limit, trlink);
first = b;
} else if (1 < (a - first)) {
last = a;
} else {
STACK_POP5(ISAd, first, last, limit, trlink);
}
}
}
} else {
if (trbudget_check(budget, last - first)) {
limit = tr_ilg(last - first), ISAd += incr;
} else {
if (0 <= trlink) { stack[trlink].d = -1; }
STACK_POP5(ISAd, first, last, limit, trlink);
}
}
}
#undef STACK_SIZE
}

void trsort(saidx_t *ISA, saidx_t *SA, saidx_t n, saidx_t depth)
{
saidx_t *ISAd;
saidx_t *first, *last;
trbudget_t budget;
saidx_t t, skip, unsorted;

trbudget_init(&budget, tr_ilg(n) * 2 / 3, n);

for (ISAd = ISA + depth; - n < *SA; ISAd += ISAd - ISA) {
first = SA;
skip = 0;
unsorted = 0;
do {
if ((t = *first) < 0) {
first -= t;
skip += t;
} else {
if (skip != 0) {
*(first + skip) = skip;
skip = 0;
}
last = SA + ISA[t] + 1;
if (1 < (last - first)) {
budget.count = 0;
tr_introsort(ISA, ISAd, SA, first, last, &budget);
if (budget.count != 0) {
unsorted += budget.count;
} else {
skip = first - last;
}
} else if ((last - first) == 1) {
skip = -1;
}
first = last;
}
} while (first < (SA + n));
if (skip != 0) { *(first + skip) = skip; }
if (unsorted == 0) { break; }
}
}

}
const int MAXN = 1.1e6;
int SA[MAXN], lcp[MAXN], rank[MAXN];
int main()
{
std::string s;
s.reserve(MAXN);
io >> s;
int i, n = s.size();
DIVSUFSORTSA::divsufsort((unsigned char *)s.c_str(), SA + 1, n);
SA[0] = n;
for (int i = 0; i <= n; i++) rank[SA[i]] = i;
int h = 0;
lcp[0] = 0;
for (int i = 0; i < n; i++) {
int j = SA[rank[i] - 1];
h > 0 && h--;
for (; j + h < n && i + h < n; h++) {
if (s[j + h] != s[i + h]) break;
}
lcp[rank[i] - 1] = h;
}
for (i = 0; i < n; ++i) { io.WS(SA[i + 1] + 1); }
io.WL();
for (int i = 0; i < n - 1; i++) { io.WS(lcp[i + 1]); }
io.WL();
}

评测结果