QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#608139#9406. Triangleucup-team4435#AC ✓283ms60152kbC++209.7kb2024-10-03 19:02:252024-10-03 19:02:25

Judging History

你现在查看的是测评时间为 2024-10-03 19:02:25 的历史记录

  • [2024-10-14 03:17:17]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:294ms
  • 内存:60364kb
  • [2024-10-14 03:16:45]
  • hack成功,自动添加数据
  • (/hack/983)
  • [2024-10-03 19:02:25]
  • 评测
  • 测评结果:100
  • 用时:283ms
  • 内存:60152kb
  • [2024-10-03 19:02:25]
  • 提交

answer

#pragma GCC optimize("Ofast")

#include "bits/stdc++.h"

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i < (n); ++i)
#define rep1n(i, n) for (int i = 1; i <= (n); ++i)
#define repr(i, n) for (int i = (n) - 1; i >= 0; --i)
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define each(x, a) for (auto &x : a)
#define ar array
#define vec vector
#define range(i, n) rep(i, n)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using str = string;
using pi = pair<int, int>;
using pl = pair<ll, ll>;

using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pair<int, int>>;
using vvi = vector<vi>;

int Bit(int mask, int b) { return (mask >> b) & 1; }

template<class T>
bool ckmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool ckmax(T &a, const T &b) {
    if (b > a) {
        a = b;
        return true;
    }
    return false;
}

// [l, r)
template<typename T, typename F>
T FindFirstTrue(T l, T r, const F &predicat) {
    --l;
    while (r - l > 1) {
        T mid = l + (r - l) / 2;
        if (predicat(mid)) {
            r = mid;
        } else {
            l = mid;
        }
    }
    return r;
}


template<typename T, typename F>
T FindLastFalse(T l, T r, const F &predicat) {
    return FindFirstTrue(l, r, predicat) - 1;
}


const ll INF = 2e18;
const int INFi = 1e9;
const int N = 30 + 5;
const int LG = 20;

struct suffix_array {
    std::vector<int> order, suffix_position, lcp;

    template<typename T>
    suffix_array(T str = T()) {
        str.push_back(*std::min_element(str.begin(), str.end()) - 1);
        int n = str.size();

        order.resize(n);
        std::iota(order.begin(), order.end(), 0);
        std::sort(order.begin(), order.end(), [&](const int i, const int j) {
            return str[i] < str[j];
        });

        suffix_position.resize(n);
        for (int i = 0; i < n; i++)
            suffix_position[order[i]] = i == 0 ? 0 : suffix_position[order[i - 1]] + (str[order[i]] != str[order[i - 1]]);

        std::vector<int> ptr(n), new_order(n), new_suffix_positoin(n);
        for (int len = 1; suffix_position[order.back()] != n - 1; len <<= 1) {
            std::fill(ptr.begin(), ptr.begin() + suffix_position[order.back()] + 1, 0);
            for (int i = 0; i < n; i++)
                if (suffix_position[i] + 1 < n)
                    ptr[suffix_position[i] + 1]++;

            for (int i = 1; i <= suffix_position[order.back()]; i++)
                ptr[i] += ptr[i - 1];

            for (const int position : order) {
                int suffix = (position - len + n) % n;
                new_order[ptr[suffix_position[suffix]]++] = suffix;
            }
            std::swap(order, new_order);

            for (int i = 0; i < n; i++)
                new_suffix_positoin[order[i]] = i == 0 ? 0 : new_suffix_positoin[order[i - 1]]
                                                             + (suffix_position[order[i]] != suffix_position[order[i - 1]]
                                                                || suffix_position[(order[i] + len) % n] != suffix_position[(order[i - 1] + len) % n]);

            std::swap(suffix_position, new_suffix_positoin);
        }
        assert(order[0] == n - 1);

        lcp.resize(n);
        int current_lcp = 0;
        for (int suffix = 0; suffix < n - 1; suffix++, current_lcp = current_lcp == 0 ? 0 : current_lcp - 1) {
            int previous_suffix = order[suffix_position[suffix] - 1];
            while (str[suffix + current_lcp] == str[previous_suffix + current_lcp])
                current_lcp++;

            lcp[suffix_position[suffix]] = current_lcp;
        }
    }
};


const int SZ = 26;
struct Trie {
    struct node {
        node* nxt[SZ], *parent;
        std::vector<int> ends;
        int parent_index, depth;
        node* suffix_link, *supper_suffix_link;

        node() : parent(nullptr), parent_index(-1), depth(0), suffix_link(nullptr), supper_suffix_link(nullptr) {
            std::fill(std::begin(nxt), std::end(nxt), nullptr);
        }

        bool is_terminal() const {
            return !ends.empty();
        }

        node* go_ignoring_extra_edges(int index) const {
            node* v = nxt[index];
            return v && v->depth == depth + 1 ? v : nullptr;
        }
    };

    node* root;

    Trie() : root(new node()) {}

    template<typename U>
    node* add(const U &str, int id = -1) {
        node* v = root;
        for (int i = 0; i < int(str.size()); i++) {
            int cur_index = str[i] - 'a';
            if (!v->nxt[cur_index]) {
                v->nxt[cur_index] = new node();
                v->nxt[cur_index]->parent = v;
                v->nxt[cur_index]->parent_index = cur_index;
                v->nxt[cur_index]->depth = v->depth + 1;
            }
            v = v->nxt[cur_index];
        }
        if (id != -1)
            v->ends.push_back(id);

        return v;
    }

    node* go(node* v, char c) {
        int cur_index = c - 'a';
        return v->nxt[cur_index];
    }


    std::vector<node*> get_vertices() {
        std::vector<node*> vertices{root};
        for (int i = 0; i < int(vertices.size()); i++)
            for (int j = 0; j < SZ; j++) {
                auto vertex = vertices[i]->go_ignoring_extra_edges(j);
                if (vertex)
                    vertices.push_back(vertex);
            }

        return vertices;
    }

    ~Trie() {
        for (auto vertex : get_vertices())
            delete vertex;
    }
};

template<typename T>
std::vector<int> z_function(const T &str) {
    int n = int(str.size());
    std::vector<int> z(n);
    for (int i = 1, l = 0, r = 0; i < n; i++) {
        if (i < r)
            z[i] = std::min(r - i, z[i - l]);

        while (i + z[i] < n && str[z[i]] == str[i + z[i]])
            z[i]++;

        if (i + z[i] > r)
            l = i, r = i + z[i];
    }
    return z;
}



struct fenwick {
    int n{};
    vector<ll> fenw{};

    void build(int k) {
        n = k;
        fenw.resize(n);
    }

    void upd(int i, ll x) {
        for (; i < n; i = i | (i + 1)) fenw[i] += x;
    }

    ll get(int i) {
        ll res = 0;
        for (; i >= 0; i = (i & (i + 1)) - 1) res += fenw[i];
        return res;
    }

    ll get(int l, int r) {
        if (l > r) return 0;
        return get(r) - get(l - 1);
    }
};

void solve() {
    int n; cin >> n;
    vector<string> s(n);
    rep(i, n) cin >> s[i];
    sort(all(s));
    vi total;
    vi start(n);
    Trie T;
    rep(i, n) {
        start[i] = total.size();
        for(auto &c : s[i]) total.push_back((int)c + n + 10);
        total.push_back(i);
        T.add(s[i], i);
    }
    suffix_array SA(total);
    vi pos(n);
    rep(i, n) pos[i] = SA.suffix_position[start[i]];
    ll ans = 0;
    rep(i, n) {
        Trie::node* v = T.root;
        ll was = 0;
        auto z = z_function(s[i]);
        z.push_back(0);
        vector<ll> cnt(s[i].size() + 1);
        vector<pair<int, int>> w(s[i].size() + 1, {-1, -1});
        vector<vi> add(s[i].size() + 1);
        fenwick f;
        f.build(s[i].size() + 1);

        for(int p = 1; p < s[i].size(); ++p) {
            if (z[p] == (int)s[i].size() - p) {
                w[p] = {z[p] + 1, s[i].size()};
            } else if (p + z[p] < (int)s[i].size() && s[i][p + z[p]] < s[i][z[p]]) {
                w[p] = {z[p] + 1, s[i].size()};
            }
            if (w[p].first != -1) {
                add[max(w[p].first, p + 1)].push_back(p);
            }
            for(auto &j : add[p]) f.upd(j, cnt[j] - cnt[j - 1]);

            cnt[p] = cnt[p - 1];
            v = T.go(v, s[i][p - 1]);
            if (v->ends.empty()) continue;
            int l1 = v->ends.front();
            int l2 = v->ends.back();
            int sz = v->ends.size();
            cnt[p] += sz;
            assert(l1 <= l2 && l2 < i);
            assert(sz == (l2 - l1 + 1));
            { // a
                int suf_pos = SA.suffix_position[start[i] + p];
                int rq = pos[i];
                int lq = max(pos[l1], suf_pos);

                int nxt = lower_bound(all(pos), lq) - pos.begin();
                assert(nxt >= l1);
                if (nxt < i) {
                    was += sz;
                    ans += 1ll * sz * (i - max(nxt, l2 + 1));
                }
                if (nxt == l1) {
                    ans += 1ll * sz * (sz - 1) / 2;
                }
            }
            { // b
                int suf_pos = SA.suffix_position[start[i] + p];
                int rq = pos[l2];
                int lq = suf_pos;

                int nxt = lower_bound(all(pos), lq) - pos.begin();
                if (nxt <= l2) {
                    assert(nxt <= l1);
                    ans += 1ll * sz * (l1 - nxt);
                }
            }
            if (w[p].first < p && w[p].first != -1) {
                ans -= f.get(w[p].first, p - 1) * sz;
            }
        }
        {
            v = T.go(v, s[i].back());
            int l = v->ends[0];
            int sz = i - l;
            ans += 1ll * sz * (l - was);
            ans += 1ll * sz * (sz - 1) / 2;
        }
    }
    cout << ans << '\n';
}


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(12) << fixed;
    int t = 1;
    cin >> t;
    rep(i, t) {
        solve();
    }
    return 0;
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3612kb

input:

3
6
cbaa
cb
cb
cbaa
ba
ba
3
sdcpc
sd
cpc
1
ccpc

output:

16
0
0

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 1ms
memory: 3660kb

input:

14
1
lfpbavjsm
2
pdtlkfwn
mbd
3
dvqksg
dvqksg
uhbhpyhj
4
ombwb
ombwb
ombwb
ombwb
5
oztclz
oztclz
oztclz
oztclz
kul
6
vco
vco
vco
dtktsqtinm
vco
vco
7
tb
tb
kowbsu
ygkfphcij
tb
uvei
tb
8
vxxtxssht
abnsxbf
bydaae
bydaae
udalyvmcef
bydaae
bydaae
bydaae
9
aaze
zvyonw
qjfv
mmhkef
qjfv
qjfv
qjfv
mmhkef
qj...

output:

0
0
0
4
10
20
10
20
41
14
63
74
18
11081

result:

ok 14 lines

Test #3:

score: 0
Accepted
time: 1ms
memory: 3764kb

input:

11
10
bppzfsncq
bppzfsncq
vcqxgcehdx
bppzfsncq
bppzfsncq
muwrcvt
w
aanwhqmync
aanwhqmync
bppzfsncq
10
t
jkky
t
z
t
t
z
z
z
t
10
qidkyca
uhqubvbo
kosyvh
gsj
gsj
gsj
duo
jrro
gsj
jrro
10
lhktb
lhktb
lhktb
uohl
lhktb
r
lhktb
lhktb
wruim
lhktb
10
e
gqvdmpvxb
gqvdmpvxb
gqvdmpvxb
sttirbhz
gqvdmpvxb
zdfpm
...

output:

30
60
15
35
20
20
23
12
38
44
8047

result:

ok 11 lines

Test #4:

score: 0
Accepted
time: 3ms
memory: 4356kb

input:

11
100
kalgqjh
mdszzwe
qxn
kalgqjh
hy
kalgqjh
suplvp
r
kkeoxmx
tcoise
suplvp
suplvp
y
kalgqjh
vrwniyici
jmnyrradyq
kalgqjh
kalgqjh
suplvp
rkg
xzevyk
zc
suplvp
hcupv
kalgqjh
qakyahjaoi
mum
pbg
u
ip
kalgqjh
kalgqjh
jngc
ylr
suplvp
qxn
kalgqjh
bzwodm
e
kalgqjh
kalgqjh
evmm
kbymvbccs
kalgqjh
suplvp
kalg...

output:

12478
6722
9220
6668
4934
11233
7950
5470
4525
5743
1586066

result:

ok 11 lines

Test #5:

score: 0
Accepted
time: 3ms
memory: 4472kb

input:

2
1000
t
lhijhkxzzx
nhfiksblww
h
xg
z
dcbmbvyz
ois
ynwjgfp
oqzv
qtoinl
gr
teu
kmza
hs
t
mwhewk
kjmuneon
bekku
qheweh
szhagft
fcwjp
bobwnap
y
oqpole
oqzv
xeaiyhfeg
rjkdidea
wmeslege
vyyi
teomn
yvmcnw
vnvum
tgnl
swqqruuvc
xxllevp
bov
dse
e
b
rtbhogkx
nzs
e
bs
pppyndgrrv
n
tzbwqdusn
e
xeaiyhfeg
i
agnet...

output:

2430570
1904282

result:

ok 2 lines

Test #6:

score: 0
Accepted
time: 36ms
memory: 13352kb

input:

503
16
yh
yh
yhc
yhc
yhcowdfqlwfidnx
yhc
yhc
yh
yhcowdfqlwfidn
yhcowdfqlwfidnx
yh
h
yh
yhcowdfqlwfidnx
yhcowdfqlwfidnx
yhc
19
nb
nbg
vpfkllgv
nmzqfsuafqtayjjjcidpygz
nb
nb
gutq
n
omyuvm
fgxtfbhuglxyiumi
nbghjuti
nbg
nb
fgxt
nbghjuti
n
nb
nbg
n
7
rtjiwfidoahckhvgoxvvrncqvgerqiuaruiftakvugsgnsw
wllcan...

output:

531
485
6
12
4
118
6
3
1635
18
373
20
954
6208
45
12
1124
79
267
2
5778
22
13
1
1
16
630
0
7
16315
0
2155
2308
26
936
109
103
5
0
2492
7
2
114
144
11
158
0
0
101
455
0
12234
78
631
5402
94
66
84
161
4412
5
3
81
22
20
13
52
632
6
137
56
2
3
64521
122
330
0
0
7
0
113
249
8
301
335
1825
110
4
108
50
10...

result:

ok 503 lines

Test #7:

score: 0
Accepted
time: 45ms
memory: 12848kb

input:

503
23
rjyyivdg
n
n
n
n
n
n
n
nmr
n
nmrk
nm
rjyyivdguyiffnvunoxconw
n
n
n
o
lixclcmwthwkrsi
mqluhyypgfkmdvgpzju
n
nmrk
rjy
n
15
jotwxwhaqdxmazhslyouztprzlirisvwvduojb
jot
jotwxw
j
jotwx
jotwx
gohg
j
gdgneodagmdhvvapjh
jotwxw
xs
vurk
vurk
j
xs
7
xrczucnkbemaymvabkkwnn
xrczucnkbemaymvabkkwnn
xrczucnkb...

output:

855
58
35
0
1
56
2
112
1
8465
242
56
110
23
544
0
3
17
29
11
764
20
9
0
4
77
812
35
4
10
32
437
9
2364
3
2
11
2
421
50
4
107
1
62
1120
3
1
16
3970
1147
1026
8
4
85
9
31
61
16
205
2
2
84
238
1
1
51
4
0
16
61
331
4
16
7
0
7
148
10
13
2
1
37
1
67
0
296
1
0
644
32
2
10
0
5
126
3490
4
0
10
331
1216
7921
...

result:

ok 503 lines

Test #8:

score: 0
Accepted
time: 48ms
memory: 12876kb

input:

503
5
ljtolmgjndlwoyjjttak
mihjdhkyfnafwrpeuiuiurusvsnu
ljtolmgjndlwoyjjttak
mihjd
ljtolmgjndlwoyjjttak
25
lhx
lh
lhx
lh
k
lh
kninp
l
lhx
lhx
izeqohkpfuovopebttqaufmmlivd
lhx
lhx
qid
lhx
lh
lhx
lhx
oklb
l
lhx
lhx
lhx
lhx
l
9
mxeonfwpujrilfigjoiyjkzdmi
fezhyrcyqy
mx
fezh
f
dmvfbklnkxmnetib
dmvfbkln
m...

output:

4
1476
27
26
117970
2
105
30
4
737
4
2
19
48
34
434
6
78331
22
23
0
228
56
4
3
305
9
84
132
199
20
3
4057
0
0
20
35
34
48
4
266
14
17
4788
545
28989
0
10
535
84
1
1775
322
11
57
16
15
1331
5
0
10
5
183
8
2
237
10
0
60
20
42
7
10
297
14
210
6254
7
3
0
13
2744
119
47
0
1
68114
17
1
2
1
7
1
2
113
26
0
...

result:

ok 503 lines

Test #9:

score: 0
Accepted
time: 48ms
memory: 12708kb

input:

503
11
wkeoqqqpvmgdv
w
w
w
wkeoqqqpvmgdv
sgrwmsfwclpamgq
wkeoqqqpvm
qkmbyvcxjsh
wkeoqqqpvm
wke
wkeoqqqpvmgdv
7
otd
qelodfwrqeprgyvzbcjljx
qe
qelodfwrqeprgyvzbcjlj
qelodfwrqeprgyvzbcjlj
qelodfwrqeprgyvzbcjlj
c
15
rce
rce
fwq
fwqqfcjrhqot
rceft
jkdrcehfwhqkupe
fwq
r
jkdr
fwq
rceft
rce
fwqqfcjrhqot
fwq...

output:

156
17
213
12
20
1
374
4
0
26
26
3
122
30
4005
24
1385
50
84
44
0
112
42
36
19
887
99
5
9
13
2
5029
52
14
84
116
2
10
4
8
141
9287
822
37
5
13
25
1030
0
2
3
35
81
1
0
1
138
0
578
7
30
636
63
22
2118
863
5377
33
34
10
156
336
1
7
7
4
1793
2
124
13
4
2015
7
23
1
4516
3
17
6
35
13336
9
61
3093
0
1
7
22...

result:

ok 503 lines

Test #10:

score: 0
Accepted
time: 267ms
memory: 60152kb

input:

1003
3
mpfowyd
mpfowydrivrkjiarwcxwbfqvnktlzcfolbbsgelvcnzeqy
hytzojmfeiwtpquxhneeznbdjjlsptedaorwfsxi
3
nyfcq
nyfcqgrmshiwmgcbukozvetdggebkkychamof
nyfcqgrmshiwmgcbukozvetdggebkkychamofadozdympuejvhdnpi
8
yoeqyfcjsywowdrlzzybjvtycqvizzomc
zci
yoeqyfc
zcinc
yoeqyfcjsywowdrlzzybjvtycqvizzomc
y
zcinc
...

output:

0
1
26
10
66
403
1
265
1025
16
329
4
1219
1
10
70
30
182
60
5
71
1
20
5343
22328
40667
90
6983
66
10
35
20
250
307
913
98
44
5393
56
280
270
3
3
2229
77
17
774
50
5
21
0
208
8
14
185
35
20
11
465
132
176
10
0
10
1704
13
44
141
0
0
5
10
79
17
213
10
108
0
0
289
10
255
27
493
4
1
24
379
30
9
284
173
2...

result:

ok 1003 lines

Test #11:

score: 0
Accepted
time: 283ms
memory: 59932kb

input:

1003
6
exssl
exsslhsuwyemcafatpinzvdeypwjqsnvxlkvmpywgx
f
exss
exs
exsslhsuwyemcafatpinzvdeypwjqsnvxlkvmpywgx
7
hzzev
hzzevmltbehnvjfhsz
hzzevmltbe
hzzevmltbehnvjfhszqzobn
hzzevmltbehnvjf
hm
hzzevmltbehnvjfhszqzobn
9
rdx
rdxnxdfcyrdpgwzwtqgtu
rdx
rdxnxdfcyrdpgwzwtqgtu
f
kpotnxntufvd
kpotnxntufvdlmij...

output:

3
19
41
134
107
2
372
0
466
456
20
13
25
339
64
170
1
5
27295
3
1
221
116
11
29
19
1006
16827
16
19863
4
6
5784
3
20
21130
66
1275
100
731
83
3
84
0
32
3
615
207
8
44
245
48
165
18050
128
11
864
21
3
1221
120
51
21
8
247
302
0
1098
0
57
42
20
0
845
1
84
16
4
0
2
836
482
4
12
150
654
1035
142
291
34
...

result:

ok 1003 lines

Test #12:

score: 0
Accepted
time: 266ms
memory: 59148kb

input:

1003
10
lgbpleleme
u
u
uxpwzhga
uxpwzhg
u
uxpwzhgaadltqqpqkbteylath
u
uxpwzhgaadltqqpqkbteylath
uxpwzhgaadltqqpq
9
aqoxfsmqwpafbocodlpdykesadqgiggw
swzjus
oim
aqoxfsmq
aqoxfsmqwpafboc
swzju
nohnsjbdhljarh
swzjusx
aqoxf
20
mbdiqaartewavbbwbhftzwxm
k
mbdiqaartewavbbwbhftzwxm
kx
kxs
kxsqv
kx
kx
kxsqv
k...

output:

70
0
290
10
604
1770
2
913
1
165
16
316
4
169
26
3
36
2
1549
2
13
15
21
14
109
34
16
1889
132
1700
1
96
17
436
2
0
6183
4144
0
4
50
4
10
5
4
4
78
10
16
97
16
50204
15871
350
3
865
46
7
0
73
38
46
29
1946
65
22088
7
91
43
310
1806
0
50
4
17
38725
262
50
0
304
141
35
50
0
22760
2973
14
410
1112
20
703...

result:

ok 1003 lines

Test #13:

score: 0
Accepted
time: 262ms
memory: 59400kb

input:

1003
7
amhy
ncfsepqjimkaxkvlsqw
bgk
ncfsepqjim
n
amhyderccfrcdclbgrhxospemrlwctcnogb
ncfsepqjimkaxkvlsqwzxubaz
15
ul
k
cqm
kuixi
ovrwzbvkvkzfuqtxooevyvuayhupn
o
kuixi
ulihj
k
k
kzlmrtwddplvqvakmeda
ku
k
kzlmrtwddplvqvakmeda
k
15
mf
dwhth
cwkbrvykvcvqltdovbcy
dwhth
dwht
dwhth
cwkbrvykvcvqltdovbcy
dwh...

output:

4
58
203
10
8614
17
20
0
0
4
43987
18
164
144
35
412
3
19
20
51
50
0
4
16
37
1
4
14
8
526
197
71
20
26
20
35
55
16
0
3667
274
2024
4
33
19492
435
1
2
10
10
22631
32
690
1
0
13
166
561
6
67
10
33
286
4
1
89
11
18
12266
26
23
280
286
16
400
102
0
10
46
40
1
84
27
14
5699
105
197
39
818
36
6
29491
4
17...

result:

ok 1003 lines

Test #14:

score: 0
Accepted
time: 267ms
memory: 59288kb

input:

1003
36
dv
d
dvgsku
dv
d
d
dv
dv
d
d
dv
dvg
dvgs
dvgsku
dv
d
d
dv
d
d
nwitakortf
dv
dv
dvg
d
dvg
dv
d
tksvgjqlfzdolvno
d
d
dvg
dv
dv
dvgsku
dv
6
w
oursusfeydeqnv
wdrteonpibjzxvhzvqbytajwkgqwmucrzemrfowydhkkd
wdrteonpibjzxvhzvqb
wdrteo
wdrteo
11
crmoyb
c
crmo
wkyxgzsh
cr
flnsuvxkaqknoofhjdackgvavroh
...

output:

1840
19
9
370
7
31
892
504
6
56
150
209
41
0
255
221
1
7670
0
14
638
3
100
1365
17
3
20
16
74
20
15
496
3270
16
0
62
2
345
1
65
2277
0
1
39
0
0
1
2381
707
152
8485
289
109
2066
2803
38
197
1
46
38
44
323
14
1
10
98
2
116
38
82
0
56
2220
4
10
1879
29
241
65
17
7
10
6
8
162
20
9
2
10
4
4
0
4
76
50
194...

result:

ok 1003 lines

Test #15:

score: 0
Accepted
time: 254ms
memory: 48092kb

input:

1003
2
serwtujvdfqkirmfdetefaevwuuwqlkcmierfpxwzimcpmvdqvuwxwqtuq
serwtujvdfqkirmfdetefaevwuuwqlkc
6
cnbkhujgexqrjtbcqwncpeiyj
cnbkhujgexqrj
cnbkhujgexqrj
gisjwbxjohpnbvmtwvhhvb
c
cnbkhujgexqrjtbcqwncpeiyj
21
k
k
k
kpqon
k
aesamtzjajczokh
kpqonwvoiy
kpqonwv
kpqonwv
sbl
kpqonwvoiy
k
tdyvo
tdyvo
kpqon...

output:

0
4
199
4
199
16
650
1
506
9
0
12
81
4
1587
10
22
0
12383
436
29
152
61990
3
40
4
10
26
1
17
4
102
22
41
32
244
3
6486
1470
2
1425
22
5
2
321
5
70724
1023
7
41
15
7
10
5
11
0
186
34
7
7
4
5
0
1184
23
115
10
124
48
0
19104
969
1179
9
7
1
23042
809
100
86
18
4
1
27
77
84
0
30
1
0
6023
418
10
1
15
52
0...

result:

ok 1003 lines

Test #16:

score: 0
Accepted
time: 161ms
memory: 39812kb

input:

4
10000
aacbfedgih
aachgdeibf
aacbfedhgi
aabciedghf
aacbgeihfd
aacdgbhefi
aacgfeihdb
aabgfehidc
aabfgehdci
aabhdceigf
aacdebihfg
aabdgeihcf
aabgdcihfe
aaceibdgfh
aacdgehbif
aabfdicehg
aabhdfegic
aacfibgdeh
aacdfghieb
aabgdifhec
aabgdfhice
aachedbgif
aabdecgihf
aabdchefig
aacfgbeihd
aabdgfihce
aabehd...

output:

0
0
0
0

result:

ok 4 lines

Test #17:

score: 0
Accepted
time: 283ms
memory: 59948kb

input:

4
317
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

2600268
13538368
13577242
13530312

result:

ok 4 lines

Extra Test:

score: 0
Extra Test Passed