#include <bits/stdc++.h>
using namespace std;
struct Runs {
int l, r, p;
bool operator==(const Runs &j) {
return l == j.l && r == j.r && p == j.p;
}
};
const int mod = 998244353, mod1 = 1e9 + 7, mod2 = 1e9 + 9;
const int bas1 = 315, bas2 = 79;
const int maxn = 2e6 + 5;
char t[maxn];
int m;
namespace getRuns {
struct Hash {
long long p[maxn], h[maxn];
int mod, buf;
Hash(int _buf, int _mod) {
buf = _buf;
mod = _mod;
}
void Init(char *s, int n) {
p[0] = 1;
h[0] = 0;
for (int i = 1; i <= n; i++) {
p[i] = p[i - 1] * buf % mod;
h[i] = (h[i - 1] * buf + s[i] - 'a' + 1) % mod;
}
}
bool tl(int u, int v, int len) {
return (h[u] - h[v] + (h[v - len] - h[u - len]) * p[len]) % mod == 0;
}
bool tr(int u, int v, int len) {
return (h[u + len - 1] - h[v + len - 1] + (h[v - 1] - h[u - 1]) * p[len]) % mod == 0;
}
int get(int l, int r) {
return (h[r] + (mod - h[l - 1]) * p[r - l + 1] % mod) % mod;
}
} h1(bas1, mod1), h2(bas2, mod2);
int extr(int x, int y) {
int l = 0, r = m - max(x, y) + 1, res = 0;
while (l <= r) {
int mid = l + r >> 1;
if (h1.tr(x, y, mid) && h2.tr(x, y, mid)) {
res = mid;
l = mid + 1;
} else
r = mid - 1;
}
return res;
}
int extl(int x, int y) {
int l = 0, r = min(x, y), res = 0;
while (l <= r) {
int mid = l + r >> 1;
if (h1.tl(x, y, mid) && h2.tl(x, y, mid)) {
res = mid;
l = mid + 1;
} else
r = mid - 1;
}
return res;
}
vector<Runs> raw_runs(0);
int CMP(int x, int y) {
if (x == y)
return 0;
int l = extr(x, y);
return t[x + l] < t[y + l] ? -1 : 1;
}
void Check(int i, int j) {
int p = j - i + 1;
int x = i - extl(i - 1, j), y = j + extr(i, j + 1);
if (y - x + 1 >= p * 2)
raw_runs.push_back({x, y, p});
}
int st[maxn], top;
void init() {
for (int i = m; i; i--) {
while (top && CMP(i, st[top]) <= 0)
top--;
if (top)
Check(i, st[top] - 1);
st[++top] = i;
}
top = 0;
for (int i = m; i; i--) {
while (top && CMP(i, st[top]) >= 0)
top--;
if (top)
Check(i, st[top] - 1);
st[++top] = i;
}
}
} // namespace getRuns
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> (t + 1);
m = strlen(t + 1);
getRuns::h1.Init(t, m);
getRuns::h2.Init(t, m);
getRuns::init();
sort(getRuns::raw_runs.begin(), getRuns::raw_runs.end(), [](const Runs & A, const Runs & B) {
return A.l == B.l ? (A.r == B.r ? A.p < B.p : A.r < B.r) : A.l < B.l;
});
int tot = std::unique(getRuns::raw_runs.begin(), getRuns::raw_runs.end()) - getRuns::raw_runs.begin();
cout << tot << '\n';
getRuns::raw_runs.resize(tot);
for (auto [l, r, p] : getRuns::raw_runs)
cout << l << " " << r << " " << p << '\n';
}
/*#ifdef LOCAL
#include "stdafx.h"
#else
#include <bits/stdc++.h>
#define IL inline
#define LL long long
#define eb emplace_back
#define sz(v) ((int) (v).size())
#define me(f, x) memset(f, x, sizeof(f))
#define mc(f, g) memcpy(f, g, sizeof(g))
#define L(i, j, k) for (int i = (j); i <= (k); ++i)
#define R(i, j, k) for (int i = (j); i >= (k); --i)
#define FIO(FILE) freopen(FILE".in", "r", stdin), freopen(FILE".out", "w", stdout)
using namespace std;
using vi = vector<int>;
#endif
namespace vEB_tree_impl {
#ifdef _WIN32
using uint = unsigned;
#endif
using ull = unsigned long long;
template<int LG, class T = void>
struct vEB_tree_t {
static constexpr uint shf = LG * 3;
static constexpr uint bas = (1U << shf) - 1;
using _vEB_tree_t = vEB_tree_t<LG / 2>;
_vEB_tree_t msk;
std::array<_vEB_tree_t, 1 << shf> ch;
int mn, mx;
vEB_tree_t () : mn(1 << 30), mx(-1) {}
bool empty () const {
return mx == -1;
}
int min () const {
return mn;
}
int max () const {
return mx;
}
void insert (int x) {
if (max() == -1) {
mn = mx = x;
return;
}
if (x == min()) {
return;
}
if (x < min()) {
std::swap(x, mn);
}
mx = std::max(mx, x);
int p = x >> shf;
if (ch[p].empty()) {
msk.insert(p);
}
ch[p].insert(x & bas);
}
void erase (int x) {
if (x == min()) {
if (x == max()) {
mn = 1U << 30, mx = -1;
} else {
int p = msk.min();
mn = (p << shf) | ch[p].min();
ch[p].erase(ch[p].min());
if (ch[p].empty()) {
msk.erase(p);
}
}
} else {
int p = x >> shf;
if (ch[p].empty()) {
return;
}
ch[p].erase(x & bas);
if (ch[p].empty()) {
msk.erase(p);
}
if (x == max()) {
p = msk.max();
mx = ~p ? (p << shf) | ch[p].max() : min();
}
}
}
bool contain (int x) {
if (x == min()) {
return true;
}
int p = x >> shf;
return !ch[p].empty() && ch[p].contain(x & bas);
}
int find_next (int x) {
if (x > max()) {
return -1;
}
if (x <= min()) {
return min();
}
int p = x >> shf;
x &= bas;
if (x <= ch[p].max()) {
return (p << shf) | ch[p].find_next(x);
}
int y = msk.find_next(p + 1);
return ~y ? (y << shf) | ch[y].min() : -1;
}
int find_prev (int x) {
if (x <= min()) {
return -1;
}
if (x > max()) {
return max();
}
int p = x >> shf;
x &= bas;
if (x > ch[p].min()) {
return (p << shf) | ch[p].find_prev(x);
}
int y = msk.find_prev(p);
return ~y ? (y << shf) | ch[y].max() : min();
}
};
inline constexpr uint lb (ull x) {
return x ? __builtin_ctzll(x) : -1;
}
inline constexpr uint hb (ull x) {
return x ? 63 - __builtin_clzll(x) : -1;
}
template<int LG>
struct vEB_tree_t<LG, typename std::enable_if<LG == 1>::type> {
ull msk;
vEB_tree_t () : msk(0) {}
bool empty () {
return msk == 0;
}
int min () const {
return msk ? __builtin_ctzll(msk) : 1U << 30;
}
int max () const {
return hb(msk);
}
bool contain (int x) {
return msk >> x & 1;
}
void insert (int x) {
msk |= 1ULL << x;
}
void erase (int x) {
msk &= ~(1ULL << x);
}
int find_next (int x) {
return lb(msk & ~((1ULL << x) - 1));
}
int find_prev (int x) {
return hb(msk & ((1ULL << x) - 1));
}
};
}
using vEB_tree = vEB_tree_impl::vEB_tree_t<4>;
vEB_tree ds;
constexpr int N = 2e5 + 9;
constexpr int inf = 2e6;
int n, M, val[N * 3], tot;
vi a[N];
IL constexpr LL sq (int x) {
return (LL)x * x;
}
struct calculator {
int l, r;
LL s;
vi A, B;
void init (int p) {
int q = p ? p - 1 : n - 1;
l = sz(a[q]);
r = -1;
vector<pair<int, int>> C;
L (i, 0, sz(a[p]) - 1) {
C.eb(a[p][i], i + 1);
}
L (i, 0, sz(a[q]) - 1) {
C.eb(a[q][i], -i - 1);
}
sort(C.begin(), C.end());
A.resize(sz(a[p]));
B.resize(sz(a[q]));
val[tot] = 0;
ds.insert(tot++);
L (i, 0, sz(C) - 1) {
val[tot] = C[i].first;
if (C[i].second > 0) {
A[C[i].second - 1] = tot++;
} else {
B[-C[i].second - 1] = tot++;
}
}
val[tot] = inf;
ds.insert(tot++);
s = (LL)inf * inf;
}
void ins (int x) {
int a = ds.find_prev(x), b = ds.find_next(x);
s += sq(val[x] - val[a]) + sq(val[x] - val[b]) - sq(val[a] - val[b]);
ds.insert(x);
}
void era (int x) {
ds.erase(x);
int a = ds.find_prev(x), b = ds.find_next(x);
s += sq(val[a] - val[b]) - sq(val[x] - val[a]) - sq(val[x] - val[b]);
}
LL gt (int ql, int qr) {
while (l > ql) {
ins(B[--l]);
}
while (r < qr) {
ins(A[++r]);
}
while (l < ql) {
era(B[l++]);
}
while (r > qr) {
era(A[r--]);
}
return s;
}
} c[N];
vector<LL> f[N];
vi g[N];
void DP (int k, int l, int r, int L, int R) {
if (l > r || L > R) {
return;
}
int m = (l + r) / 2;
LL mn = 0;
int p = -1;
L (i, L, R) {
LL w = f[k ? k - 1 : n - 1][i] + c[k].gt(i, m - 1);
if (p == -1 || w < mn) {
mn = w;
p = i;
}
}
f[k][m] = mn;
g[k][m] = p;
DP(k, l, m - 1, L, p);
DP(k, m + 1, r, p, R);
}
struct inter {
int L, R;
inter (int a = 0, int b = 0) {
L = a, R = b;
}
};
LL ans;
void conq (vector<inter> q) {
if (q[0].L > q[0].R) {
return;
}
int m = (q[0].L + q[0].R) / 2;
L (i, q[1].L, q[1].R) {
f[1][i] = c[1].gt(m, i - 1);
}
L (i, 2, n - 1) {
DP(i, q[i].L, q[i].R, q[i - 1].L, q[i - 1].R);
}
LL mn = 0;
int p = -1;
L (i, q[n - 1].L, q[n - 1].R) {
LL w = f[n - 1][i] + c[0].gt(i, m - 1);
if (p == -1 || w < mn) {
mn = w;
p = i;
}
}
ans = min(ans, mn);
auto ql = q, qr = q;
R (i, n - 1, 1) {
ql[i].R = qr[i].L = p;
p = g[i][p];
}
ql[0].R = m - 1;
qr[0].L = m + 1;
conq(ql);
conq(qr);
}
int main () {
cin >> n;
L (i, 0, n - 1) {
int m;
cin >> m;
a[i].resize(m);
L (j, 0, m - 1) {
cin >> a[i][j];
}
}
int idx = 0;
L (i, 1, n - 1) {
if (sz(a[i]) < sz(a[idx])) {
idx = i;
}
}
rotate(a, a + idx, a + n);
vector<inter> init;
L (i, 0, n - 1) {
c[i].init(i);
f[i].resize(sz(a[i]));
g[i].resize(sz(a[i]));
init.eb(0, sz(a[i]) - 1);
}
ans = LONG_LONG_MAX;
conq(init);
cout << ans << '\n';
}#ifdef LOCAL
#include "stdafx.h"
#else
#include <bits/stdc++.h>
#define IL inline
#define LL long long
#define eb emplace_back
#define sz(v) ((int) (v).size())
#define me(f, x) memset(f, x, sizeof(f))
#define mc(f, g) memcpy(f, g, sizeof(g))
#define L(i, j, k) for (int i = (j); i <= (k); ++i)
#define R(i, j, k) for (int i = (j); i >= (k); --i)
#define FIO(FILE) freopen(FILE".in", "r", stdin), freopen(FILE".out", "w", stdout)
using namespace std;
using vi = vector<int>;
#endif
namespace vEB_tree_impl {
#ifdef _WIN32
using uint = unsigned;
#endif
using ull = unsigned long long;
template<int LG, class T = void>
struct vEB_tree_t {
static constexpr uint shf = LG * 3;
static constexpr uint bas = (1U << shf) - 1;
using _vEB_tree_t = vEB_tree_t<LG / 2>;
_vEB_tree_t msk;
std::array<_vEB_tree_t, 1 << shf> ch;
int mn, mx;
vEB_tree_t () : mn(1 << 30), mx(-1) {}
bool empty () const {
return mx == -1;
}
int min () const {
return mn;
}
int max () const {
return mx;
}
void insert (int x) {
if (max() == -1) {
mn = mx = x;
return;
}
if (x == min()) {
return;
}
if (x < min()) {
std::swap(x, mn);
}
mx = std::max(mx, x);
int p = x >> shf;
if (ch[p].empty()) {
msk.insert(p);
}
ch[p].insert(x & bas);
}
void erase (int x) {
if (x == min()) {
if (x == max()) {
mn = 1U << 30, mx = -1;
} else {
int p = msk.min();
mn = (p << shf) | ch[p].min();
ch[p].erase(ch[p].min());
if (ch[p].empty()) {
msk.erase(p);
}
}
} else {
int p = x >> shf;
if (ch[p].empty()) {
return;
}
ch[p].erase(x & bas);
if (ch[p].empty()) {
msk.erase(p);
}
if (x == max()) {
p = msk.max();
mx = ~p ? (p << shf) | ch[p].max() : min();
}
}
}
bool contain (int x) {
if (x == min()) {
return true;
}
int p = x >> shf;
return !ch[p].empty() && ch[p].contain(x & bas);
}
int find_next (int x) {
if (x > max()) {
return -1;
}
if (x <= min()) {
return min();
}
int p = x >> shf;
x &= bas;
if (x <= ch[p].max()) {
return (p << shf) | ch[p].find_next(x);
}
int y = msk.find_next(p + 1);
return ~y ? (y << shf) | ch[y].min() : -1;
}
int find_prev (int x) {
if (x <= min()) {
return -1;
}
if (x > max()) {
return max();
}
int p = x >> shf;
x &= bas;
if (x > ch[p].min()) {
return (p << shf) | ch[p].find_prev(x);
}
int y = msk.find_prev(p);
return ~y ? (y << shf) | ch[y].max() : min();
}
};
inline constexpr uint lb (ull x) {
return x ? __builtin_ctzll(x) : -1;
}
inline constexpr uint hb (ull x) {
return x ? 63 - __builtin_clzll(x) : -1;
}
template<int LG>
struct vEB_tree_t<LG, typename std::enable_if<LG == 1>::type> {
ull msk;
vEB_tree_t () : msk(0) {}
bool empty () {
return msk == 0;
}
int min () const {
return msk ? __builtin_ctzll(msk) : 1U << 30;
}
int max () const {
return hb(msk);
}
bool contain (int x) {
return msk >> x & 1;
}
void insert (int x) {
msk |= 1ULL << x;
}
void erase (int x) {
msk &= ~(1ULL << x);
}
int find_next (int x) {
return lb(msk & ~((1ULL << x) - 1));
}
int find_prev (int x) {
return hb(msk & ((1ULL << x) - 1));
}
};
}
using vEB_tree = vEB_tree_impl::vEB_tree_t<4>;
vEB_tree ds;
constexpr int N = 2e5 + 9;
constexpr int inf = 2e6;
int n, M, val[N * 3], tot;
vi a[N];
IL constexpr LL sq (int x) {
return (LL)x * x;
}
struct calculator {
int l, r;
LL s;
vi A, B;
void init (int p) {
int q = p ? p - 1 : n - 1;
l = sz(a[q]);
r = -1;
vector<pair<int, int>> C;
L (i, 0, sz(a[p]) - 1) {
C.eb(a[p][i], i + 1);
}
L (i, 0, sz(a[q]) - 1) {
C.eb(a[q][i], -i - 1);
}
sort(C.begin(), C.end());
A.resize(sz(a[p]));
B.resize(sz(a[q]));
val[tot] = 0;
ds.insert(tot++);
L (i, 0, sz(C) - 1) {
val[tot] = C[i].first;
if (C[i].second > 0) {
A[C[i].second - 1] = tot++;
} else {
B[-C[i].second - 1] = tot++;
}
}
val[tot] = inf;
ds.insert(tot++);
s = (LL)inf * inf;
}
void ins (int x) {
int a = ds.find_prev(x), b = ds.find_next(x);
s += sq(val[x] - val[a]) + sq(val[x] - val[b]) - sq(val[a] - val[b]);
ds.insert(x);
}
void era (int x) {
ds.erase(x);
int a = ds.find_prev(x), b = ds.find_next(x);
s += sq(val[a] - val[b]) - sq(val[x] - val[a]) - sq(val[x] - val[b]);
}
LL gt (int ql, int qr) {
while (l > ql) {
ins(B[--l]);
}
while (r < qr) {
ins(A[++r]);
}
while (l < ql) {
era(B[l++]);
}
while (r > qr) {
era(A[r--]);
}
return s;
}
} c[N];
vector<LL> f[N];
vi g[N];
void DP (int k, int l, int r, int L, int R) {
if (l > r || L > R) {
return;
}
int m = (l + r) / 2;
LL mn = 0;
int p = -1;
L (i, L, R) {
LL w = f[k ? k - 1 : n - 1][i] + c[k].gt(i, m - 1);
if (p == -1 || w < mn) {
mn = w;
p = i;
}
}
f[k][m] = mn;
g[k][m] = p;
DP(k, l, m - 1, L, p);
DP(k, m + 1, r, p, R);
}
struct inter {
int L, R;
inter (int a = 0, int b = 0) {
L = a, R = b;
}
};
LL ans;
void conq (vector<inter> q) {
if (q[0].L > q[0].R) {
return;
}
int m = (q[0].L + q[0].R) / 2;
L (i, q[1].L, q[1].R) {
f[1][i] = c[1].gt(m, i - 1);
}
L (i, 2, n - 1) {
DP(i, q[i].L, q[i].R, q[i - 1].L, q[i - 1].R);
}
LL mn = 0;
int p = -1;
L (i, q[n - 1].L, q[n - 1].R) {
LL w = f[n - 1][i] + c[0].gt(i, m - 1);
if (p == -1 || w < mn) {
mn = w;
p = i;
}
}
ans = min(ans, mn);
auto ql = q, qr = q;
R (i, n - 1, 1) {
ql[i].R = qr[i].L = p;
p = g[i][p];
}
ql[0].R = m - 1;
qr[0].L = m + 1;
conq(ql);
conq(qr);
}
int main () {
cin >> n;
L (i, 0, n - 1) {
int m;
cin >> m;
a[i].resize(m);
L (j, 0, m - 1) {
cin >> a[i][j];
}
}
int idx = 0;
L (i, 1, n - 1) {
if (sz(a[i]) < sz(a[idx])) {
idx = i;
}
}
rotate(a, a + idx, a + n);
vector<inter> init;
L (i, 0, n - 1) {
c[i].init(i);
f[i].resize(sz(a[i]));
g[i].resize(sz(a[i]));
init.eb(0, sz(a[i]) - 1);
}
ans = LONG_LONG_MAX;
conq(init);
cout << ans << '\n';
}*/