QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#687639#9432. PermutationxydCatGirlAC ✓230ms4060kbC++203.0kb2024-10-29 20:10:242024-10-29 20:10:25

Judging History

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

  • [2024-10-29 20:10:25]
  • 评测
  • 测评结果:AC
  • 用时:230ms
  • 内存:4060kb
  • [2024-10-29 20:10:24]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define pb emplace_back
#define For(i, x, y) for (int i = (x); i <= (y); i ++)
#define rep(i, x, y) for (int i = (x); i >= (y); i --)
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define sz(v) (int)((v).size())
#define ull unsigned long long
#define ls (p << 1)
#define rs (p << 1 | 1)
#define mp make_pair
#define i128 __int128
#define db long double
#define vi vector< int >
#define mem(v, x) memset(v, x, sizeof(v))
#define A3 array< int, 3 >
#define A4 array< int, 4 >
#define vpii vector< pair< int, int > >
using namespace std;
mt19937_64 rnd(time(0));
template< typename T > void cmin(T &x, T y) { return x = min(x, y), void(); }
template< typename T > void cmax(T &x, T y) { return x = max(x, y), void(); }
int ksm(int x, int y, int p) {
    int v = 1; x %= p;
    while (y) v = 1ll * v * ((y & 1) ? x : 1) % p, x = 1ll * x * x % p, y >>= 1;
    return (v % p + p) % p;
}
bool MemoryST;
const int N = 1005;
const int mod = 998244353;
const long long INF = 1e18;
const int base = 13131;
int n;
int ans[N], q[N];
int cnt = 0;
int query() {
	if (cnt == 6665) {
		while (1);
	}
	cnt ++;
	cout << "0 ";
	For (i, 1, n) cout << q[i] << ' ';
	cout << endl;
	int res; cin >> res;
	return res;
}
int bel[N], fa[N];
int find(int x) {
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}
struct node {
	int x;
	ull val;
} ;
bool operator < (node i, node j) {
	return i.val < j.val;
}
void solve(int l, int r, vi a) {
	if (l == r) return ans[l] = a[0], void();
	int mid = (l + r) >> 1;
	set< node > s;
	for (int x : a) s.insert(node{x, rnd()}), fa[x] = x;
	while (sz(s) > 1) {
		auto [x, _] = *s.begin(); s.erase(node{x, _});
		auto [y, __] = *s.begin(); s.erase(node{y, __});
		For (i, 1, mid) q[i] = x;
		For (i, mid + 1, n) q[i] = y;
		int res = query();
		if (res == 0) bel[x] = 1, bel[y] = 0;
		else if (res == 2) bel[x] = 0, bel[y] = 1;
		else {
			if (find(x) != x || find(y) != y) while (1);
			fa[x] = y;
			s.insert(node{y, rnd()});
		}
	}
	vi b, c;
	if (sz(s) == 1) {
		auto [y, _] = *s.begin();
		vi val;
		for (int x : a) {
			if (find(x) == y) {
				val.pb(x); continue;
			}
			if (!bel[find(x)]) b.pb(x); else c.pb(x);
		}
		if (sz(b) != mid - l + 1) for (int x : val) b.pb(x);
		else for (int x : val) c.pb(x);
	} else {
		for (int x : a) if (!bel[find(x)]) b.pb(x); else c.pb(x);
	}
	solve(l, mid, b); solve(mid + 1, r, c);
	return;
}
void Main() {
	cin >> n; vi a;
	For (i, 1, n) a.pb(i);
	solve(1, n, a);
	cout << "1 ";
	For (i, 1, n) cout << ans[i] << ' ';
	cout << endl;
    return;
}
bool MemoryED;
signed main() {
    ios :: sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // cerr << fixed << setprecision(6) << (&MemoryST - &MemoryED) / 1048576.0 << "MB\n";
    int TESTCNT = 1;
    // cin >> TESTCNT;
    while (TESTCNT --) Main();
    // cerr << endl << 1e3 * clock() / CLOCKS_PER_SEC << "ms"; 
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
0
0
1
0
0
0

output:

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

result:

ok Accepted

Test #2:

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

input:

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

output:

0 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 789 78...

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: 0ms
memory: 3708kb

input:

2
2

output:

0 2 1 
1 2 1 

result:

ok Accepted

Test #5:

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

input:

3
0
0

output:

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

result:

ok Accepted

Test #6:

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

input:

4
2
0
0
0

output:

0 4 4 2 2 
0 1 1 3 3 
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: 3696kb

input:

6
2
2
0
0
0
1
2
0

output:

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

input:

7
2
0
0
1
0
0
0
0
2

output:

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

input:

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

output:

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

input:

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

output:

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

result:

ok Accepted

Test #11:

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

input:

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

output:

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

result:

ok Accepted

Test #12:

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

input:

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

output:

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

result:

ok Accepted

Test #13:

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

input:

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

output:

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

result:

ok Accepted

Test #14:

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

input:

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

output:

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

result:

ok Accepted

Test #15:

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

input:

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

output:

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

result:

ok Accepted

Test #16:

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

input:

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

output:

0 14 14 14 14 14 14 14 14 1 1 1 1 1 1 1 
0 7 7 7 7 7 7 7 7 10 10 10 10 10 10 10 
0 8 8 8 8 8 8 8 8 11 11 11 11 11 11 11 
0 10 10 10 10 10 10 10 10 15 15 15 15 15 15 15 
0 15 15 15 15 15 15 15 15 13 13 13 13 13 13 13 
0 13 13 13 13 13 13 13 13 9 9 9 9 9 9 9 
0 9 9 9 9 9 9 9 9 12 12 12 12 12 12 12 
0 ...

result:

ok Accepted

Test #17:

score: 0
Accepted
time: 196ms
memory: 3960kb

input:

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

output:

0 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 26...

result:

ok Accepted

Test #18:

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

input:

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

output:

0 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 624 62...

result:

ok Accepted

Test #19:

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

input:

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

output:

0 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 723 72...

result:

ok Accepted

Test #20:

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

input:

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

output:

0 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 746 74...

result:

ok Accepted

Test #21:

score: 0
Accepted
time: 211ms
memory: 3736kb

input:

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

output:

0 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 31...

result:

ok Accepted

Test #22:

score: 0
Accepted
time: 195ms
memory: 3808kb

input:

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

output:

0 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 14...

result:

ok Accepted

Test #23:

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

input:

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

output:

0 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 513 51...

result:

ok Accepted

Test #24:

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

input:

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

output:

0 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 729 72...

result:

ok Accepted

Test #25:

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

input:

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

output:

0 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 25...

result:

ok Accepted

Test #26:

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

input:

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

output:

0 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 485 48...

result:

ok Accepted

Test #27:

score: 0
Accepted
time: 174ms
memory: 4032kb

input:

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

output:

0 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 913 91...

result:

ok Accepted

Test #28:

score: 0
Accepted
time: 186ms
memory: 3732kb

input:

986
2
1
2
1
1
2
2
1
1
1
0
1
2
1
1
2
1
1
0
0
0
2
1
2
0
2
1
1
1
0
0
1
1
0
1
1
1
2
2
0
0
2
0
1
0
0
0
1
2
1
1
1
1
1
2
1
2
1
2
0
2
2
2
1
1
0
2
1
2
1
1
1
1
2
1
0
1
0
1
0
1
2
0
1
2
2
1
1
0
0
1
1
0
2
1
2
1
2
1
2
0
1
0
1
2
1
1
2
0
0
0
1
1
1
1
1
1
0
2
1
0
1
1
2
1
1
1
1
0
1
1
2
1
2
1
2
2
1
0
1
2
1
2
2
2
1
1
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

Test #29:

score: 0
Accepted
time: 201ms
memory: 4060kb

input:

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

output:

0 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 770 77...

result:

ok Accepted

Test #30:

score: 0
Accepted
time: 220ms
memory: 3836kb

input:

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

output:

0 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 742 74...

result:

ok Accepted

Test #31:

score: 0
Accepted
time: 180ms
memory: 4028kb

input:

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

output:

0 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 534 53...

result:

ok Accepted

Test #32:

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

input:

990
1
1
1
2
2
0
1
0
1
0
2
1
1
1
0
1
2
1
1
1
2
1
1
1
1
1
1
1
1
0
1
2
1
1
2
2
2
1
2
1
1
0
1
0
0
0
1
1
0
1
1
1
1
1
2
2
1
0
1
1
0
0
2
0
0
0
2
2
2
2
0
0
0
2
1
1
1
1
1
1
0
1
1
2
0
2
1
1
1
0
1
1
0
1
0
1
0
0
0
0
2
1
0
1
0
2
1
2
1
0
0
1
0
1
2
2
1
0
1
0
1
2
2
0
0
1
0
1
1
2
2
0
2
1
1
0
2
0
1
2
1
1
1
0
2
0
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 #33:

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

input:

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

output:

0 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 488 48...

result:

ok Accepted

Test #34:

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

input:

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

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

score: 0
Accepted
time: 211ms
memory: 3792kb

input:

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

output:

0 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 218 21...

result:

ok Accepted

Test #36:

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

input:

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

output:

0 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 652 65...

result:

ok Accepted

Test #37:

score: 0
Accepted
time: 191ms
memory: 3800kb

input:

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

output:

0 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 26...

result:

ok Accepted

Test #38:

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

input:

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

output:

0 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 21...

result:

ok Accepted

Test #39:

score: 0
Accepted
time: 230ms
memory: 3796kb

input:

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

output:

0 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 3...

result:

ok Accepted

Test #40:

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

input:

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

output:

0 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 718 71...

result:

ok Accepted

Test #41:

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

input:

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

output:

0 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 942 94...

result:

ok Accepted

Extra Test:

score: 0
Extra Test Passed