QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#673177#8647. JOI Tourhhoppitree30 1073ms66888kbC++176.0kb2024-10-24 20:53:592024-10-24 20:54:09

Judging History

你现在查看的是最新测评结果

  • [2024-10-24 20:54:09]
  • 评测
  • 测评结果:30
  • 用时:1073ms
  • 内存:66888kb
  • [2024-10-24 20:53:59]
  • 提交

answer

#include <bits/stdc++.h>
#include "joitour.h"

using namespace std;

const int N = 2e5 + 5;

int n, a[N];
vector<int> G[N];
long long S;
int dep[N], fa[N], siz[N], son[N], top[N], dfn[N];

void dfs1(int x) {
    siz[x] = 1;
    for (auto v : G[x]) {
        if (v == fa[x]) continue;
        fa[v] = x, dep[v] = dep[x] + 1;
        dfs1(v);
        siz[x] += siz[v];
        if (siz[v] > siz[son[x]]) son[x] = v;
    }
}

void dfs2(int x) {
    dfn[x] = ++dfn[0];
    if (!son[x]) return;
    int v = son[x];
    top[v] = top[x];
    dfs2(v);
    for (auto w : G[x]) {
        if (w == fa[x] || w == son[x]) continue;
        dfs2(top[w] = w);
    }
}

struct TreeArray {
    int s[N];

    void modify(int x, int y) {
        for (; x <= n; x += x & -x) s[x] += y;
    }

    int query(int x) {
        int res = 0;
        for (; x; x -= x & -x) res += s[x];
        return res;
    }

    int query(int l, int r) {
        return query(r) - query(l - 1);
    }
};

struct DS1 {
    TreeArray o[2];
    long long sum;
    int val[N];

    struct core {
        int cnt[1 << 19], val[1 << 19], lz[1 << 19];
        long long sum[1 << 19];

        void pushdown(int k) {
            if (lz[k]) {
                lz[k << 1] += lz[k], sum[k << 1] += 1ll * cnt[k << 1] * lz[k];
                lz[k << 1 | 1] += lz[k], sum[k << 1 | 1] += 1ll * cnt[k << 1 | 1] * lz[k];
                val[k << 1] += lz[k], val[k << 1 | 1] += lz[k];
                lz[k] = 0;
            }
        }

        void modify1(int k, int l, int r, int x, int y) {
            cnt[k] += y;
            if (l == r) {
                sum[k] = cnt[k] * val[k];
                return;
            }
            pushdown(k);
            int mid = (l + r) >> 1;
            if (x <= mid) modify1(k << 1, l, mid, x, y);
            else modify1(k << 1 | 1, mid + 1, r, x, y);
            sum[k] = sum[k << 1] + sum[k << 1 | 1];
        }

        void modify2(int k, int l, int r, int x, int y, int v) {
            if (l > y || r < x) return;
            if (l >= x && r <= y) {
                lz[k] += v, sum[k] += cnt[k] * v, val[k] += v;
                return;
            }
            pushdown(k);
            int mid = (l + r) >> 1;
            modify2(k << 1, l, mid, x, y, v);
            modify2(k << 1 | 1, mid + 1, r, x, y, v);
            sum[k] = sum[k << 1] + sum[k << 1 | 1];
        }

        long long query(int k, int l, int r, int x, int y) {
            if (l > y || r < x) return 0;
            if (l >= x && r <= y) return sum[k];
            pushdown(k);
            int mid = (l + r) >> 1;
            return query(k << 1, l, mid, x, y) + query(k << 1 | 1, mid + 1, r, x, y);
        }
    } dta;

    void modify0(int x, int y) {
        sum += y * o[0].query(dfn[x], dfn[x] + siz[x] - 1);
        o[1].modify(dfn[x], y);
        o[1].modify(dfn[x] + siz[x], -y);
        val[x] += y;
        dta.modify1(1, 1, n, dfn[x], y);
    }

    void modify1(int x, int y) {
        sum += y * o[1].query(1, dfn[x]);
        o[0].modify(dfn[x], y);
        while (x) {
            dta.modify2(1, 1, n, dfn[top[x]], dfn[x], y);
            if (x != 1) {
                dta.modify2(1, 1, n, max(dfn[top[x]] - 1, 1), dfn[x] - 1, y);
            }
            x = fa[top[x]];
        }
    }

    long long query(int x) {
        long long ans = sum;
        ans += 1ll * o[0].query(1, n) * o[1].query(1, dfn[x]);
        while (x) {
            if (x != top[x]) ans -= dta.query(1, 1, n, dfn[top[x]], dfn[x] - 1);
            if (val[fa[top[x]]]) {
                ans -= o[0].query(dfn[top[x]], dfn[top[x]] + siz[top[x]] - 1);
                ans -= o[0].query(dfn[fa[top[x]]], dfn[fa[top[x]]] + siz[fa[top[x]]] - 1);
            }
            x = fa[top[x]];
        }
        return ans;
    }
} d0, d2;

struct DS2 {
    TreeArray o[2];

    struct Core {
        long long res[N];
        int cnt[2][N];

        void modify(int ty, int x, int y) {
            while (x) {
                res[fa[top[x]]] -= 1ll * cnt[0][top[x]] * cnt[1][top[x]];
                cnt[ty][top[x]] += y;
                res[fa[top[x]]] += 1ll * cnt[0][top[x]] * cnt[1][top[x]];
                x = fa[top[x]];
            }
        }

        long long query(int x) {
            return res[x];
        }
    } dta;

    pair<int, int> get(int x) {
        return {o[0].query(dfn[x], dfn[x] + siz[x] - 1),
                o[1].query(dfn[x], dfn[x] + siz[x] - 1)};
    }

    void modify(int ty, int x, int y) {
        o[ty].modify(dfn[x], y);
        dta.modify(ty, x, y);
    }

    long long query(int x) {
        int tot0, tot1, inner0, inner1;
        tie(tot0, tot1) = get(1);
        tie(inner0, inner1) = get(x);
        long long res = 1ll * tot0 * tot1 - 1ll * (tot0 - inner0) * (tot1 - inner1);
        if (!son[x]) return res;
        int tct0, tct1;
        tie(tct0, tct1) = get(son[x]);
        res -= tct0 * tct1;
        res -= dta.query(x);
        return res;
    }
} d1;

void modify(int x, int y, int z) {
    if (y == 0) {
        S += z * d0.query(x);
        d1.modify(0, x, z);
        d2.modify1(x, z);
    } else if (y == 1) {
        S += z * d1.query(x);
        d0.modify0(x, z);
        d2.modify0(x, z);
    } else if (y == 2) {
        S += z * d2.query(x);
        d0.modify1(x, z);
        d1.modify(1, x, z);
    }
}

void init(int tn, vector<int> ta, vector<int> ox, vector<int> oy, int) {
    n = tn;
    for (int i = 1; i <= n; ++i) a[i] = ta[i - 1];
    for (int i = 1, x, y; i < n; ++i) {
        x = ox[i - 1] + 1, y = oy[i - 1] + 1;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs1(dep[1] = 1), dfs2(top[1] = 1);
    for (int i = 1; i <= n; ++i) {
        modify(i, a[i], 1);
    }
}

void change(int x, int y) {
    ++x;
    if (y == a[x]) return;
    modify(x, a[x], -1);
    a[x] = y;
    modify(x, a[x], 1);
}

long long num_tours() {
    return S;
}

詳細信息

Subtask #1:

score: 6
Accepted

Test #1:

score: 6
Accepted
time: 2ms
memory: 20960kb

input:

400
1 1 0 2 2 0 2 1 1 1 1 0 1 2 2 2 2 0 0 2 0 2 0 2 1 1 2 2 1 2 1 0 1 2 2 2 0 0 0 2 1 2 2 0 0 0 1 2 1 1 0 1 1 2 1 2 2 2 1 1 0 1 1 1 2 2 1 1 0 0 1 1 0 0 1 1 1 2 2 2 1 1 2 1 1 1 0 2 0 2 1 0 1 1 2 0 0 2 1 0 2 2 1 0 0 0 0 1 1 1 0 1 2 1 1 1 2 0 2 2 0 2 0 1 0 1 1 1 1 0 1 1 0 0 0 2 2 0 2 2 2 1 1 0 1 2 0 1 ...

output:

597892
604453
604236
600488
598028
594449
593671
586072
582432
581797
586919
588018
591441
592178
589303
587825
591777
595845
591906
591733
593937
592286
587593
583280
582383
580941
576582
577908
579779
578590
578141
577238
577854
584168
591759
594698
591476
590496
583825
582797
581264
586076
587779...

result:

ok 

Test #2:

score: 6
Accepted
time: 0ms
memory: 18212kb

input:

3
1 2 2
0 2
0 1
100
1 0
2 0
0 2
0 0
0 1
2 1
0 2
0 1
0 2
0 1
0 2
1 2
2 2
0 1
2 0
1 0
1 2
1 0
1 1
0 2
1 2
1 0
2 2
2 0
1 1
0 1
1 2
2 1
2 2
2 0
2 2
2 0
2 1
2 0
2 1
1 1
1 0
1 1
0 0
2 0
0 1
1 0
1 2
0 0
0 1
1 1
0 0
2 2
0 1
2 0
0 2
2 2
2 1
1 2
0 1
1 1
1 2
1 0
0 2
2 0
2 1
0 0
0 1
1 2
1 1
2 2
1 2
0 2
1 1
0 1
...

output:

0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
1
0
0
1
0
1
0
1
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 

Test #3:

score: 6
Accepted
time: 5ms
memory: 22320kb

input:

4
2 2 0 2
1 2
1 3
0 3
100
2 2
2 0
0 0
1 1
0 2
2 2
1 2
3 1
0 0
2 1
3 2
0 1
3 0
1 1
3 2
0 0
0 2
2 0
0 0
3 1
2 2
2 1
2 0
3 2
1 0
0 1
3 1
2 1
3 0
3 2
3 1
3 2
2 0
3 0
0 2
0 0
3 2
0 2
3 1
0 0
1 1
2 2
2 1
2 0
0 2
3 2
3 1
1 0
0 0
0 2
3 0
2 2
0 0
3 2
3 0
3 2
2 0
1 2
0 1
1 0
3 1
1 2
1 0
1 1
3 0
0 2
1 0
0 0
1 ...

output:

0
0
0
0
1
2
0
0
0
2
1
0
0
0
0
0
0
0
2
1
0
2
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
0
2
0
0
2
2
2
2
0
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
2
0
0
0
2
0
0
0
0
0
0
0
2
1
1
1
0
1
0
1
2
0
0
0
0
0
0
0
0
0

result:

ok 

Test #4:

score: 6
Accepted
time: 5ms
memory: 21728kb

input:

5
2 0 1 2 1
0 3
3 4
2 3
1 3
100
0 0
1 2
3 0
0 1
3 1
3 2
1 1
1 0
0 0
0 1
0 2
2 0
0 0
0 1
3 0
0 2
3 1
3 0
4 0
1 1
4 2
0 1
3 1
2 1
0 2
3 0
3 1
1 2
1 1
4 0
1 2
2 0
4 2
4 1
4 2
3 0
3 2
2 1
0 0
0 2
1 1
4 0
2 0
2 1
2 2
1 2
3 1
2 0
0 1
3 2
2 2
0 2
0 1
4 2
3 0
2 0
2 2
3 2
0 0
0 2
2 1
3 1
2 2
4 0
4 1
4 2
1 1
...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
0
0
0
0
1
0
0
0
0
0
0
1
2
4
3
2
3
0
0
0
0
0
0
0
0
0
0
0
3
4
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
0
0
0
0
0
0
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 

Test #5:

score: 6
Accepted
time: 0ms
memory: 20996kb

input:

6
0 0 0 0 0 2
2 4
4 5
0 4
2 3
1 5
100
5 1
3 1
4 1
0 2
2 2
2 0
5 2
4 0
2 2
1 2
4 2
0 1
3 0
4 0
0 2
3 1
4 1
4 0
4 1
0 0
3 2
2 1
2 2
3 1
3 0
1 0
4 2
0 1
5 0
3 1
2 0
2 1
0 2
5 2
1 2
5 1
1 0
2 0
3 0
4 0
1 2
3 2
2 1
5 0
0 1
4 2
4 1
0 0
2 0
3 0
3 2
3 0
5 2
3 2
0 1
0 0
5 0
1 1
4 2
5 1
3 1
2 2
0 2
2 1
1 0
1 ...

output:

0
0
0
0
3
4
3
3
0
0
0
0
0
0
0
0
0
0
0
0
3
4
4
4
3
5
4
0
0
0
0
0
0
0
0
0
0
2
2
2
1
3
2
2
2
2
1
2
5
4
3
4
3
6
5
2
5
4
2
0
0
0
0
0
0
2
0
1
2
2
1
2
4
2
1
2
4
2
1
2
2
3
5
2
4
0
2
2
0
0
0
1
2
1
0
0
0
0
0
3
2

result:

ok 

Test #6:

score: 6
Accepted
time: 2ms
memory: 20820kb

input:

400
1 1 1 0 0 0 1 1 2 1 1 1 1 1 1 0 2 2 1 0 1 0 2 0 1 2 2 1 1 2 2 1 2 0 2 0 2 0 0 0 0 2 1 2 1 0 2 0 1 0 1 0 1 0 1 1 1 1 0 0 0 1 1 1 1 1 2 1 2 0 0 2 1 1 1 2 2 0 0 0 2 2 1 1 1 2 1 1 0 1 0 0 2 1 2 1 2 0 0 2 0 2 1 2 1 1 0 2 2 2 1 1 0 2 0 0 0 1 2 2 1 2 1 0 2 0 0 1 0 0 0 1 2 0 2 1 0 0 0 0 1 1 2 1 1 0 1 0 ...

output:

89736
92089
97184
97881
97958
97957
98575
98780
98194
98636
98571
98118
98137
96880
97697
97751
97126
95885
95846
95881
95780
96554
97541
97088
97147
97124
97229
97271
97761
98723
98751
99213
99575
99558
99541
100018
99689
100639
100160
101057
98928
99588
98995
99010
98196
103072
103702
103678
10365...

result:

ok 

Test #7:

score: 6
Accepted
time: 4ms
memory: 18256kb

input:

400
1 1 0 2 2 0 2 1 1 1 1 0 1 2 2 2 2 0 0 2 0 2 0 2 1 1 2 2 1 2 1 0 1 2 2 2 0 0 0 2 1 2 2 0 0 0 1 2 1 1 0 1 1 2 1 2 2 2 1 1 0 1 1 1 2 2 1 1 0 0 1 1 0 0 1 1 1 2 2 2 1 1 2 1 1 1 0 2 0 2 1 0 1 1 2 0 0 2 1 0 2 2 1 0 0 0 0 1 1 1 0 1 2 1 1 1 2 0 2 2 0 2 0 1 0 1 1 1 1 0 1 1 0 0 0 2 2 0 2 2 2 1 1 0 1 2 0 1 ...

output:

17280
17415
17280
17408
17272
17145
17272
17136
17000
16988
17112
16988
16851
16974
17097
17080
17202
17324
17202
17324
17466
17324
17182
17061
16940
16920
16800
16660
16541
16520
16380
16356
16497
16638
16779
16660
16520
16497
16356
16497
16638
16520
16541
16560
16577
16714
16592
16605
16728
16740
...

result:

ok 

Subtask #2:

score: 8
Accepted

Dependency #1:

100%
Accepted

Test #8:

score: 8
Accepted
time: 7ms
memory: 23900kb

input:

4000
2 0 2 1 2 1 0 2 0 2 2 1 0 2 2 2 2 1 1 2 2 1 1 0 2 0 0 2 1 0 0 1 1 1 0 2 0 2 2 1 0 2 2 1 0 2 2 1 2 2 0 2 0 1 1 2 2 0 2 0 0 1 0 0 0 1 2 1 0 2 2 1 0 0 0 0 1 2 0 0 1 2 1 0 0 1 2 2 1 2 0 2 0 2 1 2 1 0 0 1 1 2 2 2 1 2 2 0 2 0 1 2 0 1 2 1 2 2 1 1 1 2 0 0 0 0 1 2 2 2 0 1 1 2 2 2 0 1 0 0 2 1 1 0 2 0 1 0...

output:

620474975
620091276
620213053
620215716
620182492
619967950
620433875
620378867
619791163
620294584
620042350
620254670
619599499
619635328
619632073
619845490
620198042
620214770
620452856
620637250
620099913
620537344
620561024
620602104
620531392
620536225
620559149
621081398
621137321
621348648
...

result:

ok 

Test #9:

score: 8
Accepted
time: 8ms
memory: 20808kb

input:

4000
0 1 1 2 1 2 1 2 2 2 0 0 2 1 2 1 1 0 0 2 0 0 2 0 2 1 2 1 0 2 2 1 2 0 2 1 0 1 2 1 1 0 0 0 0 1 2 0 1 2 0 1 2 2 1 2 1 2 1 1 0 0 0 0 1 0 0 0 2 2 1 2 2 0 0 1 0 1 1 0 1 1 0 0 1 1 1 1 0 0 0 2 0 0 0 2 1 1 2 0 0 0 0 0 0 0 2 0 1 1 1 2 2 2 1 2 0 1 0 2 0 0 1 2 0 2 1 0 0 1 0 2 2 0 0 0 1 0 1 0 0 2 2 1 2 0 0 0...

output:

42768942
42797072
42797223
42840318
42832995
42797246
42797380
42817147
42816920
42815937
42778805
42753526
42752585
42787135
42764416
42796136
42796797
42766303
42765309
42764279
42740223
42739766
42767580
43539681
43587532
43564273
43590474
43562674
43561503
43524119
43524798
43524001
43525085
435...

result:

ok 

Test #10:

score: 8
Accepted
time: 10ms
memory: 19940kb

input:

4000
2 0 2 1 2 1 0 2 0 2 2 1 0 2 2 2 2 1 1 2 2 1 1 0 2 0 0 2 1 0 0 1 1 1 0 2 0 2 2 1 0 2 2 1 0 2 2 1 2 2 0 2 0 1 1 2 2 0 2 0 0 1 0 0 0 1 2 1 0 2 2 1 0 0 0 0 1 2 0 0 1 2 1 0 0 1 2 2 1 2 0 2 0 2 1 2 1 0 0 1 1 2 2 2 1 2 2 0 2 0 1 2 0 1 2 1 2 2 1 1 1 2 0 0 0 0 1 2 2 2 0 1 1 2 2 2 0 1 0 0 2 1 1 0 2 0 1 0...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 

Subtask #3:

score: 0
Wrong Answer

Test #11:

score: 0
Wrong Answer
time: 321ms
memory: 60420kb

input:

200000
0 2 2 0 2 2 0 1 1 0 2 2 0 1 2 2 0 1 0 2 1 1 0 1 0 2 0 2 0 0 0 1 0 0 2 0 2 1 0 0 1 1 1 0 0 2 1 2 2 1 0 2 2 2 0 2 2 1 2 0 1 0 0 1 2 0 0 2 1 1 1 0 1 1 1 2 1 0 1 1 0 1 2 2 2 0 1 0 1 1 0 2 0 1 0 2 0 0 2 2 2 2 2 0 0 2 1 2 2 1 2 0 1 1 1 1 1 0 2 0 2 0 1 1 1 0 1 0 2 1 2 0 1 1 0 2 1 2 2 2 0 0 2 2 2 0 1...

output:

86337902438588

result:

wrong answer 

Subtask #4:

score: 0
Wrong Answer

Test #38:

score: 16
Accepted
time: 0ms
memory: 19116kb

input:

3
1 1 1
0 1
1 2
100
2 0
0 0
0 2
2 1
0 1
0 0
0 1
0 0
1 0
2 2
0 1
0 0
0 1
1 1
0 0
2 0
2 1
2 2
0 2
2 1
2 2
2 0
0 1
2 1
0 2
0 1
2 0
2 1
0 0
2 0
2 1
2 2
0 2
2 0
0 0
2 1
2 0
2 2
1 2
0 1
1 1
2 1
0 0
0 2
0 1
0 0
1 2
1 0
1 2
1 0
0 1
2 2
2 1
2 2
0 2
1 2
2 1
0 0
0 2
0 1
1 1
2 0
0 0
1 2
0 2
0 0
1 0
0 1
0 2
2 1
...

output:

0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0

result:

ok 

Test #39:

score: 16
Accepted
time: 5ms
memory: 18272kb

input:

4
2 2 2 0
0 1
1 2
2 3
100
0 0
3 2
1 1
3 1
0 2
2 0
1 0
3 0
0 1
1 2
0 0
3 2
3 1
1 0
3 2
3 0
3 1
1 2
3 2
0 1
2 2
2 1
1 0
1 1
1 0
3 0
0 2
1 2
0 0
3 1
1 0
2 0
3 0
2 2
3 2
0 2
0 1
3 1
2 1
3 0
1 2
2 2
3 2
2 1
1 1
3 1
1 2
2 0
0 2
1 1
0 1
3 0
2 2
0 2
0 0
1 0
3 1
2 1
0 2
2 2
0 0
0 1
3 0
2 1
1 2
3 1
3 2
1 1
2 ...

output:

0
0
0
2
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
1
2
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
1
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 

Test #40:

score: 16
Accepted
time: 0ms
memory: 19188kb

input:

5
0 1 0 2 1
0 1
1 2
2 3
3 4
100
1 0
4 2
3 1
2 2
2 0
4 1
1 2
3 0
3 2
3 1
1 0
1 2
2 2
4 2
1 1
4 0
2 0
0 2
2 1
0 1
3 2
1 0
4 1
3 0
4 0
3 2
2 0
0 0
2 1
0 2
0 1
4 1
3 0
0 2
4 2
2 0
2 1
4 0
1 2
4 1
1 0
3 2
0 0
2 0
2 2
4 2
3 1
3 0
0 2
1 2
0 0
2 1
3 2
2 0
2 2
0 1
2 0
3 1
0 0
4 0
2 2
1 0
2 1
3 2
4 2
1 1
4 1
...

output:

1
0
0
3
2
3
0
0
0
0
0
0
0
0
1
3
2
0
3
3
0
0
1
1
0
0
1
0
0
2
2
1
1
0
1
2
0
2
2
4
2
1
1
2
0
0
0
2
0
0
0
0
2
2
0
0
0
0
1
2
1
2
1
0
2
4
4
2
1
2
4
2
0
2
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
1
2
1
0
1
0
0
0
3
0
0
2

result:

ok 

Test #41:

score: 16
Accepted
time: 3ms
memory: 22588kb

input:

6
0 1 2 0 1 2
0 1
1 2
2 3
3 4
4 5
100
2 1
5 1
5 2
1 2
2 2
3 2
2 1
0 2
3 1
3 0
0 1
0 0
3 2
5 1
4 2
1 0
0 1
5 0
1 2
5 1
5 2
4 0
0 0
0 2
2 2
0 0
1 0
2 0
0 1
1 2
2 2
2 0
2 1
1 1
4 1
3 0
1 0
3 1
0 0
5 0
1 1
2 0
2 1
2 0
4 2
3 0
1 2
4 0
2 1
3 1
3 2
2 2
3 0
4 1
5 1
5 0
4 2
3 2
2 1
4 0
5 1
2 0
1 1
1 0
4 1
3 ...

output:

4
4
0
4
4
2
1
3
0
0
3
2
4
3
1
2
4
2
2
1
0
0
1
3
2
0
0
0
0
0
0
0
0
1
0
0
1
3
3
6
0
0
0
0
0
3
1
0
0
3
4
3
0
0
2
0
2
0
0
3
3
2
0
1
0
0
0
0
4
4
3
4
4
4
3
2
2
2
3
0
0
2
0
0
0
0
0
0
2
4
3
2
1
0
1
0
0
1
2
3
6

result:

ok 

Test #42:

score: 16
Accepted
time: 0ms
memory: 22992kb

input:

400
0 2 2 1 0 2 2 1 2 0 1 2 0 0 2 1 2 0 1 0 2 2 0 2 1 1 1 1 0 1 0 1 0 1 1 1 0 1 0 2 1 2 2 1 0 1 1 2 0 1 2 0 2 1 2 1 1 2 1 1 0 1 0 2 2 2 2 1 0 1 0 0 0 2 2 0 2 1 1 0 0 0 1 1 1 0 0 2 0 0 2 0 1 2 1 1 0 1 2 1 0 1 0 1 1 0 1 2 0 1 0 2 2 1 0 0 1 0 2 1 2 0 1 1 1 0 1 1 0 1 0 2 0 1 1 2 0 2 2 2 2 2 0 1 0 0 2 2 ...

output:

748492
751280
745592
746546
748685
749066
748286
746439
742602
741927
739801
738044
740003
732801
732137
732791
741037
740750
744502
744511
744015
746300
749460
745730
745106
751192
750538
754769
756253
757792
760457
756172
757024
761186
760814
761345
762058
764833
769148
767330
764502
764339
767930...

result:

ok 

Test #43:

score: 16
Accepted
time: 12ms
memory: 21292kb

input:

4000
1 1 1 2 0 2 2 1 1 2 0 1 0 1 2 0 1 1 1 1 1 0 0 0 2 2 1 2 2 0 1 2 0 0 2 0 1 0 2 1 2 0 0 0 0 2 0 2 2 1 0 2 2 2 2 1 0 2 1 0 1 1 2 1 0 0 0 2 1 1 0 1 0 1 2 2 2 1 0 1 2 0 2 2 1 2 1 0 1 1 0 1 0 0 2 0 2 2 1 0 1 2 0 2 1 1 0 2 1 2 2 0 0 0 1 2 0 2 1 2 0 0 2 1 1 2 1 1 0 2 1 0 2 0 1 1 0 0 0 0 2 0 2 1 2 0 0 2...

output:

791220194
791202818
791448703
790793734
790538710
790399232
790680228
790274544
789587326
789569532
789589951
789568904
789520169
789458372
789475557
788952064
788936826
788957112
788606079
788625706
788314564
788853784
788476658
788033878
787760817
787604725
787949498
787930696
787950912
787946164
...

result:

ok 

Test #44:

score: 16
Accepted
time: 170ms
memory: 66520kb

input:

200000
1 2 0 2 1 2 1 1 0 1 1 1 0 1 2 0 2 1 2 1 1 0 0 0 0 2 2 2 0 0 1 1 1 2 1 0 0 2 2 0 2 1 0 2 0 0 1 1 2 2 0 2 0 0 1 1 2 2 0 2 1 1 1 1 0 2 0 1 1 0 2 0 0 2 1 0 2 2 2 0 0 2 0 2 0 2 2 1 2 1 1 2 0 1 0 0 2 0 2 2 1 0 0 2 1 0 2 0 2 1 0 2 1 0 2 0 0 0 0 0 2 0 0 2 2 1 0 2 0 2 1 2 1 2 2 2 0 2 0 0 0 0 2 1 0 0 1...

output:

98878415111108

result:

ok 

Test #45:

score: 16
Accepted
time: 160ms
memory: 66520kb

input:

200000
1 2 2 1 2 2 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 2 2 2 1 2 1 1 2 2 1 1 2 1 1 1 1 2 2 2 2 1 2 2 1 2 2 1 2 2 2 2 1 1 2 2 1 2 1 2 2 1 1 2 2 1 1 1 2 1 2 2 1 2 2 1 2 2 2 2 2 2 1 0 1 1 1 2 2 1 0 2 1 2 2 2 1 1 1 2 1 2 2 2 2 2 2 2 1 2 2 1 1 1 1 0 1 1 1 2 1 2 2 1 1 1 2 2 2 2 1 1 2 2 2 1 2 1 1 1 1 1 2 2 2...

output:

18725807625786

result:

ok 

Test #46:

score: 16
Accepted
time: 162ms
memory: 66888kb

input:

200000
0 2 2 2 0 2 0 2 0 2 0 0 0 0 2 0 2 2 0 2 0 0 2 2 2 2 2 2 0 2 2 0 0 0 0 0 0 0 2 0 0 1 2 0 2 2 2 0 2 0 0 0 2 0 0 2 2 0 2 0 0 0 0 0 2 2 2 0 0 0 2 2 0 0 0 0 2 0 2 0 1 2 2 0 0 2 0 2 0 2 2 0 2 0 2 0 0 2 0 0 0 2 0 0 0 2 0 2 0 0 2 0 0 2 0 2 0 2 2 2 0 0 2 0 2 2 2 2 1 0 0 0 2 2 0 2 0 2 0 2 2 2 0 0 0 0 0...

output:

19001142419904

result:

ok 

Test #47:

score: 16
Accepted
time: 162ms
memory: 66532kb

input:

200000
0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 1 0 0 0 1 1 1 1 0 0 1 0 0 0 1 1 0 1 1 0 1 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 1 1 0 1 1 1 0 1 1 0 0 1 1 0 0 0 1 0 0 1 0 0 1 1 1 0 1 0 0 0 1 1 0 0 1 1 0 1 1 0 0 0 1 1 0 0 1 1 1 0 0 0 0 0 1 1 1 1 1 1 0 1 1 1 1 0 0 0 1 1 1 1 1 0 1 0 1 0 1 1 0 0 0 1 2 2 1 0 0 1 0 2 1 2 1 2...

output:

19038058071323

result:

ok 

Test #48:

score: 16
Accepted
time: 169ms
memory: 42096kb

input:

100000
0 2 1 1 0 2 0 0 2 2 2 2 0 0 1 1 0 2 2 2 0 2 1 2 1 0 2 0 0 2 0 1 0 1 2 0 0 2 2 1 0 2 2 1 0 2 1 0 2 1 2 0 2 0 1 2 1 0 2 0 1 0 1 0 0 0 0 2 1 2 0 1 1 0 1 0 0 2 2 0 2 1 0 2 2 1 2 0 1 0 2 1 2 0 2 0 0 0 0 2 1 1 0 1 1 2 2 1 2 0 1 1 1 1 0 0 2 2 2 2 2 2 0 2 2 1 0 1 0 0 1 0 0 1 1 2 1 1 2 1 1 0 1 1 2 0 0...

output:

12305851592762
12305852134900
12306133507778
12305866995960
12305585087263
12305866995960
12305585642746
12305866995960
12305585642746
12305866995960
12305585642746
12305583154618
12305582570257
12305583154618
12305864493268
12305582570257
12305583154618
12305864493268
12305863525808
12305581608077
...

result:

ok 

Test #49:

score: 16
Accepted
time: 149ms
memory: 44660kb

input:

100000
1 2 0 2 2 1 2 0 2 1 1 0 0 1 1 2 2 1 2 1 1 1 0 0 0 2 1 2 1 2 1 1 0 0 1 2 1 0 1 1 1 0 0 2 2 2 0 1 2 2 1 0 1 0 1 2 0 0 0 2 0 1 0 2 0 2 2 0 0 0 1 2 1 1 1 0 1 2 2 1 2 0 1 0 0 2 0 0 2 2 1 2 1 1 2 2 2 2 2 0 2 2 0 0 0 0 2 0 2 2 1 0 1 2 1 1 0 2 2 1 0 1 2 1 1 2 2 2 0 1 2 2 1 2 1 2 2 0 0 1 1 1 0 2 2 1 2...

output:

12301813256756
12302373157130
12301813256756
12302373157130
12302924262596
12302925522835
12302374383909
12302373157130
12301813256756
12302373157130
12302374383909
12301813256756
12302367485243
12302364362222
12302924262596
12302364362222
12302367485243
12301813256756
12302364362222
12302925522835
...

result:

ok 

Test #50:

score: 16
Accepted
time: 220ms
memory: 43736kb

input:

100000
2 2 2 2 1 0 2 1 2 1 1 2 0 1 1 2 1 1 0 2 1 0 1 1 1 1 1 1 0 0 0 0 1 2 1 2 0 1 0 2 0 2 0 1 0 1 2 1 0 1 1 1 2 0 1 0 0 2 0 0 1 2 1 0 1 2 1 1 2 2 2 1 1 0 1 2 1 0 0 0 0 0 0 0 0 2 1 1 2 0 0 0 0 0 1 1 1 2 0 2 1 2 1 1 1 0 2 1 0 1 0 0 2 2 2 2 2 2 1 0 2 2 0 2 2 0 0 1 2 2 0 2 1 2 1 1 2 1 2 1 1 2 2 1 2 1 0...

output:

12418513167989
12418318171086
12418165193041
12418160409001
12418126763330
12418040055626
12418267377528
12418272506223
12417820448436
12417972199669
12417773522932
12417576059620
12417757013704
12417825430253
12418053743032
12418508820771
12418503688442
12418439828326
12418689699116
12418838558201
...

result:

ok 

Test #51:

score: 16
Accepted
time: 171ms
memory: 46580kb

input:

100000
2 1 2 1 2 2 1 1 1 1 2 1 2 1 1 2 2 1 2 1 2 2 1 1 2 2 2 2 2 1 2 2 2 1 1 2 1 2 2 2 2 1 1 2 2 1 2 1 2 1 2 1 2 1 1 1 1 2 2 2 2 2 1 2 1 2 2 1 2 1 2 2 1 1 1 1 0 2 1 2 1 2 2 1 1 2 2 2 1 1 0 1 2 1 1 1 1 2 1 1 1 1 2 2 1 1 1 2 0 1 2 2 2 1 2 1 2 1 1 1 1 1 2 1 1 1 0 1 1 1 1 1 1 2 2 2 2 2 1 1 2 2 1 2 1 2 1...

output:

2346723587578
2346797006215
2346772375460
2346809727919
2347690734887
2347721226196
2347677034956
2347711403087
2347703419765
2347769503612
2347741902138
2348263987234
2348275750601
2348310490766
2348282698683
2348245269554
2348276304355
2348288123222
2348310435745
2348929711544
2348877359493
234885...

result:

ok 

Test #52:

score: 0
Wrong Answer
time: 174ms
memory: 47516kb

input:

100000
2 0 2 2 2 2 2 2 2 2 0 0 2 0 2 0 2 2 0 2 0 0 0 0 0 1 2 0 1 0 2 2 0 2 0 2 0 2 2 0 0 0 2 0 2 2 2 0 2 0 0 2 2 0 0 2 2 2 2 0 0 0 0 0 2 0 0 2 0 2 0 0 2 2 0 2 2 0 2 0 0 0 2 0 2 2 0 2 0 2 1 2 0 0 0 0 0 0 0 1 2 0 0 0 0 2 0 0 0 2 2 0 0 0 0 0 0 0 2 2 2 2 2 0 2 0 2 0 2 0 1 2 2 2 0 0 2 0 2 2 0 2 2 0 2 2 2...

output:

2400462386571
2400462158148
2400461544795
2400461889958
2400461185189
2400461548434
2400461920357
2400461234560
2400460695567
2400460511380
2400459879735
2400460424304
2400460567413
2400460041056
2400459736037
2400459512574
2400459660195
2400459345806
2404870317416
2404870914220
2404870346100
240486...

result:

wrong answer 

Subtask #5:

score: 16
Accepted

Test #60:

score: 16
Accepted
time: 0ms
memory: 22616kb

input:

3
2 0 0
0 1
0 2
100
0 1
2 2
2 1
1 1
0 0
2 2
1 2
0 2
0 1
0 0
0 1
0 2
2 1
1 0
2 2
2 0
0 0
0 2
1 1
1 2
2 2
2 1
0 0
2 2
0 1
1 0
0 0
2 0
1 1
1 0
2 1
2 0
0 2
0 1
2 2
1 1
0 0
0 1
2 1
0 0
2 0
0 1
2 1
2 0
0 2
2 2
0 1
2 0
0 0
0 1
2 1
0 2
0 1
0 2
2 2
1 0
1 1
1 2
1 0
1 2
1 0
0 0
1 1
0 1
1 0
2 0
1 2
1 0
0 2
0 0
...

output:

0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 

Test #61:

score: 16
Accepted
time: 0ms
memory: 21000kb

input:

4
1 0 1 0
0 1
0 2
1 3
100
0 2
3 2
1 1
0 1
3 1
3 2
3 1
2 2
1 2
2 1
1 0
2 2
3 2
3 1
1 1
3 2
2 0
3 1
0 2
1 2
2 1
2 2
0 1
1 0
3 0
3 2
3 1
3 0
0 0
2 0
1 1
1 2
0 1
1 0
2 2
2 1
1 1
3 2
0 0
2 2
0 1
3 1
1 0
2 1
2 0
1 2
0 2
3 0
3 1
0 1
0 2
3 2
3 1
1 1
1 0
2 2
0 0
0 1
0 0
0 1
0 0
2 0
0 1
3 2
0 2
3 0
2 2
2 1
3 ...

output:

0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
2
0
0
0
0
0
0
1
2
1
1
2
0
0
0
0
1
0
2
0
0
0
1
1
0
0
1
0
0
1
0
0
0
1
0
0
0
0
0
0
0
1
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
2
1
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 

Test #62:

score: 16
Accepted
time: 0ms
memory: 18136kb

input:

5
1 0 0 1 1
0 1
0 2
1 3
1 4
100
0 0
0 2
1 1
3 0
3 2
1 0
2 1
0 0
1 2
4 0
0 2
1 0
2 0
1 1
1 0
1 2
3 0
1 0
0 1
0 0
4 1
4 2
3 1
2 1
4 0
3 2
3 1
2 0
2 1
2 0
0 2
2 1
0 0
2 2
1 1
0 2
3 2
4 2
1 2
2 1
0 0
2 0
1 0
0 1
2 2
3 0
3 2
2 0
0 2
1 2
3 1
2 1
4 1
2 2
0 0
0 2
1 0
2 1
4 0
1 2
1 0
1 2
2 0
2 1
0 0
4 1
1 0
...

output:

0
0
0
0
1
1
0
0
0
0
0
0
0
0
3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
2
3
0
0
0
0
0
0
2
1
2
1
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
1
2
0
0
2
1
0
1
3
0
0
0
0
0
0
0
0
0
1
2
0

result:

ok 

Test #63:

score: 16
Accepted
time: 2ms
memory: 20236kb

input:

6
2 1 0 2 1 2
0 1
0 2
1 3
1 4
2 5
100
5 1
4 0
3 1
5 2
4 2
2 1
2 0
2 1
5 0
3 0
4 1
0 1
4 0
1 0
0 0
1 1
5 1
4 2
0 1
1 2
3 1
3 2
0 2
1 0
3 0
1 2
1 0
1 1
1 2
4 1
2 0
1 0
5 0
0 0
5 1
5 0
1 2
0 2
5 2
0 0
3 2
3 0
3 2
3 1
0 2
4 0
5 1
4 1
3 0
5 2
3 1
4 0
1 1
5 1
2 2
5 2
5 1
3 2
0 0
0 1
4 2
2 0
5 2
1 0
3 1
2 ...

output:

1
1
3
1
2
1
0
1
0
3
5
2
0
0
0
0
0
0
2
1
0
0
0
0
0
0
0
0
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
1
2
3
2
3
3
3
0
4
4
3
2
2
2
1
0
0
0
2
2
2
4
2
4
2
2
0
0
0
0
0
0
3
3
3
3
2
2
2
0
0
3
0
0
0
0
0

result:

ok 

Test #64:

score: 16
Accepted
time: 0ms
memory: 22676kb

input:

400
1 1 1 0 1 0 2 2 0 0 2 1 2 2 1 2 2 1 1 1 2 1 0 1 2 0 0 1 0 0 1 0 1 2 1 2 1 2 0 0 1 1 0 2 1 1 1 1 0 2 2 1 2 0 0 1 1 2 1 2 1 1 0 0 0 2 0 2 2 0 1 2 0 2 0 1 0 0 2 2 1 0 2 2 2 2 1 2 1 1 2 1 2 2 2 2 0 0 2 1 2 0 1 1 1 1 0 1 1 0 2 0 0 1 1 1 1 0 1 2 0 2 1 2 1 1 1 0 0 0 2 2 1 0 1 0 0 1 2 1 1 2 0 2 0 1 1 2 ...

output:

81027
81548
82381
82262
82052
81837
81658
81443
82127
81941
82560
80316
79750
80735
80890
73382
73536
73359
73138
72918
72653
71997
72478
72672
72911
72261
72853
73213
72954
73769
74787
74121
73931
71563
71778
70747
70281
70114
67043
66640
66415
65849
66006
66629
66799
66844
71682
71874
72971
72416
...

result:

ok 

Test #65:

score: 16
Accepted
time: 12ms
memory: 23160kb

input:

4000
1 1 1 0 1 1 0 2 1 1 2 1 2 2 1 0 1 2 2 0 1 1 1 1 2 0 1 1 0 0 2 0 1 1 2 2 2 2 1 1 1 1 0 0 1 2 0 1 0 2 1 2 2 1 2 0 1 2 0 0 0 1 1 0 1 2 1 1 1 1 0 1 0 1 1 2 1 1 0 1 1 0 0 2 2 0 1 0 0 1 1 2 0 0 1 0 0 1 0 0 2 0 2 2 1 1 2 0 2 1 2 2 0 1 1 1 1 1 1 1 0 2 0 2 0 1 1 1 1 1 1 0 0 0 1 2 1 2 0 0 0 0 1 1 2 0 0 0...

output:

14132542
14132780
14127197
14127091
14141758
14141687
14141782
14142021
14142204
14134941
14142824
14142974
14140574
14140667
14180192
14184660
14184584
14184417
14184136
14167667
14167744
14167912
14167710
14167788
14174353
14182082
14181898
14186831
14198546
14205957
14196800
14206231
14206053
141...

result:

ok 

Test #66:

score: 16
Accepted
time: 439ms
memory: 52860kb

input:

200000
0 1 1 2 2 0 2 2 0 2 0 2 1 1 2 1 1 0 1 1 1 2 1 1 0 1 1 0 2 2 1 0 1 0 1 0 0 1 2 1 1 0 0 1 1 1 1 0 2 0 2 1 0 2 2 0 2 0 0 1 1 1 2 1 0 0 1 0 2 2 2 1 1 2 1 0 0 1 0 2 1 0 1 1 1 2 1 0 1 1 2 2 2 1 2 2 0 1 1 1 2 0 0 2 0 1 0 1 0 2 0 2 1 2 2 1 0 0 0 2 1 2 0 0 1 2 2 1 1 1 0 0 1 2 2 2 2 0 0 1 1 0 1 0 1 2 2...

output:

44705759734

result:

ok 

Test #67:

score: 16
Accepted
time: 386ms
memory: 52872kb

input:

200000
1 1 2 1 2 0 2 2 1 2 1 2 1 2 2 2 2 2 2 2 1 1 1 1 2 2 1 1 2 1 1 2 2 2 2 1 2 1 2 1 1 1 1 1 0 2 2 1 1 2 1 1 1 2 1 1 1 1 2 1 1 1 0 1 2 1 2 2 2 1 1 2 1 1 1 2 2 2 1 1 2 1 2 2 2 1 1 2 2 1 2 1 1 1 0 0 1 2 1 1 2 0 1 1 1 1 2 1 1 1 2 1 1 1 1 1 1 1 1 2 2 1 1 1 2 2 1 2 1 1 2 2 1 1 1 2 2 2 2 1 1 2 1 2 2 1 0...

output:

8081399556

result:

ok 

Test #68:

score: 16
Accepted
time: 577ms
memory: 53172kb

input:

200000
0 2 2 0 2 2 2 2 2 2 0 2 0 2 0 0 0 0 2 0 0 0 2 0 0 2 1 2 0 2 0 0 0 2 0 0 2 0 2 2 2 2 2 0 0 2 1 0 0 2 2 2 2 0 0 2 2 0 2 0 2 2 0 2 0 2 2 0 0 0 0 2 2 2 2 2 0 2 0 0 2 2 2 0 2 2 0 2 0 0 2 0 2 2 2 0 2 2 0 2 0 2 0 2 2 0 0 2 0 2 2 0 0 0 0 2 2 2 0 2 0 2 2 0 1 0 0 0 0 0 2 0 0 0 2 1 0 0 2 2 2 2 2 0 2 2 1...

output:

7578518269

result:

ok 

Test #69:

score: 16
Accepted
time: 390ms
memory: 52620kb

input:

200000
1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 0 1 0 2 0 1 1 0 1 0 1 0 0 1 1 0 1 0 0 1 1 1 1 0 0 2 1 0 0 1 1 0 1 1 1 1 0 1 1 0 0 0 0 1 0 0 0 1 0 1 1 0 0 1 0 1 1 1 1 1 0 0 0 1 1 1 1 0 1 1 0 0 1 2 0 1 0 0 1 1 1 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 0 0 2 0 1 1 1 1 0 1 0 0 2 0 0 0 0 1 0 1 0 1 0...

output:

7842611505

result:

ok 

Test #70:

score: 16
Accepted
time: 321ms
memory: 38920kb

input:

100000
0 2 0 0 0 0 2 2 1 1 2 1 1 1 0 2 1 2 1 1 2 1 2 2 1 0 0 0 2 2 1 2 2 2 2 2 2 0 1 2 0 2 1 1 0 1 2 0 2 0 2 0 2 0 2 0 0 1 0 0 0 1 2 2 1 0 2 0 1 2 0 0 2 2 1 1 0 1 2 2 0 1 2 1 0 2 0 0 0 0 0 0 1 0 1 1 0 0 1 2 1 0 2 2 2 0 2 0 2 0 1 2 1 2 1 2 0 1 1 2 2 2 1 1 2 2 2 2 1 0 2 2 2 1 2 2 1 1 2 0 0 1 1 2 1 0 2...

output:

8821295872
8821296147
9564139052
8821295872
8821295681
9564138785
9564557503
9564371980
8821528877
8821295963
8821273000
8821273290
8821273000
9564071254
8821273290
9564071254
8821273000
8821273290
9564071254
8821273290
8820974722
9563750804
8820974722
8820974425
9563750804
8820974722
8821039686
882...

result:

ok 

Test #71:

score: 16
Accepted
time: 433ms
memory: 39344kb

input:

100000
1 0 2 1 0 2 2 0 2 2 2 2 2 0 2 1 1 0 1 1 1 1 0 1 2 1 1 2 2 2 2 2 0 1 1 2 1 1 2 0 1 1 1 1 2 0 0 1 2 0 2 0 1 2 2 1 2 2 2 2 1 2 0 2 2 0 1 1 1 1 2 0 1 1 1 2 1 1 0 2 2 2 1 1 0 2 2 1 2 2 1 2 1 2 1 1 2 0 1 1 2 1 2 1 1 1 2 0 1 2 0 1 0 2 0 0 2 2 0 0 1 1 2 0 1 1 1 1 1 0 0 2 1 2 2 0 1 1 0 0 2 1 2 2 0 0 0...

output:

9900828574
9901123105
9901558117
9901559863
9901561538
9901241053
9901243302
9900841539
9901073511
9900841551
9901224707
9900891827
9901193513
9901191456
9900859127
9900508225
9900868272
9900869818
9901103676
9901101160
9901405928
9901403850
9901736004
9902118965
9902402250
9902404114
9902169373
990...

result:

ok 

Test #72:

score: 16
Accepted
time: 416ms
memory: 36208kb

input:

100000
1 2 2 2 0 2 1 1 0 0 2 0 2 1 0 2 2 1 1 1 2 0 0 2 2 2 0 1 2 2 2 0 0 1 1 1 0 0 0 0 0 1 0 2 0 1 0 1 0 0 0 1 0 2 0 0 2 0 2 2 2 2 1 0 1 2 0 0 0 2 0 0 1 2 1 0 0 1 0 2 1 1 2 2 2 2 2 0 1 0 2 2 2 2 1 0 0 2 2 2 0 2 0 1 2 2 2 2 1 1 0 2 0 2 1 1 2 1 0 0 1 0 0 1 1 2 1 2 1 2 1 0 1 0 0 2 0 1 1 0 1 0 1 2 1 1 2...

output:

8866532903
8866266025
8866265404
8866264491
8865969722
8865968574
8865970233
8866204005
8865029098
8865196570
8865368030
8865370923
8865369538
8865168328
8865135093
8865385470
8865384250
8865383594
8865076149
8865313844
8865546375
8865244496
8864975343
8864974133
8864739724
8864740482
8864739477
886...

result:

ok 

Test #73:

score: 16
Accepted
time: 429ms
memory: 37544kb

input:

100000
1 2 2 0 1 1 2 1 2 1 1 2 2 1 1 1 1 1 1 1 1 1 1 2 1 2 1 1 2 2 1 2 1 2 2 2 1 2 2 2 1 1 1 2 2 1 1 1 1 1 1 2 2 2 0 2 1 1 2 1 2 2 2 2 1 2 2 2 2 2 1 1 1 1 2 2 2 1 1 1 2 1 1 1 1 2 1 2 2 2 1 1 1 1 1 1 2 1 1 1 2 1 2 2 1 2 2 1 1 2 2 1 2 1 1 1 2 2 2 1 1 2 0 1 2 1 2 2 2 1 1 2 2 1 1 1 2 1 2 2 1 1 1 1 1 2 2...

output:

1923134841
1923098761
1923068781
1923100856
1923136813
1923178461
1923151422
1923190446
1923139511
1923107348
1923142475
1923193068
1922471761
1922501746
1922531560
1922483959
1923074561
1923029924
1922988637
1923039300
1923012232
1923055404
1923709851
1924332573
1924291452
1924336408
1923841979
192...

result:

ok 

Test #74:

score: 16
Accepted
time: 474ms
memory: 37900kb

input:

100000
2 0 2 2 2 2 0 0 2 0 0 0 0 2 2 2 2 2 2 2 0 0 2 2 2 2 0 2 0 2 0 2 2 2 2 2 2 2 2 0 1 0 0 0 2 0 0 0 2 2 2 2 0 2 1 0 0 2 0 0 0 2 2 0 2 0 2 0 2 2 0 2 0 1 0 0 2 2 2 2 0 2 0 0 0 2 2 0 2 0 0 0 0 2 0 0 0 0 0 0 2 2 2 0 0 2 2 2 0 2 2 2 2 2 0 0 2 0 2 2 0 0 0 0 2 0 0 2 2 2 0 0 2 0 2 2 0 2 1 0 0 2 2 0 2 0 2...

output:

1525082875
1525082664
1525098402
1525098613
1525098402
1525098613
1525098666
1525098457
1530990775
1530990974
1530991108
1530990905
1530990702
1530990737
1530990721
1530990924
1530990945
1530990921
1531653395
1531653190
1531653395
1531653190
1531653147
1531653354
1531653381
1531653176
1531687363
153...

result:

ok 

Test #75:

score: 16
Accepted
time: 366ms
memory: 38016kb

input:

100000
0 1 0 1 1 1 1 1 1 0 0 1 1 1 0 0 1 1 1 0 1 0 0 0 0 1 0 1 1 1 1 0 0 1 0 0 0 1 1 1 1 1 0 0 1 0 0 1 0 1 0 1 0 1 1 0 1 1 1 0 1 1 2 1 0 0 0 1 1 0 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 0 0 1 1 1 0 0 1 1 0 0 0 2 1 1 1 0 1 1 1 0 0 1 1 1 1 1 1 0 1 1 1 0 0 0 1 1 0 1 1 0 0 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 0 1...

output:

2063072176
2063026328
2063571586
2064283826
2064244031
2064284088
2064324207
2063683556
2063638505
2063590631
2063627298
2063648635
2063605542
2063913146
2063956384
2063999436
2063960585
2063923816
2063883884
2063860177
2063893092
2063929914
2064077069
2064034617
2063988435
2064000191
2063960758
206...

result:

ok 

Test #76:

score: 16
Accepted
time: 691ms
memory: 53380kb

input:

200000
2 2 2 0 2 0 0 1 2 1 2 2 2 0 2 0 1 2 2 2 2 0 2 0 0 0 1 0 1 1 2 1 2 0 0 0 1 2 2 0 0 2 1 1 2 1 1 1 1 0 0 2 2 0 0 1 1 0 2 1 2 0 1 2 0 2 1 1 0 2 2 2 0 2 1 2 1 1 1 1 0 2 0 2 2 1 2 2 2 0 0 2 0 0 0 2 1 2 0 2 1 1 0 2 1 0 1 1 0 0 1 0 1 1 0 0 2 2 2 0 1 2 0 0 1 1 0 2 0 2 2 0 2 2 0 0 1 1 0 2 2 2 2 0 2 0 0...

output:

35803105614
38762344942
38761437962
35802153839
38761437962
38762063367
35802734800
35802734454
38762063367
35802734800
38762063367
38762064512
35802735377
38762064512
38762643916
35803270356
35803270016
38762643916
35803270016
35803268938
38762642614
35803268938
38762642614
35803269286
35803463662
...

result:

ok 

Test #77:

score: 16
Accepted
time: 971ms
memory: 52912kb

input:

200000
1 0 1 0 0 2 1 0 1 2 0 1 1 1 0 1 2 2 1 0 2 0 0 2 1 1 1 0 1 1 2 1 2 2 0 2 2 2 0 0 1 1 2 0 0 2 0 1 1 1 0 0 0 1 2 1 0 2 1 0 1 2 0 2 2 0 1 0 0 2 2 1 2 0 1 2 1 0 2 1 1 1 1 1 1 0 1 0 0 2 1 1 2 0 2 2 1 2 1 2 2 0 0 1 2 0 1 1 2 0 2 2 0 0 2 1 2 2 1 0 2 2 1 0 0 0 1 0 0 0 0 0 2 1 0 0 0 2 0 2 2 0 0 2 2 0 2...

output:

43444761896
43445433771
43445977597
43445201981
43445746105
43445006762
43445006666
43445724756
43445723551
43445121919
43445841023
43445839953
43445839539
43445839231
43446516618
43447290990
43448075191
43448075302
43447423180
43447834695
43447163589
43447706753
43447705667
43447704670
43446988668
...

result:

ok 

Test #78:

score: 16
Accepted
time: 950ms
memory: 53024kb

input:

200000
1 1 2 0 1 0 0 1 1 2 0 0 1 2 2 2 1 0 2 2 0 2 1 0 0 1 0 2 2 1 1 2 2 0 1 1 0 2 0 2 1 0 0 1 2 1 1 0 1 2 0 0 1 1 2 2 0 1 1 0 0 0 1 2 2 1 1 1 0 2 1 0 1 1 1 2 1 2 2 0 0 2 2 1 0 1 0 1 0 2 0 2 2 2 0 2 1 2 1 0 1 1 1 2 2 1 0 2 1 1 1 1 2 2 2 2 2 2 2 1 2 2 0 2 1 0 2 2 1 1 2 0 1 1 1 0 0 2 0 2 2 2 0 0 2 0 2...

output:

44897023717
44897026214
44896465355
44896591251
44896593006
44896590513
44895834212
44895368461
44894907040
44895640846
44895212634
44895677125
44894935040
44895723594
44896330327
44896326613
44896856238
44896170213
44895426076
44895423193
44895428090
44895426675
44895786854
44895241240
44894631441
...

result:

ok 

Test #79:

score: 16
Accepted
time: 828ms
memory: 52840kb

input:

200000
2 1 1 2 1 2 2 1 1 2 1 1 0 2 2 2 1 1 2 2 2 2 2 2 2 1 1 1 2 2 2 1 2 1 2 2 2 1 2 1 2 2 1 1 0 2 2 1 2 1 1 2 1 2 2 2 2 2 1 1 1 2 1 2 2 2 1 1 1 2 1 1 2 1 2 1 1 1 1 1 1 2 2 1 1 2 2 2 2 1 1 2 2 2 1 1 2 2 2 1 2 2 2 1 1 1 0 1 2 2 1 1 2 1 2 1 1 1 2 2 2 1 2 1 2 2 1 2 2 0 2 2 1 1 2 1 1 1 1 1 2 1 2 1 2 2 2...

output:

8101789485
8101739494
8103558728
8103498085
8103578182
8103664670
8103590427
8103512505
8103596589
8103555534
8103628457
8103701618
8103629649
8103726089
8103641305
8103685315
8104669426
8104768182
8104683042
8104599420
8104685426
8104775423
8104866920
8104042681
8103946158
8104045127
8103977963
810...

result:

ok 

Test #80:

score: 16
Accepted
time: 1073ms
memory: 52884kb

input:

200000
0 0 1 0 0 0 0 2 0 2 2 2 0 0 0 0 2 0 0 2 2 2 0 2 0 0 2 2 0 0 2 2 2 1 0 2 0 0 2 2 2 0 0 2 2 2 0 2 0 2 2 2 2 2 0 2 2 2 0 0 0 2 2 0 2 2 2 0 0 2 0 1 0 0 0 2 2 0 2 1 0 0 2 2 0 2 2 0 2 2 2 2 2 0 0 0 0 2 2 2 0 0 0 2 2 0 2 0 2 0 0 2 0 0 2 0 2 0 2 0 2 1 2 0 1 0 2 0 2 2 2 2 0 0 2 0 0 0 0 2 0 2 0 2 0 2 0...

output:

11328642689
11329157196
11329157389
11329157196
11329157003
11329157196
11329157033
11329157228
11329157389
11329157582
11329157338
11329157501
11329157338
11329157143
11329157593
11329157752
11329157481
11329157290
11329157455
11329157266
11329157433
11329157600
11329157785
11329157538
11329157701
...

result:

ok 

Test #81:

score: 16
Accepted
time: 835ms
memory: 53096kb

input:

200000
0 0 0 1 0 1 0 0 0 0 1 1 0 0 1 1 0 1 1 0 0 0 0 0 1 0 0 1 0 1 1 0 0 0 1 0 0 0 0 1 1 0 0 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 1 1 0 1 1 1 0 0 1 1 0 0 0 0 1 1 0 1 1 0 1 1 0 0 1 0 0 0 1 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 1 1 0 1 0 0 0 2 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 1 1 0 0 0 1 1 1 0...

output:

7202374285
7202488860
7202567943
7202610579
7202678643
7203651400
7203653724
7203779776
7203727143
7202795337
7202721296
7202788305
7203614354
7203691259
7203631682
7203564301
7203734098
7203722068
7203783310
7203872538
7203799847
7203858616
7203914809
7203824076
7203876720
7203805758
7203894616
720...

result:

ok 

Subtask #6:

score: 0
Wrong Answer

Dependency #2:

100%
Accepted

Test #82:

score: 34
Accepted
time: 243ms
memory: 39736kb

input:

100000
2 1 0 2 1 2 2 2 0 1 2 1 1 2 1 2 1 1 1 1 1 0 1 0 0 1 0 1 1 2 0 1 2 1 0 1 2 2 2 1 0 1 0 2 1 1 2 0 1 0 0 2 0 2 2 2 2 1 0 2 0 1 1 2 2 2 0 2 1 0 1 1 0 1 1 0 1 1 1 2 2 0 2 1 1 2 0 0 0 2 0 2 2 1 1 2 2 1 2 2 1 0 2 0 1 2 2 1 1 1 2 2 1 1 1 2 0 0 0 0 1 0 0 0 2 0 2 0 0 2 1 0 0 2 2 2 0 1 1 1 1 1 0 1 0 0 1...

output:

9559281849549
9558726709272
9558729881442
9559281849549
9558726709272
9559281849549
9558729881442
9559281849549
9558729881442
9559281849549
9558726709272
9559281849549
9559183715845
9558884413811
9558329259230
9558343181485
9558898362995
9558346366933
9558349676690
9558901679573
9558349676690
955890...

result:

ok 

Test #83:

score: 34
Accepted
time: 206ms
memory: 42136kb

input:

100000
0 0 1 1 1 2 1 0 1 1 0 2 1 1 1 1 0 0 0 2 1 0 1 2 0 2 0 0 0 2 2 0 2 0 1 1 1 0 2 0 2 1 1 2 1 1 0 0 2 1 0 2 2 1 0 1 1 0 0 2 1 2 0 2 2 1 2 0 2 1 0 2 2 1 0 1 0 1 2 0 0 1 1 2 0 0 0 2 1 2 1 2 0 0 1 2 0 1 2 1 1 1 0 0 1 0 1 2 1 0 2 0 2 2 0 2 0 1 1 1 2 1 1 0 1 0 1 0 0 1 1 1 1 0 2 1 0 0 2 2 2 2 1 1 1 2 1...

output:

9596047596512
9595616104943
9596053532037
9595619499659
9595182072565
9594755235780
9595189245987
9595616104943
9595622020637
9595188010430
9595625415285
9595192640635
9595619499659
9595613541827
9595619499659
9595192640635
9595625415285
9595619499659
9595182072565
9594755235780
9595192640635
959562...

result:

ok 

Test #84:

score: 34
Accepted
time: 242ms
memory: 38180kb

input:

100000
2 1 2 2 0 0 1 1 1 0 0 2 0 0 2 0 0 2 1 2 2 2 0 0 2 0 2 0 0 1 2 0 1 1 0 0 1 0 0 2 0 0 2 0 1 2 0 1 1 1 2 1 0 1 0 0 2 0 2 1 2 1 1 0 1 2 0 0 2 2 1 2 1 2 1 1 2 2 2 0 1 1 0 1 1 1 0 1 1 0 0 0 0 1 2 0 2 1 2 0 1 1 2 1 2 1 1 2 0 2 2 2 1 0 0 2 1 1 2 2 0 1 2 1 0 0 2 1 0 2 2 0 2 1 1 0 0 1 1 2 0 2 0 0 2 0 1...

output:

9622694298497
9622741686310
9622812806952
9622385374356
9622418884136
9622421503780
9622420867340
9622420434599
9622420218943
9622422748226
9622422450342
9622422397283
9622169880867
9621998244485
9622205951428
9622011532374
9621602858583
9621832212874
9621831997132
9621807638552
9621958911257
962181...

result:

ok 

Test #85:

score: 34
Accepted
time: 262ms
memory: 44028kb

input:

100000
2 2 1 1 2 1 1 1 1 2 1 1 1 2 1 2 1 2 1 2 2 1 2 2 2 1 2 1 1 1 1 2 2 2 2 2 1 1 1 2 1 1 2 1 1 2 2 1 2 1 2 2 2 1 1 2 1 2 1 2 2 1 2 1 2 1 1 1 1 2 1 1 1 2 1 2 2 1 1 2 2 1 1 1 1 1 2 2 2 1 2 2 1 2 2 2 2 1 1 2 2 1 0 2 2 1 2 2 2 1 2 1 1 2 2 2 1 2 2 1 1 1 2 2 2 1 2 2 2 2 2 1 2 2 1 1 1 1 0 1 1 2 1 1 1 1 1...

output:

1772658133910
1772639782734
1772648903878
1772618082106
1772649217472
1772697652664
1772731157534
1772763191996
1772788201196
1772800273408
1772798905708
1772762384054
1772809290010
1772773292125
1773433797235
1773430197860
1773394126747
1773373709629
1773409559971
1773427138827
1773429214543
177341...

result:

ok 

Test #86:

score: 0
Wrong Answer
time: 236ms
memory: 45152kb

input:

100000
2 2 0 0 0 0 0 0 2 0 2 2 2 0 0 0 0 2 0 0 0 2 0 2 0 0 2 2 2 0 2 2 0 1 2 2 2 2 0 0 2 2 2 2 0 2 0 2 0 2 2 0 0 0 2 2 0 0 2 0 2 2 2 2 2 2 0 0 0 2 2 0 0 0 0 0 0 2 2 2 0 0 0 0 0 0 2 0 2 0 0 2 0 2 0 0 0 0 2 2 2 2 2 0 2 2 2 1 2 2 0 0 2 0 2 0 0 0 0 0 0 0 0 0 0 0 2 2 2 2 0 0 2 2 2 2 0 0 0 2 2 0 2 2 2 2 2...

output:

1848048426618
1848048055088
1848047854878
1848048116999
1848048343733
1847202679200
1848223385989
1848223660206
1848223300531
1848223061452
1848222745270
1848965045086
1848964690052
1848964978358
1848965183224
1848965481126
1848965819718
1848965580392
1848965339494
1848965671252
1849877920206
184987...

result:

wrong answer 

Subtask #7:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

0%