QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#744015#9432. Permutationlzc0115AC ✓308ms3828kbC++141.3kb2024-11-13 20:35:542024-11-13 20:35:54

Judging History

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

  • [2024-11-13 20:35:54]
  • 评测
  • 测评结果:AC
  • 用时:308ms
  • 内存:3828kb
  • [2024-11-13 20:35:54]
  • 提交

answer

#include<iostream>
#include<algorithm>
#include<vector>
#include<random>

using namespace std;

int n, a[1010], f[1010], sz[1010], cl, cr;
bool b[1010];

mt19937 Rand(time(0));

vector<int> S;

int F(int x){
  return (f[x] ? f[x] = F(f[x]) : x);
}

int Ask(int mid, int x, int y){
  int c = 0;
  cout << "0 ";
  for(int i = 1; i <= mid; i++) cout << x << " ";
  for(int i = mid + 1; i <= n; i++) cout << y << " ";
  cout << endl;
  cin >> c;
  if(c == 1){
    f[x] = y, sz[y] += sz[x];
    return 1;
  }
  if(c == 2) cl += sz[x], cr += sz[y], b[y] = 1;
  else cl += sz[y], cr += sz[x], b[x] = 1;
  return 2;
}

void Solve(int l, int r){
  if(l == r) return;
  shuffle(a + l, a + r + 1, Rand);
  for(int i = l; i <= r; i++) b[a[i]] = f[a[i]] = 0, sz[a[i]] = 1;
  cl = cr = 0;
  int p = l, mid = (l + r) >> 1;
  while(p < r) p += Ask(mid, a[p], a[p + 1]);
  if(p == r) b[a[p]] = (cl == mid - l + 1);
  for(int i = l; i <= r; i++){
    b[a[i]] = b[F(a[i])];
  }
  for(int i = l, j = r; i < j; ){
    while(i < j && !b[a[i]]) i++;
    while(i < j && b[a[j]]) j--;
    swap(a[i], a[j]);
  }
  Solve(l, mid), Solve(mid + 1, r);
}

int main(){
  cin >> n;
  for(int i = 1; i <= n; i++) a[i] = i;
  Solve(1, n);
  cout << 1 << " ";
  for(int i = 1; i <= n; i++){
    cout << a[i] << " ";
  }
  cout << endl;
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
1
1
2
2
2
0

output:

0 4 4 4 3 3 
0 3 3 3 2 2 
0 2 2 2 1 1 
0 3 3 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: 272ms
memory: 3756kb

input:

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

output:

0 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 647 64...

result:

ok Accepted

Test #3:

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

input:

1

output:

1 1 

result:

ok Accepted

Test #4:

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

input:

2
2

output:

0 2 1 
1 2 1 

result:

ok Accepted

Test #5:

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

input:

3
0
2

output:

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

result:

ok Accepted

Test #6:

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

input:

4
2
2
0
0

output:

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

result:

ok Accepted

Test #7:

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

input:

6
2
2
2
2
0
2
2

output:

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

result:

ok Accepted

Test #8:

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

input:

7
1
2
0
0
1
2
0
0
2
2

output:

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

result:

ok Accepted

Test #9:

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

input:

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

output:

0 4 4 4 4 6 6 6 6 
0 6 6 6 6 3 3 3 3 
0 7 7 7 7 2 2 2 2 
0 2 2 2 2 1 1 1 1 
0 1 1 1 1 5 5 5 5 
0 3 3 7 7 7 7 7 7 
0 7 7 2 2 2 2 2 2 
0 3 7 7 7 7 7 7 7 
0 2 2 2 1 1 1 1 1 
0 8 8 8 8 8 8 5 5 
0 4 4 4 4 4 4 6 6 
0 5 5 5 5 5 6 6 6 
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: 3756kb

input:

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

output:

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

result:

ok Accepted

Test #11:

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

input:

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

output:

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

result:

ok Accepted

Test #12:

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

input:

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

output:

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

result:

ok Accepted

Test #13:

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

input:

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

output:

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

result:

ok Accepted

Test #14:

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

input:

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

output:

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

result:

ok Accepted

Test #15:

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

input:

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

output:

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

result:

ok Accepted

Test #16:

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

input:

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

output:

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

result:

ok Accepted

Test #17:

score: 0
Accepted
time: 264ms
memory: 3812kb

input:

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

output:

0 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 233 23...

result:

ok Accepted

Test #18:

score: 0
Accepted
time: 252ms
memory: 3760kb

input:

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

output:

0 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 20...

result:

ok Accepted

Test #19:

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

input:

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

output:

0 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 958 95...

result:

ok Accepted

Test #20:

score: 0
Accepted
time: 278ms
memory: 3684kb

input:

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

output:

0 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 86...

result:

ok Accepted

Test #21:

score: 0
Accepted
time: 259ms
memory: 3768kb

input:

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

output:

0 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 31...

result:

ok Accepted

Test #22:

score: 0
Accepted
time: 280ms
memory: 3676kb

input:

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

output:

0 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 8...

result:

ok Accepted

Test #23:

score: 0
Accepted
time: 261ms
memory: 3768kb

input:

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

output:

0 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 4...

result:

ok Accepted

Test #24:

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

input:

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

output:

0 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 343 34...

result:

ok Accepted

Test #25:

score: 0
Accepted
time: 274ms
memory: 3680kb

input:

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

output:

0 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 361 36...

result:

ok Accepted

Test #26:

score: 0
Accepted
time: 296ms
memory: 3744kb

input:

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

output:

0 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 225 22...

result:

ok Accepted

Test #27:

score: 0
Accepted
time: 277ms
memory: 3756kb

input:

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

output:

0 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 733 73...

result:

ok Accepted

Test #28:

score: 0
Accepted
time: 302ms
memory: 3828kb

input:

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

output:

0 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 708 70...

result:

ok Accepted

Test #29:

score: 0
Accepted
time: 292ms
memory: 3640kb

input:

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

output:

0 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 42...

result:

ok Accepted

Test #30:

score: 0
Accepted
time: 270ms
memory: 3676kb

input:

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

output:

0 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 849 84...

result:

ok Accepted

Test #31:

score: 0
Accepted
time: 279ms
memory: 3688kb

input:

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

output:

0 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 30...

result:

ok Accepted

Test #32:

score: 0
Accepted
time: 279ms
memory: 3640kb

input:

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

output:

0 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 15...

result:

ok Accepted

Test #33:

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

input:

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

output:

0 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 471 47...

result:

ok Accepted

Test #34:

score: 0
Accepted
time: 268ms
memory: 3676kb

input:

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

output:

0 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 357 35...

result:

ok Accepted

Test #35:

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

input:

993
1
0
0
1
0
1
2
1
2
1
1
2
0
1
2
1
0
2
1
1
1
1
2
0
1
0
0
1
1
1
1
1
1
1
1
1
2
2
2
1
1
2
2
1
1
1
1
1
1
0
1
1
1
0
1
1
0
0
1
0
1
1
0
1
0
0
2
1
2
2
1
1
2
1
2
1
0
1
1
1
1
1
1
2
2
1
1
2
1
0
0
2
0
1
1
0
2
2
1
0
1
1
1
2
1
2
0
2
2
0
1
2
0
1
2
1
2
2
1
1
2
1
0
1
0
1
1
1
2
1
0
0
1
1
0
0
0
2
1
2
0
1
1
1
1
0
2
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 #36:

score: 0
Accepted
time: 272ms
memory: 3684kb

input:

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

output:

0 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 537 53...

result:

ok Accepted

Test #37:

score: 0
Accepted
time: 289ms
memory: 3684kb

input:

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

output:

0 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 281 28...

result:

ok Accepted

Test #38:

score: 0
Accepted
time: 287ms
memory: 3684kb

input:

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

output:

0 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 289 28...

result:

ok Accepted

Test #39:

score: 0
Accepted
time: 297ms
memory: 3756kb

input:

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

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 #40:

score: 0
Accepted
time: 284ms
memory: 3708kb

input:

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

output:

0 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 46...

result:

ok Accepted

Test #41:

score: 0
Accepted
time: 308ms
memory: 3620kb

input:

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

output:

0 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 463 46...

result:

ok Accepted

Extra Test:

score: 0
Extra Test Passed