QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#787547#1133. Monster Game_8_8_100 ✓26ms8024kbC++173.1kb2024-11-27 12:41:532024-11-27 12:41:53

Judging History

This is the latest submission verdict.

  • [2024-11-27 12:41:53]
  • Judged
  • Verdict: 100
  • Time: 26ms
  • Memory: 8024kb
  • [2024-11-27 12:41:53]
  • Submitted

answer

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

using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int mem[1001][1001];
int qr(int x, int y) {
    if(mem[x][y] != -1) return mem[x][y];
    int k = Query(x, y);
    mem[x][y] = k;
    mem[y][x] = 1 - k;
    return k;
}

vector<int> sor(vector<int> x) {
    if((int)x.size() == 1) return x;
    if(x.empty()) return x;
    int mid = (int)x.size() / 2;
    vector<int> l, r;
    for(int i = 0; i < (int)x.size(); i++) {
        if(i < mid) {
            l.push_back(x[i]);
        } else {
            r.push_back(x[i]);
        }
    }
    x.clear();
    l = sor(l);
    r = sor(r);
    int _l = 0, _r = 0;
    int L = (int)l.size(), R = (int)r.size();
    while(_l < L || _r < R) {
        if(_l == L) {
            x.push_back(r[_r]);
            _r++;
        } else if(_r == R) {
            x.push_back(l[_l]);
            _l++;
        } else {
            if(qr(l[_l], r[_r])) {
                x.push_back(r[_r]);
                _r++;
            } else {
                x.push_back(l[_l]);
                _l++;
            }
        }
    }
    return x;
}
vector<int> Solve(int N) {
    memset(mem, -1, sizeof(mem));
    vector<int> a(N), res(N);
    iota(a.begin(), a.end(), 0);
    // shuffle(a.begin(), a.end(), rng);
    // for(int i = 1; i < min(N, 10); i += 2) {
    //     qr(a[i], a[i - 1]);
    // }
    shuffle(a.begin(), a.end(), rng);
    a = sor(a);
    int i = 0;
    auto calc = [&](vector<int> x, int v) {
        int ret = 0;
        for(int i : x) if(i != v) {
            if(qr(v, i)) {
                ret++;
            }
        }
        return ret;
    };
    while(i < N - 1) {
        int val;
        if(!i) {
            vector<int> x;
            vector<pair<int, int>> y;
            for(int j = i; j < min(N, i + 10); j++) {
                x.push_back(a[j]);
            }
            for(int j : x) {
                y.emplace_back(calc(x, j), j);
            }
            sort(y.begin(), y.end());
            val = y[0].second;
            if(y[1].first == 1 && qr(y[1].second, y[0].second)) {
                val = y[1].second;
            }
            if((int)y.size() > 2 && y[2].first == 1) {
                if(qr(a[i - 1], y[0].second)) {
                    val = y[0].second;
                } else if(qr(a[i - 1], y[1].second)) {
                    val = y[1].second;
                } else {
                    val = y[2].second;
                }
            }
        } else {
            for(int j = i; j < min(N, i + 10); j++) {
                if(qr(a[i - 1], a[j])) {
                    val = a[j];
                    break;
                }
            }
        }
        for(int j = i; j < N; j++) {
            if(a[j] == val) {
                reverse(a.begin() + i, a.begin() + j + 1);
                i = j + 1;
                break;
            }
        }
    } 

    for(int i = 0; i < N; i++) {
        res[a[i]] = i;
    }
    return res;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 0ms
memory: 7780kb

input:

4
1
1
1
0
1
1

output:

Q 0 2
Q 3 1
Q 2 1
Q 2 3
Q 0 3
Q 1 0
F 4
 2 1 0 3

result:

points 1.0 points  1.0

Test #2:

score: 10
Accepted
time: 1ms
memory: 7764kb

input:

4
1
1
0
1
0
1

output:

Q 3 0
Q 1 2
Q 0 2
Q 3 2
Q 3 1
Q 0 1
F 4
 1 2 0 3

result:

points 1.0 points  1.0

Test #3:

score: 10
Accepted
time: 2ms
memory: 7708kb

input:

4
1
0
0
0
1
0

output:

Q 1 2
Q 0 3
Q 2 0
Q 1 0
Q 2 3
Q 1 3
F 4
 3 0 1 2

result:

points 1.0 points  1.0

Test #4:

score: 10
Accepted
time: 1ms
memory: 7704kb

input:

5
0
1
0
0
1
0
0
1
0
1

output:

Q 1 3
Q 0 2
Q 4 2
Q 1 4
Q 3 4
Q 3 2
Q 1 2
Q 1 0
Q 4 0
Q 3 0
F 5
 2 1 3 4 0

result:

points 1.0 points  1.0

Test #5:

score: 10
Accepted
time: 1ms
memory: 7704kb

input:

5
0
0
0
0
0
0
1
0
0
1

output:

Q 1 2
Q 0 3
Q 4 0
Q 1 4
Q 2 4
Q 1 0
Q 1 3
Q 2 0
Q 2 3
Q 4 3
F 5
 3 1 0 2 4

result:

points 1.0 points  1.0

Test #6:

score: 10
Accepted
time: 1ms
memory: 8000kb

input:

5
0
0
1
0
0
1
1
0
1
1

output:

Q 0 1
Q 4 2
Q 3 4
Q 3 2
Q 0 4
Q 1 4
Q 1 3
Q 1 2
Q 0 3
Q 0 2
F 5
 2 4 3 0 1

result:

points 1.0 points  1.0

Test #7:

score: 10
Accepted
time: 2ms
memory: 7692kb

input:

6
1
1
0
0
1
1
0
1
0
1
0
1
0
0
1

output:

Q 3 2
Q 0 2
Q 0 3
Q 4 5
Q 1 4
Q 1 5
Q 2 4
Q 0 4
Q 0 5
Q 3 5
Q 3 1
Q 2 5
Q 2 1
Q 4 3
Q 0 1
F 6
 3 4 1 5 0 2

result:

points 1.0 points  1.0

Test #8:

score: 10
Accepted
time: 0ms
memory: 7760kb

input:

6
1
1
0
0
1
1
0
1
1
1
1
1
0
0
1

output:

Q 2 3
Q 1 3
Q 1 2
Q 0 5
Q 4 0
Q 4 5
Q 3 0
Q 1 0
Q 1 5
Q 1 4
Q 3 5
Q 3 4
Q 0 2
Q 5 2
Q 4 2
F 6
 1 5 4 2 3 0

result:

points 1.0 points  1.0

Test #9:

score: 10
Accepted
time: 0ms
memory: 7768kb

input:

6
1
1
1
1
1
1
1
0
1
0
1
1
0
0
1

output:

Q 3 5
Q 4 5
Q 4 3
Q 1 2
Q 0 2
Q 0 1
Q 5 2
Q 5 1
Q 3 1
Q 3 0
Q 4 0
Q 2 3
Q 2 4
Q 5 0
Q 1 4
F 6
 5 3 1 2 4 0

result:

points 1.0 points  1.0

Test #10:

score: 10
Accepted
time: 2ms
memory: 7692kb

input:

7
0
1
0
0
1
1
0
0
0
0
1
1
1
0
0
1
0
1
1
1
1

output:

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

result:

points 1.0 points  1.0

Test #11:

score: 10
Accepted
time: 0ms
memory: 7652kb

input:

7
1
0
1
1
0
1
1
0
1
0
1
0
1
0
0
0
0
0
0
1
1

output:

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

result:

points 1.0 points  1.0

Test #12:

score: 10
Accepted
time: 2ms
memory: 7672kb

input:

7
1
1
1
0
1
1
1
1
0
0
1
1
0
1
0
0
0
0
1
0
1

output:

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

result:

points 1.0 points  1.0

Test #13:

score: 10
Accepted
time: 2ms
memory: 7956kb

input:

8
0
1
1
0
1
1
1
0
1
1
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
1
1

output:

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

result:

points 1.0 points  1.0

Test #14:

score: 10
Accepted
time: 2ms
memory: 7780kb

input:

8
1
0
1
0
1
0
1
1
0
0
0
0
1
1
1
1
1
0
0
0
1
1
0
0
0
0
1
1

output:

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

result:

points 1.0 points  1.0

Test #15:

score: 10
Accepted
time: 1ms
memory: 7844kb

input:

8
1
0
1
1
1
1
1
1
1
0
0
0
1
0
0
1
0
0
0
0
0
1
0
0
0
0
1
0

output:

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

result:

points 1.0 points  1.0

Test #16:

score: 10
Accepted
time: 0ms
memory: 7964kb

input:

198
0
1
1
0
1
1
0
0
1
0
1
1
0
1
1
0
1
1
0
0
0
1
1
0
0
0
0
1
1
1
0
1
0
0
1
0
1
1
1
0
1
1
0
0
1
0
0
0
0
0
0
0
1
1
1
1
1
0
0
1
0
0
1
0
1
0
0
0
1
0
1
1
1
0
1
0
1
0
0
1
1
0
1
0
1
1
0
0
1
0
1
1
1
1
1
1
0
0
1
1
1
0
0
1
1
1
1
0
1
0
0
0
0
1
1
0
0
1
0
0
0
0
1
1
1
1
1
0
1
0
1
0
1
0
0
1
1
1
1
0
0
1
1
0
1
1
0
1
...

output:

Q 149 178
Q 191 149
Q 191 178
Q 88 90
Q 165 88
Q 165 90
Q 149 88
Q 178 88
Q 191 88
Q 191 90
Q 71 26
Q 40 26
Q 40 71
Q 47 31
Q 72 31
Q 72 47
Q 26 31
Q 26 72
Q 26 47
Q 40 47
Q 71 47
Q 149 31
Q 149 72
Q 149 26
Q 178 26
Q 88 26
Q 191 26
Q 90 26
Q 90 40
Q 90 71
Q 90 47
Q 165 47
Q 173 48
Q 78 173
Q 118 63...

result:

points 1.0 points  1.0

Test #17:

score: 10
Accepted
time: 4ms
memory: 7712kb

input:

199
1
0
0
1
1
1
0
1
1
1
1
0
0
0
1
0
0
1
0
1
1
0
0
1
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
1
1
1
1
0
1
1
1
1
0
0
1
0
0
1
0
0
0
1
0
1
0
1
0
0
0
1
1
0
0
1
0
1
0
1
1
1
1
1
1
0
0
1
1
1
1
0
0
0
0
0
0
0
1
0
0
1
1
0
0
1
1
1
1
0
1
0
0
1
1
0
1
0
0
1
0
1
1
1
1
0
0
0
1
0
1
1
1
0
0
0
1
0
0
1
1
0
0
1
1
0
1
0
1
1
1
0
1
...

output:

Q 75 67
Q 181 67
Q 168 146
Q 97 168
Q 97 146
Q 181 168
Q 181 146
Q 67 146
Q 67 97
Q 70 5
Q 31 5
Q 31 70
Q 111 60
Q 189 111
Q 5 189
Q 5 111
Q 31 111
Q 70 111
Q 70 60
Q 168 189
Q 168 5
Q 168 31
Q 181 31
Q 146 31
Q 146 111
Q 146 70
Q 97 70
Q 67 70
Q 75 70
Q 98 13
Q 150 98
Q 185 172
Q 46 185
Q 150 46
Q ...

result:

points 1.0 points  1.0

Test #18:

score: 10
Accepted
time: 7ms
memory: 7852kb

input:

200
0
1
1
1
1
0
1
0
1
1
1
1
0
0
0
0
1
0
1
0
0
0
1
1
1
0
1
1
0
0
1
0
0
1
0
1
1
0
1
1
1
1
0
1
1
0
1
1
1
0
1
0
0
0
1
1
0
0
1
1
1
0
1
0
1
0
1
0
1
0
1
1
0
1
1
1
1
0
1
0
0
0
1
0
1
1
1
0
0
1
0
0
0
1
1
1
1
1
1
1
0
1
0
1
0
1
1
0
0
0
0
1
1
1
0
0
1
1
0
0
0
1
1
0
0
0
0
1
1
0
0
1
1
1
1
0
0
1
0
1
1
1
1
1
0
0
1
0
...

output:

Q 173 97
Q 74 173
Q 74 97
Q 71 73
Q 178 73
Q 178 71
Q 173 73
Q 173 178
Q 97 178
Q 97 71
Q 18 114
Q 139 114
Q 139 18
Q 185 0
Q 44 185
Q 114 44
Q 139 44
Q 139 185
Q 18 185
Q 18 0
Q 73 114
Q 173 114
Q 178 114
Q 178 44
Q 178 139
Q 178 185
Q 71 185
Q 71 18
Q 71 0
Q 97 0
Q 74 0
Q 95 103
Q 92 95
Q 17 187
Q...

result:

points 1.0 points  1.0

Test #19:

score: 10
Accepted
time: 0ms
memory: 7708kb

input:

200
0
1
1
0
1
1
0
0
1
0
1
0
0
1
1
1
0
0
0
0
1
1
0
1
0
0
1
1
0
0
1
0
1
0
1
0
0
0
0
1
0
1
1
1
1
0
1
1
0
1
0
1
1
1
0
0
0
0
1
0
1
1
0
0
0
1
1
0
0
0
0
1
1
0
1
1
1
1
1
0
1
0
1
1
0
0
0
1
1
0
1
1
0
1
1
1
1
1
1
1
1
1
0
1
1
1
1
0
1
1
0
0
1
1
0
0
0
1
1
0
1
1
0
0
0
1
0
0
1
0
1
0
1
0
0
1
0
0
1
0
0
0
1
1
0
1
1
1
...

output:

Q 161 77
Q 160 161
Q 160 77
Q 50 19
Q 145 50
Q 145 19
Q 161 50
Q 77 50
Q 160 50
Q 160 19
Q 61 182
Q 124 182
Q 16 114
Q 95 16
Q 95 114
Q 124 16
Q 124 114
Q 182 114
Q 61 114
Q 161 16
Q 77 16
Q 77 124
Q 77 182
Q 50 182
Q 50 61
Q 160 61
Q 19 61
Q 19 114
Q 19 95
Q 145 95
Q 27 131
Q 10 131
Q 168 60
Q 102 ...

result:

points 1.0 points  1.0

Test #20:

score: 10
Accepted
time: 4ms
memory: 7712kb

input:

200
0
0
0
1
1
0
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
0
0
1
1
1
1
1
0
0
0
1
0
1
1
0
0
0
1
0
1
1
0
1
1
1
1
1
0
1
1
1
1
0
1
0
1
1
1
0
1
1
0
1
1
0
1
0
1
1
1
0
0
0
1
1
0
1
1
1
1
1
1
0
1
0
0
1
0
1
0
0
1
1
0
0
0
0
1
0
0
1
0
0
0
1
1
1
0
1
1
1
0
1
1
1
1
0
0
0
0
1
0
1
0
1
0
0
1
1
0
0
1
0
1
1
0
1
1
0
0
0
1
1
0
0
1
0
...

output:

Q 158 11
Q 19 158
Q 189 92
Q 113 189
Q 113 92
Q 19 189
Q 158 189
Q 158 92
Q 158 113
Q 11 113
Q 192 83
Q 112 83
Q 112 192
Q 60 37
Q 1 60
Q 1 37
Q 83 60
Q 112 60
Q 112 37
Q 192 37
Q 192 1
Q 19 83
Q 189 83
Q 92 83
Q 92 60
Q 92 112
Q 92 37
Q 92 192
Q 92 1
Q 158 1
Q 11 1
Q 113 1
Q 109 74
Q 196 109
Q 196 ...

result:

points 1.0 points  1.0

Test #21:

score: 10
Accepted
time: 2ms
memory: 7768kb

input:

4
1
0
0
0
1
0

output:

Q 0 1
Q 3 2
Q 1 3
Q 0 3
Q 1 2
Q 0 2
F 4
 0 1 2 3

result:

points 1.0 points  1.0

Test #22:

score: 10
Accepted
time: 2ms
memory: 7988kb

input:

5
1
1
1
0
1
0
0
1
1
0

output:

Q 1 2
Q 3 0
Q 4 0
Q 4 3
Q 2 0
Q 2 4
Q 1 4
Q 0 1
Q 2 3
Q 1 3
F 5
 0 1 2 3 4

result:

points 1.0 points  1.0

Test #23:

score: 10
Accepted
time: 2ms
memory: 7992kb

input:

6
1
1
1
0
0
1
1
1
0
1
0
0
0
1
1

output:

Q 2 3
Q 5 3
Q 5 2
Q 0 4
Q 1 0
Q 3 1
Q 3 0
Q 3 4
Q 1 4
Q 1 2
Q 1 5
Q 0 2
Q 0 5
Q 4 2
Q 4 5
F 6
 0 1 2 3 4 5

result:

points 1.0 points  1.0

Test #24:

score: 10
Accepted
time: 2ms
memory: 7992kb

input:

7
1
1
1
0
0
0
1
0
0
1
0
1
1
0
0
1
0
0
0
1
1

output:

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

result:

points 1.0 points  1.0

Test #25:

score: 10
Accepted
time: 2ms
memory: 7704kb

input:

8
0
0
0
1
1
0
1
0
1
0
0
0
1
1
1
1
1
0
0
0
1
1
0
0
0
0
1
1

output:

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

result:

points 1.0 points  1.0

Test #26:

score: 10
Accepted
time: 7ms
memory: 7992kb

input:

200
0
1
1
1
1
1
1
1
0
0
1
1
1
0
1
1
1
0
1
1
1
1
0
1
0
0
1
0
1
1
1
0
1
0
0
0
1
0
0
1
0
1
1
1
1
0
1
1
1
0
0
1
1
0
0
1
0
1
1
0
0
1
1
1
0
1
1
0
1
0
0
1
0
1
0
1
1
0
1
0
1
1
1
0
1
1
1
1
1
1
0
0
0
0
1
1
0
0
1
1
0
0
0
1
1
1
0
1
1
1
0
0
0
0
1
0
1
1
0
1
0
0
1
0
1
1
1
0
0
0
1
1
1
0
1
0
1
1
0
0
1
1
0
0
0
1
1
1
...

output:

Q 55 85
Q 199 55
Q 199 85
Q 50 33
Q 195 33
Q 195 50
Q 55 33
Q 55 50
Q 55 195
Q 85 195
Q 199 195
Q 166 8
Q 141 8
Q 141 166
Q 63 40
Q 104 40
Q 104 63
Q 8 40
Q 141 40
Q 141 63
Q 141 104
Q 33 8
Q 33 40
Q 50 40
Q 50 63
Q 55 63
Q 85 63
Q 85 104
Q 195 104
Q 195 141
Q 195 166
Q 39 109
Q 61 39
Q 61 109
Q 78 ...

result:

points 1.0 points  1.0

Test #27:

score: 10
Accepted
time: 2ms
memory: 7708kb

input:

4
1
0
0
0
1
0

output:

Q 3 2
Q 0 1
Q 2 0
Q 3 0
Q 2 1
Q 3 1
F 4
 3 2 1 0

result:

points 1.0 points  1.0

Test #28:

score: 10
Accepted
time: 0ms
memory: 7988kb

input:

5
0
1
1
1
1
0
0
1
0
1

output:

Q 4 2
Q 0 3
Q 1 3
Q 1 0
Q 4 3
Q 4 0
Q 2 0
Q 3 2
Q 4 1
Q 2 1
F 5
 4 3 2 1 0

result:

points 1.0 points  1.0

Test #29:

score: 10
Accepted
time: 0ms
memory: 7692kb

input:

6
0
0
1
0
0
1
1
1
1
1
0
0
0
0
1

output:

Q 0 1
Q 3 0
Q 2 5
Q 4 5
Q 3 4
Q 0 4
Q 0 5
Q 0 2
Q 3 5
Q 3 2
Q 3 1
Q 4 2
Q 4 1
Q 5 1
Q 2 1
F 6
 5 4 3 2 1 0

result:

points 1.0 points  1.0

Test #30:

score: 10
Accepted
time: 0ms
memory: 7924kb

input:

7
0
1
0
1
0
0
1
1
0
1
0
1
1
0
0
1
0
0
0
1
1

output:

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

result:

points 1.0 points  1.0

Test #31:

score: 10
Accepted
time: 2ms
memory: 7720kb

input:

8
1
0
1
0
0
0
0
0
1
1
0
1
1
0
0
0
1
0
0
0
0
0
0
1
0
1
0
1

output:

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

result:

points 1.0 points  1.0

Test #32:

score: 10
Accepted
time: 0ms
memory: 7708kb

input:

200
0
1
0
1
1
1
1
0
0
1
0
0
0
1
1
0
1
0
1
0
0
0
1
0
0
0
0
1
1
1
1
0
1
0
1
1
1
0
0
1
0
1
1
0
1
1
1
1
1
1
0
0
1
1
0
1
1
1
0
0
1
0
1
1
1
0
1
1
1
1
0
1
1
1
0
0
0
1
1
0
0
0
0
0
0
1
1
1
1
0
1
0
0
0
1
1
0
0
1
1
1
0
0
1
1
1
0
0
1
1
1
0
0
0
0
1
1
1
0
1
0
0
1
0
1
1
1
0
0
1
1
1
1
1
0
1
1
0
1
1
1
0
1
0
1
0
0
1
...

output:

Q 104 78
Q 94 104
Q 94 78
Q 91 186
Q 47 186
Q 47 91
Q 104 186
Q 104 91
Q 94 91
Q 78 91
Q 78 47
Q 53 49
Q 79 53
Q 5 140
Q 76 140
Q 76 5
Q 79 140
Q 79 76
Q 53 76
Q 53 5
Q 49 5
Q 186 140
Q 104 140
Q 104 79
Q 94 79
Q 91 79
Q 78 79
Q 47 79
Q 47 76
Q 47 53
Q 47 49
Q 47 5
Q 89 137
Q 182 137
Q 18 121
Q 14 1...

result:

points 1.0 points  1.0

Subtask #2:

score: 15
Accepted

Test #33:

score: 15
Accepted
time: 3ms
memory: 7788kb

input:

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

output:

Q 36 952
Q 393 36
Q 393 952
Q 260 727
Q 753 768
Q 260 768
Q 727 768
Q 727 753
Q 36 260
Q 36 768
Q 36 753
Q 36 727
Q 393 727
Q 952 727
Q 140 875
Q 591 197
Q 140 591
Q 875 591
Q 875 197
Q 940 497
Q 639 616
Q 940 616
Q 940 639
Q 140 616
Q 140 639
Q 140 940
Q 591 940
Q 197 940
Q 875 940
Q 875 497
Q 260 ...

result:

points 1.0 points  1.0

Test #34:

score: 15
Accepted
time: 17ms
memory: 7696kb

input:

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

output:

Q 760 866
Q 976 866
Q 976 760
Q 311 298
Q 314 354
Q 311 354
Q 311 314
Q 298 314
Q 866 354
Q 976 354
Q 760 354
Q 760 311
Q 760 314
Q 760 298
Q 649 625
Q 902 24
Q 649 24
Q 649 902
Q 625 902
Q 926 164
Q 212 17
Q 926 212
Q 164 212
Q 24 926
Q 24 164
Q 649 164
Q 649 212
Q 649 17
Q 625 17
Q 902 17
Q 866 92...

result:

points 1.0 points  1.0

Test #35:

score: 15
Accepted
time: 0ms
memory: 7796kb

input:

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

output:

Q 99 879
Q 434 99
Q 936 720
Q 940 971
Q 720 971
Q 720 940
Q 434 971
Q 434 940
Q 434 720
Q 99 720
Q 879 720
Q 879 936
Q 754 923
Q 213 166
Q 923 166
Q 754 166
Q 816 544
Q 29 974
Q 816 29
Q 816 974
Q 544 974
Q 923 29
Q 923 816
Q 754 816
Q 754 544
Q 166 544
Q 213 544
Q 971 29
Q 971 923
Q 940 923
Q 940 8...

result:

points 1.0 points  1.0

Test #36:

score: 15
Accepted
time: 17ms
memory: 7716kb

input:

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

output:

Q 514 118
Q 333 118
Q 773 445
Q 460 184
Q 773 460
Q 445 460
Q 333 773
Q 333 445
Q 118 445
Q 514 445
Q 514 460
Q 807 670
Q 256 85
Q 807 85
Q 670 85
Q 670 256
Q 67 692
Q 663 474
Q 692 474
Q 67 474
Q 67 663
Q 807 692
Q 85 692
Q 670 692
Q 670 474
Q 670 663
Q 256 663
Q 773 807
Q 773 85
Q 333 85
Q 118 85
...

result:

points 1.0 points  1.0

Test #37:

score: 15
Accepted
time: 6ms
memory: 7780kb

input:

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

output:

Q 165 524
Q 210 524
Q 210 165
Q 882 282
Q 657 480
Q 882 657
Q 282 657
Q 524 882
Q 524 282
Q 210 282
Q 210 657
Q 165 657
Q 165 480
Q 186 72
Q 15 528
Q 186 528
Q 72 528
Q 977 214
Q 150 742
Q 977 150
Q 977 742
Q 214 742
Q 186 150
Q 186 977
Q 186 742
Q 72 742
Q 528 742
Q 15 742
Q 882 150
Q 882 977
Q 524...

result:

points 1.0 points  1.0

Test #38:

score: 15
Accepted
time: 24ms
memory: 7792kb

input:

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

output:

Q 602 362
Q 57 362
Q 326 491
Q 678 66
Q 326 66
Q 491 66
Q 491 678
Q 57 326
Q 362 326
Q 362 66
Q 362 491
Q 362 678
Q 602 678
Q 935 33
Q 497 700
Q 33 497
Q 935 497
Q 935 700
Q 842 705
Q 76 206
Q 842 206
Q 842 76
Q 705 76
Q 33 206
Q 33 842
Q 497 842
Q 700 842
Q 935 842
Q 935 76
Q 935 705
Q 57 206
Q 57 ...

result:

points 1.0 points  1.0

Test #39:

score: 15
Accepted
time: 5ms
memory: 7796kb

input:

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

output:

Q 762 882
Q 982 762
Q 982 882
Q 4 212
Q 502 151
Q 212 502
Q 212 151
Q 4 151
Q 762 502
Q 762 212
Q 982 212
Q 982 151
Q 982 4
Q 882 4
Q 689 189
Q 66 380
Q 689 66
Q 689 380
Q 189 380
Q 471 979
Q 931 520
Q 471 931
Q 979 931
Q 66 471
Q 66 979
Q 689 979
Q 380 979
Q 380 931
Q 380 520
Q 502 471
Q 762 471
Q ...

result:

points 1.0 points  1.0

Test #40:

score: 15
Accepted
time: 0ms
memory: 7732kb

input:

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

output:

Q 224 874
Q 448 224
Q 448 874
Q 167 355
Q 888 150
Q 167 150
Q 355 150
Q 355 888
Q 224 167
Q 224 150
Q 874 150
Q 874 355
Q 874 888
Q 448 888
Q 378 782
Q 210 443
Q 378 210
Q 378 443
Q 782 443
Q 236 629
Q 51 340
Q 629 340
Q 236 340
Q 236 51
Q 210 629
Q 378 629
Q 782 629
Q 782 340
Q 782 236
Q 782 51
Q 1...

result:

points 1.0 points  1.0

Test #41:

score: 15
Accepted
time: 8ms
memory: 7760kb

input:

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

output:

Q 875 294
Q 885 875
Q 885 294
Q 817 664
Q 458 986
Q 664 458
Q 817 458
Q 875 664
Q 875 817
Q 294 817
Q 885 817
Q 885 458
Q 494 668
Q 203 804
Q 494 804
Q 494 203
Q 668 203
Q 991 628
Q 405 821
Q 628 405
Q 628 821
Q 804 405
Q 804 821
Q 494 821
Q 668 821
Q 668 628
Q 668 991
Q 664 405
Q 664 804
Q 875 804
...

result:

points 1.0 points  1.0

Test #42:

score: 15
Accepted
time: 6ms
memory: 7804kb

input:

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

output:

Q 320 90
Q 891 90
Q 891 320
Q 706 779
Q 507 957
Q 779 507
Q 706 507
Q 706 957
Q 90 779
Q 90 507
Q 320 507
Q 320 957
Q 320 706
Q 891 706
Q 972 519
Q 335 770
Q 972 770
Q 519 770
Q 519 335
Q 657 344
Q 505 114
Q 657 505
Q 657 114
Q 344 114
Q 972 505
Q 770 505
Q 770 657
Q 770 114
Q 770 344
Q 519 344
Q 33...

result:

points 1.0 points  1.0

Test #43:

score: 15
Accepted
time: 15ms
memory: 7732kb

input:

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

output:

Q 998 225
Q 745 225
Q 745 998
Q 755 427
Q 471 690
Q 427 471
Q 755 471
Q 755 690
Q 225 427
Q 745 427
Q 745 471
Q 745 690
Q 745 755
Q 998 755
Q 530 446
Q 417 484
Q 446 417
Q 446 484
Q 530 484
Q 33 645
Q 187 454
Q 33 187
Q 645 187
Q 645 454
Q 417 33
Q 417 187
Q 417 454
Q 446 454
Q 484 454
Q 484 645
Q 5...

result:

points 1.0 points  1.0

Test #44:

score: 15
Accepted
time: 0ms
memory: 7864kb

input:

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

output:

Q 344 435
Q 852 435
Q 903 574
Q 976 789
Q 903 976
Q 903 789
Q 574 789
Q 852 976
Q 852 903
Q 852 789
Q 435 789
Q 435 574
Q 581 305
Q 786 598
Q 581 786
Q 581 598
Q 653 579
Q 700 161
Q 653 700
Q 653 161
Q 579 161
Q 786 700
Q 598 700
Q 598 653
Q 598 579
Q 581 579
Q 305 579
Q 305 161
Q 976 786
Q 903 786
...

result:

points 1.0 points  1.0

Subtask #3:

score: 75
Accepted

Test #45:

score: 75
Accepted
time: 11ms
memory: 8008kb

input:

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

output:

Q 693 599
Q 344 693
Q 344 599
Q 579 940
Q 891 956
Q 940 956
Q 940 891
Q 579 891
Q 693 956
Q 344 956
Q 344 940
Q 599 940
Q 599 579
Q 599 891
Q 351 830
Q 582 327
Q 351 582
Q 830 582
Q 830 327
Q 316 79
Q 658 279
Q 79 279
Q 79 658
Q 316 658
Q 351 279
Q 351 79
Q 582 79
Q 582 316
Q 830 316
Q 830 658
Q 327...

result:

points 1.0 points  1.0

Test #46:

score: 75
Accepted
time: 8ms
memory: 7720kb

input:

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

output:

Q 328 247
Q 216 328
Q 216 247
Q 195 26
Q 982 497
Q 195 497
Q 26 497
Q 26 982
Q 328 195
Q 247 195
Q 216 195
Q 427 270
Q 981 395
Q 427 395
Q 427 981
Q 270 981
Q 505 735
Q 408 723
Q 735 723
Q 735 408
Q 505 408
Q 395 723
Q 427 723
Q 270 723
Q 270 735
Q 981 735
Q 981 505
Q 981 408
Q 328 395
Q 247 395
Q 2...

result:

points 1.0 points  1.0

Test #47:

score: 75
Accepted
time: 24ms
memory: 7724kb

input:

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

output:

Q 173 921
Q 642 173
Q 642 921
Q 586 384
Q 589 497
Q 384 589
Q 586 589
Q 173 384
Q 173 586
Q 642 586
Q 642 589
Q 642 497
Q 231 223
Q 733 884
Q 231 884
Q 231 733
Q 333 736
Q 471 704
Q 333 471
Q 736 471
Q 736 704
Q 884 333
Q 884 471
Q 733 471
Q 733 704
Q 231 704
Q 231 736
Q 384 333
Q 173 333
Q 586 333
...

result:

points 1.0 points  1.0

Test #48:

score: 75
Accepted
time: 21ms
memory: 8008kb

input:

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

output:

Q 943 524
Q 502 524
Q 483 118
Q 708 382
Q 483 382
Q 118 382
Q 118 708
Q 502 483
Q 524 483
Q 943 483
Q 923 749
Q 966 199
Q 923 966
Q 749 966
Q 64 131
Q 884 560
Q 64 884
Q 131 884
Q 923 64
Q 749 64
Q 749 131
Q 966 131
Q 966 884
Q 199 884
Q 199 560
Q 502 923
Q 502 64
Q 524 64
Q 943 64
Q 483 64
Q 382 64...

result:

points 1.0 points  1.0

Test #49:

score: 75
Accepted
time: 0ms
memory: 7804kb

input:

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

output:

Q 962 783
Q 861 962
Q 861 783
Q 559 618
Q 288 469
Q 559 288
Q 559 469
Q 618 469
Q 962 288
Q 962 559
Q 962 469
Q 962 618
Q 861 618
Q 783 618
Q 945 806
Q 147 876
Q 806 876
Q 945 876
Q 945 147
Q 598 223
Q 131 784
Q 598 784
Q 223 784
Q 223 131
Q 806 598
Q 806 784
Q 806 131
Q 806 223
Q 876 223
Q 288 598
...

result:

points 1.0 points  1.0

Test #50:

score: 75
Accepted
time: 26ms
memory: 7728kb

input:

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

output:

Q 572 434
Q 803 572
Q 911 937
Q 810 707
Q 937 707
Q 937 810
Q 911 810
Q 803 707
Q 572 707
Q 434 707
Q 434 937
Q 434 911
Q 706 843
Q 31 1
Q 843 1
Q 843 31
Q 706 31
Q 248 109
Q 345 929
Q 109 929
Q 109 345
Q 248 345
Q 1 929
Q 843 929
Q 706 929
Q 706 109
Q 706 248
Q 706 345
Q 803 1
Q 572 1
Q 707 1
Q 937...

result:

points 1.0 points  1.0

Test #51:

score: 75
Accepted
time: 13ms
memory: 7804kb

input:

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

output:

Q 901 712
Q 929 712
Q 929 901
Q 25 397
Q 566 390
Q 25 566
Q 25 390
Q 397 390
Q 712 566
Q 901 566
Q 901 25
Q 901 397
Q 901 390
Q 165 627
Q 401 529
Q 165 401
Q 165 529
Q 627 529
Q 126 902
Q 425 877
Q 126 425
Q 126 877
Q 902 877
Q 401 425
Q 165 425
Q 627 425
Q 627 126
Q 627 902
Q 627 877
Q 712 401
Q 56...

result:

points 1.0 points  1.0

Test #52:

score: 75
Accepted
time: 13ms
memory: 7796kb

input:

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

output:

Q 300 66
Q 744 300
Q 206 214
Q 715 166
Q 214 166
Q 214 715
Q 206 715
Q 744 166
Q 744 214
Q 300 214
Q 300 206
Q 66 206
Q 170 202
Q 943 369
Q 202 369
Q 170 369
Q 923 795
Q 812 514
Q 923 812
Q 923 514
Q 795 514
Q 202 812
Q 202 923
Q 202 795
Q 170 795
Q 369 795
Q 369 514
Q 943 514
Q 166 812
Q 166 923
Q ...

result:

points 1.0 points  1.0

Test #53:

score: 75
Accepted
time: 9ms
memory: 7720kb

input:

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

output:

Q 15 884
Q 405 884
Q 405 15
Q 964 24
Q 398 946
Q 24 946
Q 964 946
Q 884 24
Q 405 24
Q 405 964
Q 15 964
Q 12 167
Q 319 620
Q 12 620
Q 12 319
Q 86 285
Q 332 867
Q 285 332
Q 285 867
Q 620 332
Q 319 332
Q 319 867
Q 319 285
Q 319 86
Q 12 86
Q 167 86
Q 884 620
Q 884 332
Q 884 867
Q 24 867
Q 405 867
Q 15 8...

result:

points 1.0 points  1.0

Test #54:

score: 75
Accepted
time: 0ms
memory: 7784kb

input:

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

output:

Q 366 853
Q 468 366
Q 468 853
Q 932 62
Q 222 701
Q 932 701
Q 932 222
Q 62 222
Q 366 701
Q 468 701
Q 853 701
Q 853 932
Q 853 222
Q 483 165
Q 330 3
Q 165 330
Q 165 3
Q 483 3
Q 621 606
Q 938 6
Q 621 938
Q 606 938
Q 606 6
Q 330 621
Q 330 938
Q 330 606
Q 165 606
Q 165 6
Q 483 6
Q 366 621
Q 366 938
Q 366 ...

result:

points 1.0 points  1.0

Test #55:

score: 75
Accepted
time: 16ms
memory: 7984kb

input:

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

output:

Q 123 458
Q 704 458
Q 704 123
Q 9 155
Q 1 319
Q 155 1
Q 155 319
Q 9 319
Q 458 1
Q 704 1
Q 704 155
Q 123 155
Q 123 9
Q 123 319
Q 39 471
Q 137 984
Q 471 984
Q 39 984
Q 39 137
Q 778 681
Q 845 307
Q 778 845
Q 778 307
Q 471 845
Q 471 307
Q 471 778
Q 471 681
Q 984 681
Q 39 681
Q 137 681
Q 458 845
Q 1 845
...

result:

points 1.0 points  1.0

Test #56:

score: 75
Accepted
time: 5ms
memory: 7720kb

input:

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

output:

Q 283 381
Q 389 381
Q 389 283
Q 193 412
Q 361 761
Q 193 761
Q 412 761
Q 412 361
Q 381 193
Q 381 761
Q 389 761
Q 283 761
Q 283 412
Q 283 361
Q 550 534
Q 93 775
Q 534 775
Q 534 93
Q 264 679
Q 299 373
Q 264 299
Q 679 299
Q 775 264
Q 775 679
Q 93 679
Q 93 299
Q 534 299
Q 550 299
Q 550 373
Q 193 264
Q 38...

result:

points 1.0 points  1.0

Test #57:

score: 75
Accepted
time: 22ms
memory: 7788kb

input:

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

output:

Q 582 956
Q 205 582
Q 678 626
Q 370 719
Q 626 719
Q 626 370
Q 205 719
Q 205 370
Q 582 370
Q 956 370
Q 155 547
Q 7 709
Q 547 709
Q 547 7
Q 155 7
Q 572 350
Q 936 348
Q 350 348
Q 350 936
Q 572 936
Q 709 348
Q 709 350
Q 709 936
Q 547 936
Q 7 936
Q 7 572
Q 719 348
Q 719 350
Q 205 350
Q 582 350
Q 956 350
...

result:

points 1.0 points  1.0

Test #58:

score: 75
Accepted
time: 3ms
memory: 8024kb

input:

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

output:

Q 396 563
Q 142 563
Q 142 396
Q 175 736
Q 518 169
Q 175 518
Q 175 169
Q 736 169
Q 563 518
Q 142 518
Q 142 175
Q 142 169
Q 142 736
Q 926 187
Q 505 291
Q 926 505
Q 926 291
Q 187 291
Q 112 824
Q 425 496
Q 112 425
Q 112 496
Q 824 496
Q 505 425
Q 926 425
Q 291 425
Q 291 112
Q 291 496
Q 291 824
Q 563 505
...

result:

points 1.0 points  1.0

Test #59:

score: 75
Accepted
time: 4ms
memory: 7796kb

input:

1000
1
0
1
1
0
0
0
0
0
1
1
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
1
1
0
0
0
0
0
0
1
1
0
0
1
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
1
0
0
0
0
0
1
1
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
1
1
0
0
0
0
0
0
1
1
0
0
1
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...

output:

Q 902 208
Q 852 208
Q 140 738
Q 245 984
Q 738 984
Q 140 984
Q 852 738
Q 208 738
Q 902 738
Q 678 27
Q 518 584
Q 27 584
Q 678 584
Q 532 663
Q 685 326
Q 663 326
Q 532 326
Q 27 663
Q 678 663
Q 584 663
Q 518 663
Q 852 27
Q 208 27
Q 902 27
Q 738 27
Q 140 27
Q 984 27
Q 245 27
Q 862 105
Q 8 339
Q 105 339
Q ...

result:

points 1.0 points  1.0

Test #60:

score: 75
Accepted
time: 4ms
memory: 7792kb

input:

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

output:

Q 968 450
Q 655 968
Q 509 917
Q 531 664
Q 509 531
Q 509 664
Q 655 531
Q 655 664
Q 655 509
Q 968 509
Q 968 917
Q 123 474
Q 184 67
Q 123 184
Q 123 67
Q 894 682
Q 65 485
Q 894 65
Q 894 485
Q 184 65
Q 184 485
Q 184 894
Q 184 682
Q 531 65
Q 531 485
Q 531 894
Q 531 682
Q 531 184
Q 531 67
Q 531 123
Q 531 4...

result:

points 1.0 points  1.0

Test #61:

score: 75
Accepted
time: 22ms
memory: 7720kb

input:

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

output:

Q 773 277
Q 854 277
Q 908 313
Q 331 150
Q 313 150
Q 908 150
Q 908 331
Q 854 313
Q 854 150
Q 854 908
Q 277 908
Q 773 908
Q 132 244
Q 135 429
Q 244 429
Q 132 429
Q 132 135
Q 742 617
Q 871 595
Q 617 595
Q 742 595
Q 742 871
Q 244 617
Q 429 617
Q 429 595
Q 132 595
Q 132 742
Q 135 742
Q 313 244
Q 150 244
...

result:

points 1.0 points  1.0

Test #62:

score: 75
Accepted
time: 7ms
memory: 7732kb

input:

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

output:

Q 972 171
Q 906 972
Q 58 574
Q 412 791
Q 58 412
Q 58 791
Q 906 412
Q 906 791
Q 906 58
Q 972 58
Q 972 574
Q 144 682
Q 681 629
Q 144 681
Q 144 629
Q 416 684
Q 561 813
Q 416 561
Q 416 813
Q 681 561
Q 681 813
Q 681 416
Q 681 684
Q 412 561
Q 412 813
Q 412 416
Q 412 684
Q 412 681
Q 412 629
Q 412 144
Q 412...

result:

points 1.0 points  1.0