QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#621465#9432. PermutationsupepapupuAC ✓212ms5948kbC++202.0kb2024-10-08 14:41:582024-10-08 14:42:28

Judging History

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

  • [2024-10-08 14:42:28]
  • 评测
  • 测评结果:AC
  • 用时:212ms
  • 内存:5948kb
  • [2024-10-08 14:41:58]
  • 提交

answer

#include <bits/stdc++.h>

#define x first
#define y second
#define el '\n'
#define debug(x) cerr << #x << ": " << x << endl
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 3e5 + 10, INF = 0x3f3f3f3f, mod = 998244353;

int n;
int fa[N], ans[N], id[N];
int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
mt19937 rng(0);

void work(int l, int r, vector<int> a) {
    assert(a.size() == r - l + 1);
    if (l == r) {
        ans[l] = a[0];
        return;
    }
    for (int i: a) fa[i] = i;
    shuffle(a.begin(), a.end(), rng);
    vector<int> b = a;
    int mid = l + r >> 1;
    vector<int> al, ar;
    while (a.size() >= 2) {
        int x = a.back(); a.pop_back();
        int y = a.back(); a.pop_back();
        cout << 0;
        for (int i = 1; i <= mid; ++i) cout << ' ' << x;
        for (int i = mid + 1; i <= n; ++i) cout << ' ' << y;
        cout << endl;
        int res; cin >> res;
        if (res == 0) al.emplace_back(y), ar.emplace_back(x), id[y] = 0, id[x] = 1;
        else if (res == 2) al.emplace_back(x), ar.emplace_back(y), id[x] = 0, id[y] = 1;
        else {
            fa[y] = x;
            a.emplace_back(x);
        }
    }
    for (int i: b) {
        if (find(i) != i) {
            if (a.size() && find(i) == a[0]) continue;
            if (id[find(i)] == 0) al.emplace_back(i);
            else ar.emplace_back(i);
        }
    }
    if (a.size()) {
        if (al.size() < mid - l + 1) {
            for (int i: b) 
                if (find(i) == a[0]) al.emplace_back(i);
        } else {
            for (int i: b) 
                if (find(i) == a[0]) ar.emplace_back(i);
        }
    }
    work(l, mid, al), work(mid + 1, r, ar);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    vector<int> a(n);
    iota(a.begin(), a.end(), 1);
    work(1, n, a);
    cout << 1;
    for (int i = 1; i <= n; ++i) {
        cout << ' ' << ans[i];
    }
    cout << endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5644kb

input:

5
2
2
1
2
2
0

output:

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

result:

ok Accepted

Test #2:

score: 0
Accepted
time: 184ms
memory: 5732kb

input:

1000
1
2
1
2
0
1
2
0
0
2
0
0
2
1
2
2
0
0
1
1
1
0
1
1
0
0
1
1
2
1
2
2
0
0
1
1
1
0
1
2
2
0
0
0
0
2
1
0
1
1
0
1
0
2
1
1
0
2
1
2
0
0
2
1
2
2
2
1
0
2
0
1
2
1
1
0
0
2
0
0
1
1
2
0
1
0
0
1
0
2
1
1
2
1
1
2
0
0
2
2
2
2
1
1
0
0
1
0
0
2
0
2
0
0
1
0
1
0
1
2
0
0
1
1
1
0
1
2
0
1
1
1
1
1
2
1
2
2
1
1
0
1
0
0
1
1
2
1...

output:

0 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 24...

result:

ok Accepted

Test #3:

score: 0
Accepted
time: 0ms
memory: 5616kb

input:

1

output:

1 1

result:

ok Accepted

Test #4:

score: 0
Accepted
time: 0ms
memory: 3548kb

input:

2
2

output:

0 2 1
1 2 1

result:

ok Accepted

Test #5:

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

input:

3
2
2

output:

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

result:

ok Accepted

Test #6:

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

input:

4
2
2
2
0

output:

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

result:

ok Accepted

Test #7:

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

input:

6
0
0
2
2
0
1
2
0

output:

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

result:

ok Accepted

Test #8:

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

input:

7
0
0
2
2
2
0
2
1
2
0

output:

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

result:

ok Accepted

Test #9:

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

input:

8
1
0
1
0
1
0
0
0
2
2
2
2
0

output:

0 8 8 8 8 5 5 5 5
0 8 8 8 8 7 7 7 7
0 4 4 4 4 6 6 6 6
0 4 4 4 4 2 2 2 2
0 3 3 3 3 1 1 1 1
0 1 1 3 3 3 3 3 3
0 2 2 7 7 7 7 7 7
0 7 3 3 3 3 3 3 3
0 2 2 2 1 1 1 1 1
0 5 5 5 5 5 5 8 8
0 6 6 6 6 6 6 4 4
0 6 6 6 6 6 5 5 5
0 8 8 8 8 8 8 8 4
1 3 7 2 1 6 5 4 8

result:

ok Accepted

Test #10:

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

input:

9
1
0
2
1
2
0
1
2
1
2
2
0
2
2
0
0

output:

0 8 8 8 8 8 4 4 4 4
0 8 8 8 8 8 9 9 9 9
0 2 2 2 2 2 6 6 6 6
0 1 1 1 1 1 7 7 7 7
0 1 1 1 1 1 5 5 5 5
0 9 9 9 7 7 7 7 7 7
0 3 3 3 2 2 2 2 2 2
0 3 3 3 1 1 1 1 1 1
0 7 7 3 3 3 3 3 3 3
0 7 7 2 2 2 2 2 2 2
0 3 7 7 7 7 7 7 7 7
0 9 9 9 9 1 1 1 1 1
0 4 4 4 4 4 4 4 6 6
0 5 5 5 5 5 5 5 8 8
0 4 4 4 4 4 4 5 5 5
...

result:

ok Accepted

Test #11:

score: 0
Accepted
time: 0ms
memory: 5704kb

input:

10
0
1
0
2
0
1
1
2
0
2
2
1
1
2
0
0
2

output:

0 4 4 4 4 4 7 7 7 7 7
0 8 8 8 8 8 5 5 5 5 5
0 8 8 8 8 8 9 9 9 9 9
0 10 10 10 10 10 6 6 6 6 6
0 2 2 2 2 2 3 3 3 3 3
0 7 7 7 10 10 10 10 10 10 10
0 7 7 7 3 3 3 3 3 3 3
0 7 7 7 9 9 9 9 9 9 9
0 10 10 3 3 3 3 3 3 3 3
0 3 7 7 7 7 7 7 7 7 7
0 1 1 1 1 9 9 9 9 9 9
0 4 4 4 4 4 4 4 4 8 8
0 4 4 4 4 4 4 4 4 5 5
...

result:

ok Accepted

Test #12:

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

input:

11
1
2
0
1
0
1
2
1
0
2
2
0
1
2
2
2
0
0
0
2

output:

0 3 3 3 3 3 3 9 9 9 9 9
0 3 3 3 3 3 3 8 8 8 8 8
0 4 4 4 4 4 4 10 10 10 10 10
0 2 2 2 2 2 2 6 6 6 6 6
0 2 2 2 2 2 2 1 1 1 1 1
0 7 7 7 7 7 7 5 5 5 5 5
0 7 7 7 7 7 7 11 11 11 11 11
0 1 1 1 5 5 5 5 5 5 5 5
0 1 1 1 10 10 10 10 10 10 10 10
0 7 7 7 9 9 9 9 9 9 9 9
0 3 3 10 10 10 10 10 10 10 10 10
0 7 3 3 3...

result:

ok Accepted

Test #13:

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

input:

12
2
0
0
0
1
0
0
0
2
0
0
1
2
2
1
2
2
2
0
0
0

output:

0 9 9 9 9 9 9 4 4 4 4 4 4
0 11 11 11 11 11 11 7 7 7 7 7 7
0 8 8 8 8 8 8 5 5 5 5 5 5
0 12 12 12 12 12 12 10 10 10 10 10 10
0 6 6 6 6 6 6 2 2 2 2 2 2
0 6 6 6 6 6 6 3 3 3 3 3 3
0 9 9 9 10 10 10 10 10 10 10 10 10
0 5 5 5 3 3 3 3 3 3 3 3 3
0 7 7 7 1 1 1 1 1 1 1 1 1
0 10 10 3 3 3 3 3 3 3 3 3 3
0 7 3 3 3 3...

result:

ok Accepted

Test #14:

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

input:

13
2
0
0
2
0
1
2
1
2
0
2
0
2
0
0
2
0
1
0
2
2
0
2
2

output:

0 1 1 1 1 1 1 1 3 3 3 3 3 3
0 12 12 12 12 12 12 12 9 9 9 9 9 9
0 8 8 8 8 8 8 8 4 4 4 4 4 4
0 10 10 10 10 10 10 10 2 2 2 2 2 2
0 6 6 6 6 6 6 6 13 13 13 13 13 13
0 7 7 7 7 7 7 7 5 5 5 5 5 5
0 7 7 7 7 7 7 7 11 11 11 11 11 11
0 10 10 10 10 1 1 1 1 1 1 1 1 1
0 10 10 10 10 9 9 9 9 9 9 9 9 9
0 5 5 5 5 7 7 ...

result:

ok Accepted

Test #15:

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

input:

14
1
0
2
1
2
0
1
0
0
0
1
2
0
2
2
0
2
2
2
0
1
2
1
0
2
0
2
0

output:

0 3 3 3 3 3 3 3 8 8 8 8 8 8 8
0 3 3 3 3 3 3 3 9 9 9 9 9 9 9
0 4 4 4 4 4 4 4 11 11 11 11 11 11 11
0 7 7 7 7 7 7 7 13 13 13 13 13 13 13
0 7 7 7 7 7 7 7 5 5 5 5 5 5 5
0 12 12 12 12 12 12 12 10 10 10 10 10 10 10
0 6 6 6 6 6 6 6 2 2 2 2 2 2 2
0 6 6 6 6 6 6 6 14 14 14 14 14 14 14
0 14 14 14 14 1 1 1 1 1 1...

result:

ok Accepted

Test #16:

score: 0
Accepted
time: 0ms
memory: 5864kb

input:

15
1
1
2
0
1
0
1
0
2
0
1
0
0
2
0
2
0
0
0
0
0
0
1
1
2
1
0
2
2
1
2
2

output:

0 9 9 9 9 9 9 9 9 4 4 4 4 4 4 4
0 9 9 9 9 9 9 9 9 1 1 1 1 1 1 1
0 9 9 9 9 9 9 9 9 3 3 3 3 3 3 3
0 12 12 12 12 12 12 12 12 15 15 15 15 15 15 15
0 8 8 8 8 8 8 8 8 14 14 14 14 14 14 14
0 8 8 8 8 8 8 8 8 10 10 10 10 10 10 10
0 2 2 2 2 2 2 2 2 6 6 6 6 6 6 6
0 2 2 2 2 2 2 2 2 13 13 13 13 13 13 13
0 7 7 7 ...

result:

ok Accepted

Test #17:

score: 0
Accepted
time: 188ms
memory: 3652kb

input:

975
1
2
0
1
1
1
1
0
0
2
1
1
1
0
0
0
2
1
2
0
2
0
1
2
2
0
0
2
1
1
2
2
0
2
2
2
0
2
0
0
1
0
1
2
1
0
1
0
0
0
2
1
2
1
0
1
2
0
1
1
1
0
1
0
1
2
1
1
2
1
0
1
1
1
1
1
1
2
1
1
2
1
1
2
2
1
1
1
0
0
0
1
1
1
1
2
1
0
0
2
1
1
0
2
1
1
1
1
2
0
1
1
1
0
2
1
1
1
1
2
1
0
2
1
1
2
0
0
0
0
2
0
1
0
2
2
2
1
1
0
1
2
1
1
1
0
1
0
...

output:

0 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 719 71...

result:

ok Accepted

Test #18:

score: 0
Accepted
time: 192ms
memory: 5928kb

input:

976
2
2
0
0
1
1
1
0
1
1
0
0
1
1
2
1
2
2
0
0
1
1
1
0
1
2
2
0
0
0
0
2
1
0
1
0
2
0
2
1
1
0
2
1
2
0
0
2
2
0
0
1
1
1
0
1
0
1
2
1
1
0
0
2
0
0
1
1
2
0
1
0
0
1
0
2
1
1
2
1
1
2
0
0
2
1
1
2
2
1
1
1
1
0
1
0
0
2
0
2
0
0
1
0
1
0
1
2
0
0
1
1
1
0
1
2
0
1
1
1
1
2
0
1
1
2
1
1
0
1
0
0
1
1
2
1
1
1
1
1
0
2
1
2
1
1
2
2
...

output:

0 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 12...

result:

ok Accepted

Test #19:

score: 0
Accepted
time: 165ms
memory: 5680kb

input:

977
1
0
2
0
1
1
1
1
0
0
2
1
1
1
0
0
0
2
1
2
0
2
0
1
2
2
0
0
2
1
1
2
2
0
2
2
2
0
2
0
0
1
0
1
2
1
0
1
0
0
0
2
1
2
1
0
1
2
0
1
1
1
0
1
0
1
2
1
1
2
1
0
1
1
1
1
1
1
2
1
1
2
1
1
2
2
1
1
1
0
0
0
1
1
1
1
2
1
0
0
2
1
1
0
2
1
1
1
1
2
0
1
1
1
0
2
1
1
1
1
2
1
0
2
1
1
2
0
0
0
0
2
0
1
0
2
2
2
1
1
0
1
2
1
1
1
0
1
...

output:

0 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 46...

result:

ok Accepted

Test #20:

score: 0
Accepted
time: 203ms
memory: 3880kb

input:

978
0
2
2
0
0
1
1
1
0
1
1
0
0
1
1
2
1
2
2
0
0
1
1
1
0
1
2
2
0
0
0
0
2
1
0
1
0
2
0
2
1
1
0
2
1
2
0
0
2
2
0
0
1
1
1
0
1
0
1
2
1
1
0
0
2
0
0
1
1
2
0
1
0
0
1
0
2
1
1
2
1
1
2
0
0
2
1
1
2
2
1
1
1
1
0
1
0
0
2
0
2
0
0
1
0
1
0
1
2
0
0
1
1
1
0
1
2
0
1
1
1
1
2
0
1
1
2
1
1
0
1
0
0
1
1
2
1
1
1
1
1
0
2
1
2
1
1
2
...

output:

0 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 222 22...

result:

ok Accepted

Test #21:

score: 0
Accepted
time: 197ms
memory: 5948kb

input:

979
2
1
0
2
0
1
1
1
1
0
0
2
1
1
1
0
0
0
2
1
2
0
2
0
1
2
2
0
0
2
1
1
2
2
0
2
2
2
0
2
0
0
1
0
1
2
1
0
1
0
0
0
2
1
2
1
0
1
2
0
1
1
1
0
1
0
1
2
1
1
2
1
0
1
1
1
1
1
1
2
1
1
2
1
1
2
2
1
1
1
0
0
0
1
1
1
1
2
1
0
0
2
1
1
0
2
1
1
1
1
2
0
1
1
1
0
2
1
1
1
1
2
1
0
2
1
1
2
0
0
0
0
2
0
1
0
2
2
2
1
1
0
1
2
1
1
1
0
...

output:

0 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 306 30...

result:

ok Accepted

Test #22:

score: 0
Accepted
time: 189ms
memory: 5676kb

input:

980
1
2
1
2
2
0
0
1
1
1
0
1
1
0
0
1
1
2
1
2
2
0
0
1
1
1
0
1
2
2
0
0
0
0
2
1
0
1
0
2
0
2
1
1
0
2
1
2
0
0
2
2
0
0
1
1
1
0
1
0
1
2
1
1
0
0
2
0
0
1
1
2
0
1
0
0
1
0
2
1
1
2
1
1
2
0
0
2
1
1
2
2
1
1
1
1
0
1
0
0
2
0
2
0
0
1
0
1
0
1
2
0
0
1
1
1
0
1
2
0
1
1
1
1
2
0
2
2
1
1
0
1
0
0
1
1
2
1
1
1
1
1
0
2
1
2
1
1
...

output:

0 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 700 70...

result:

ok Accepted

Test #23:

score: 0
Accepted
time: 193ms
memory: 3644kb

input:

981
1
0
1
1
0
2
0
0
1
1
0
0
2
1
1
1
0
0
0
2
1
2
0
2
0
1
2
2
0
0
2
1
1
2
2
0
2
2
2
0
2
0
0
1
0
1
2
1
0
1
0
0
0
2
1
2
1
0
1
2
0
1
1
1
0
1
0
1
2
1
1
2
1
0
0
1
1
1
1
2
1
1
2
1
1
2
2
1
1
1
0
0
0
1
1
1
1
2
1
0
0
2
1
1
0
2
1
1
1
1
2
0
1
1
1
0
2
1
1
1
1
2
1
0
2
1
1
2
0
0
0
0
2
0
1
0
2
2
2
1
1
0
1
2
1
1
1
0
...

output:

0 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 95...

result:

ok Accepted

Test #24:

score: 0
Accepted
time: 194ms
memory: 5744kb

input:

982
2
1
2
1
2
2
0
0
1
1
1
0
1
1
0
0
1
1
2
1
2
2
0
0
1
1
1
0
1
2
2
0
0
0
0
2
1
0
1
0
2
0
2
1
1
0
2
1
2
0
0
2
2
0
0
1
1
1
0
1
0
1
2
1
1
0
0
2
0
0
1
1
2
0
1
0
0
1
0
2
1
1
2
1
1
2
0
0
2
1
1
2
2
1
1
1
1
0
1
0
0
2
0
2
0
0
1
0
1
0
1
2
0
0
1
1
1
0
1
2
0
1
1
1
1
2
0
2
2
1
1
0
1
0
0
1
1
2
1
1
1
1
1
0
2
1
2
1
...

output:

0 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 854 85...

result:

ok Accepted

Test #25:

score: 0
Accepted
time: 208ms
memory: 5700kb

input:

983
0
1
0
1
1
0
2
0
0
1
1
0
0
2
1
1
1
0
0
0
2
1
2
0
2
0
1
2
2
0
0
2
1
1
2
2
0
2
2
2
0
2
0
0
1
0
1
2
1
0
1
0
0
0
2
1
2
1
0
1
2
0
1
1
1
0
1
0
1
2
1
1
2
1
0
0
1
1
1
1
2
1
1
2
1
1
2
2
1
1
1
0
0
0
1
1
1
1
2
1
0
0
2
1
1
0
2
1
1
1
1
2
0
1
1
1
0
2
1
1
1
1
2
1
0
2
1
1
2
0
0
0
0
2
0
1
0
2
2
2
1
1
0
1
2
1
1
1
...

output:

0 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 669 66...

result:

ok Accepted

Test #26:

score: 0
Accepted
time: 205ms
memory: 5908kb

input:

984
1
0
0
2
1
2
2
0
0
1
1
1
0
1
1
0
0
1
1
2
1
2
2
0
0
1
1
1
0
1
2
2
0
0
0
0
2
1
0
1
0
2
0
2
1
1
0
2
1
2
0
0
2
2
0
0
1
1
1
0
1
0
1
2
1
1
0
0
2
0
0
1
1
2
0
1
0
0
1
0
2
1
1
2
1
1
2
0
0
2
1
1
2
2
1
1
1
1
0
1
0
0
2
0
2
0
0
1
0
1
0
1
2
0
0
1
1
1
0
1
2
0
1
1
1
1
2
0
2
2
1
1
0
1
0
0
1
1
2
1
1
1
1
1
0
2
1
2
...

output:

0 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 47...

result:

ok Accepted

Test #27:

score: 0
Accepted
time: 182ms
memory: 5636kb

input:

985
1
2
2
0
1
1
0
2
0
0
1
1
0
0
1
1
1
1
1
0
0
0
2
1
2
0
2
0
1
2
2
0
0
2
1
1
2
2
0
2
2
2
0
2
0
0
1
0
1
2
1
0
1
0
0
0
2
1
2
1
0
1
2
0
1
1
1
0
1
0
1
2
1
1
2
1
0
0
1
1
1
1
2
1
1
2
1
1
2
2
1
1
1
0
0
0
1
1
1
1
2
1
0
0
2
1
1
0
2
1
1
1
1
2
0
1
1
1
0
2
1
1
1
1
2
1
0
2
1
1
2
0
0
0
0
2
0
1
0
2
2
2
1
1
0
1
2
1
...

output:

0 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 1...

result:

ok Accepted

Test #28:

score: 0
Accepted
time: 199ms
memory: 5740kb

input:

986
1
2
0
0
2
1
2
2
0
0
1
1
1
0
1
1
0
0
1
1
2
1
2
2
0
0
1
1
1
0
1
2
2
0
0
0
0
2
1
0
1
0
2
0
2
1
1
0
2
1
2
0
0
2
2
0
0
1
1
1
0
1
0
1
2
1
1
0
0
2
0
0
1
1
2
0
1
0
0
1
0
2
1
1
2
1
1
2
0
0
2
2
2
2
1
1
1
1
0
1
0
0
2
0
2
0
0
1
0
1
0
1
2
0
0
1
1
1
0
1
2
0
1
1
1
1
1
2
1
2
2
1
1
0
1
0
0
1
1
2
1
1
1
1
1
0
2
1
...

output:

0 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 69...

result:

ok Accepted

Test #29:

score: 0
Accepted
time: 205ms
memory: 5640kb

input:

987
0
1
2
2
0
1
1
1
0
1
0
0
1
1
0
0
1
1
1
1
1
0
0
0
2
1
2
0
2
0
1
2
2
0
0
2
1
1
2
2
0
2
2
2
0
2
0
0
1
0
1
2
1
0
1
0
0
0
2
1
2
1
0
1
2
0
1
1
1
0
1
0
1
2
1
1
2
1
0
0
1
1
1
1
2
1
1
2
1
1
2
2
1
1
1
0
0
0
1
1
1
1
2
1
0
0
2
1
1
0
2
1
1
1
1
2
0
1
1
1
0
2
1
1
1
1
2
1
0
2
1
1
2
0
0
0
0
2
0
1
0
2
2
2
1
1
0
1
...

output:

0 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 18...

result:

ok Accepted

Test #30:

score: 0
Accepted
time: 207ms
memory: 5740kb

input:

988
2
1
2
0
0
2
1
2
2
0
0
1
1
1
0
1
1
0
0
1
1
2
1
2
2
0
0
1
1
1
0
1
2
2
0
0
0
0
2
1
0
1
0
2
0
2
1
1
0
2
1
2
0
0
2
1
2
2
2
1
1
0
1
0
1
2
1
1
0
0
2
0
0
1
1
2
0
1
0
0
1
0
2
1
1
2
1
1
2
0
0
2
2
2
2
1
1
1
1
0
1
0
0
2
0
2
0
0
1
0
1
0
1
2
0
0
1
1
1
0
1
2
0
1
1
1
1
1
2
1
2
2
1
1
0
1
0
0
1
1
2
1
1
1
1
1
0
2
...

output:

0 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 158 15...

result:

ok Accepted

Test #31:

score: 0
Accepted
time: 176ms
memory: 5944kb

input:

989
0
0
1
2
2
0
1
1
1
0
1
0
0
1
1
0
0
1
1
1
1
1
0
0
0
2
1
2
0
2
0
1
2
2
0
0
2
1
1
2
2
0
2
2
2
0
2
0
0
1
0
1
2
1
0
1
0
0
0
2
1
2
1
0
1
2
0
1
1
1
0
1
0
1
2
1
1
2
1
0
0
1
1
1
1
2
1
1
2
1
1
2
2
1
1
1
0
0
0
1
2
1
2
1
0
0
2
1
1
0
2
1
1
1
1
2
0
1
1
1
0
2
1
1
1
1
2
1
0
2
1
1
2
0
0
0
0
2
0
1
0
2
2
2
1
1
0
1
...

output:

0 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 763 76...

result:

ok Accepted

Test #32:

score: 0
Accepted
time: 212ms
memory: 5688kb

input:

990
1
0
0
2
0
0
2
1
2
2
0
0
1
1
1
0
1
1
0
0
1
1
2
1
2
2
0
0
1
1
1
0
1
2
2
0
0
0
0
2
1
0
1
0
2
0
2
1
1
0
2
1
2
0
0
2
1
2
2
2
1
0
2
0
1
2
1
1
0
0
2
0
0
1
1
2
0
1
0
0
1
0
2
1
1
2
1
1
2
0
0
2
2
2
2
1
1
1
1
0
1
0
0
2
0
2
0
0
1
0
1
0
1
2
0
0
1
1
1
0
1
2
0
1
1
1
1
1
2
1
2
2
1
1
0
1
0
0
1
1
2
1
1
1
1
1
0
2
...

output:

0 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 583 58...

result:

ok Accepted

Test #33:

score: 0
Accepted
time: 190ms
memory: 5684kb

input:

991
2
0
0
1
2
2
0
1
1
1
0
1
0
0
1
1
0
0
1
1
1
1
1
0
0
0
2
1
2
0
2
0
1
2
2
0
0
2
1
1
2
2
0
2
2
2
0
2
0
0
1
0
1
2
1
0
1
0
0
0
2
1
2
1
0
1
2
0
1
1
1
0
1
0
1
2
1
1
2
1
0
0
1
1
1
1
2
1
1
2
1
1
2
2
1
1
1
0
0
0
1
2
1
2
1
0
0
2
1
1
0
2
1
1
1
1
2
0
1
1
1
0
2
1
1
1
1
2
1
0
2
1
1
2
0
0
0
0
2
0
1
0
2
2
2
1
1
0
...

output:

0 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 279 27...

result:

ok Accepted

Test #34:

score: 0
Accepted
time: 187ms
memory: 5740kb

input:

992
1
2
0
0
2
0
0
2
1
2
2
0
0
1
1
1
0
1
1
0
0
1
1
2
1
2
2
0
0
1
1
1
0
1
2
2
0
0
0
0
2
1
0
1
0
2
0
2
1
1
0
2
1
2
0
0
2
1
2
2
2
1
0
2
0
1
2
1
1
0
0
2
0
0
1
1
2
0
1
0
0
1
0
2
1
1
2
1
1
2
0
0
2
2
2
2
1
1
1
1
0
1
0
0
2
0
2
0
0
1
0
1
0
1
2
0
0
1
1
1
0
1
2
0
1
1
1
1
1
2
1
2
2
1
1
0
1
0
0
1
1
2
1
1
1
1
1
0
...

output:

0 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 63...

result:

ok Accepted

Test #35:

score: 0
Accepted
time: 177ms
memory: 5680kb

input:

993
1
1
2
0
0
1
2
2
0
1
1
1
0
1
0
0
1
1
0
0
1
1
1
1
1
0
0
0
2
1
2
1
1
2
0
1
2
2
0
0
2
1
1
2
2
0
2
2
2
0
2
0
0
1
0
1
2
1
0
1
0
0
0
2
1
2
1
0
1
2
0
1
1
1
0
1
0
1
2
1
1
2
1
0
0
1
1
1
1
2
1
1
2
1
1
2
2
1
1
1
0
0
0
1
2
1
2
1
0
0
2
1
1
0
2
1
1
1
1
2
0
1
1
1
0
2
1
1
1
1
2
1
0
2
1
1
2
0
0
0
0
2
0
1
0
2
2
2
...

output:

0 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 526 52...

result:

ok Accepted

Test #36:

score: 0
Accepted
time: 199ms
memory: 5712kb

input:

994
0
1
2
0
0
2
0
0
2
1
2
2
0
0
1
1
1
0
1
1
0
0
1
1
2
1
2
2
0
0
1
1
1
0
1
2
2
0
0
0
0
2
1
0
1
1
0
1
0
2
1
1
0
2
1
2
0
0
2
1
2
2
2
1
0
2
0
1
2
1
1
0
0
2
0
0
1
1
2
0
1
0
0
1
0
2
1
1
2
1
1
2
0
0
2
2
2
2
1
1
0
0
1
0
0
2
0
2
0
0
1
0
1
0
1
2
0
0
1
1
1
0
1
2
0
1
1
1
1
1
2
1
2
2
1
1
0
1
0
0
1
1
2
1
1
1
1
1
...

output:

0 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 616 61...

result:

ok Accepted

Test #37:

score: 0
Accepted
time: 187ms
memory: 5692kb

input:

995
1
1
1
1
2
0
0
1
2
2
0
1
1
1
1
1
1
0
0
1
1
0
0
1
1
1
1
1
0
0
0
2
1
2
1
1
2
0
1
2
2
0
0
2
1
1
2
2
0
2
2
2
0
2
0
0
1
0
1
2
1
0
1
0
0
0
2
1
2
1
0
1
2
0
1
1
1
0
1
0
1
2
1
1
2
1
0
0
1
1
1
1
2
1
1
2
1
1
2
2
1
1
1
0
0
0
1
2
1
2
1
0
0
2
1
1
0
2
1
1
1
1
2
0
1
1
1
0
2
1
1
1
1
2
1
0
2
1
1
2
0
0
0
0
2
0
1
0
...

output:

0 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 9...

result:

ok Accepted

Test #38:

score: 0
Accepted
time: 205ms
memory: 3648kb

input:

996
2
0
1
2
0
0
2
0
0
2
1
2
2
0
0
1
1
1
0
1
1
0
0
1
1
2
1
2
2
0
0
1
1
1
0
1
2
2
0
0
0
0
2
1
0
1
1
0
1
0
2
1
1
0
2
1
2
0
0
2
1
2
2
2
1
0
2
0
1
2
1
1
0
0
2
0
0
1
1
2
0
1
0
0
1
0
2
1
1
2
1
1
2
0
0
2
2
2
2
1
1
0
0
1
0
0
2
0
2
0
0
1
0
1
0
1
2
0
0
1
1
1
0
1
2
0
1
1
1
1
1
2
1
2
2
1
1
0
1
0
0
1
1
2
1
1
1
1
...

output:

0 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 303 30...

result:

ok Accepted

Test #39:

score: 0
Accepted
time: 203ms
memory: 3656kb

input:

997
2
1
1
1
1
2
0
0
1
2
2
0
1
1
1
1
1
1
0
0
1
1
0
0
1
1
1
1
1
0
0
0
2
1
2
1
1
2
0
1
2
2
0
0
2
1
1
2
2
0
2
2
2
0
2
0
0
1
0
1
2
1
0
1
0
0
0
2
1
2
1
0
1
2
0
1
1
1
0
1
0
1
2
1
1
2
1
0
0
1
1
1
1
2
1
1
2
1
1
2
2
1
1
1
0
0
0
1
2
1
2
1
0
0
2
1
1
0
2
1
1
1
1
2
0
1
1
1
0
2
1
1
1
1
2
1
0
2
1
1
2
0
0
0
0
2
0
1
...

output:

0 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 16...

result:

ok Accepted

Test #40:

score: 0
Accepted
time: 202ms
memory: 3948kb

input:

998
0
2
0
1
2
0
0
2
0
0
2
1
2
2
0
0
1
1
1
0
1
1
0
0
1
1
2
1
2
2
0
0
1
1
1
0
1
2
2
0
0
0
0
2
1
0
1
1
0
1
0
2
1
1
0
2
1
2
0
0
2
1
2
2
2
1
0
2
0
1
2
1
1
0
0
2
0
0
1
1
2
0
1
0
0
1
0
2
1
1
2
1
1
2
0
0
2
2
2
2
1
1
0
0
1
0
0
2
0
2
0
0
1
0
1
0
1
2
0
0
1
1
1
0
1
2
0
1
1
1
1
1
2
1
2
2
1
1
0
1
0
0
1
1
2
1
1
1
...

output:

0 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 11...

result:

ok Accepted

Test #41:

score: 0
Accepted
time: 200ms
memory: 3712kb

input:

999
2
2
1
1
1
1
2
0
0
1
2
2
0
1
1
1
1
1
1
0
0
1
1
0
0
1
1
1
1
1
0
0
0
2
1
2
1
1
2
0
1
2
2
0
0
2
1
1
2
2
0
2
2
2
0
2
0
0
1
0
1
2
1
0
1
0
0
0
2
1
2
1
0
1
2
0
1
1
1
0
1
0
1
2
1
1
2
1
0
0
1
1
1
1
2
1
1
2
1
1
2
2
1
1
1
0
0
0
1
2
1
2
1
0
0
2
1
1
0
2
1
1
1
1
2
0
1
1
1
0
2
1
1
1
1
2
1
0
2
1
1
2
0
0
0
0
2
0
...

output:

0 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 14...

result:

ok Accepted

Extra Test:

score: 0
Extra Test Passed