QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#290053#7788. Rook Detectionecnerwala#AC ✓222ms5192kbC++236.0kb2023-12-24 12:06:502023-12-24 12:06:50

Judging History

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

  • [2023-12-24 12:06:50]
  • 评测
  • 测评结果:AC
  • 用时:222ms
  • 内存:5192kb
  • [2023-12-24 12:06:50]
  • 提交

answer

#include <bits/stdc++.h>

// Floor of log_2(a); index of highest 1-bit
inline int floor_log_2(int a) {
	return a ? (8 * sizeof(a)) - 1 - __builtin_clz(a) : -1;
}

inline int ceil_log_2(int a) {
	return a ? floor_log_2(2*a-1) : -1;
}

inline int next_pow_2(int a) {
	return 1 << ceil_log_2(a);
}

int main() {
	using namespace std;
	ios_base::sync_with_stdio(false), cin.tie(nullptr);

	auto solve = [&](int N, auto&& query) -> std::vector<std::string> {
		auto solve_empty_row = [&](int r_empty) -> std::vector<std::string> {
			std::vector<int> resp(N);
			for (int b = 0; (1 << b) < N; b++) {
				std::vector<std::string> Q(N, std::string(N, '0'));
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < N; j++) {
						if (j % (1 << b) == resp[i] && (j & (1 << b))) Q[j][i] = '1';
					}
					Q[r_empty][i] = '1';
				}
				auto R = query(Q);
				for (int i = 0; i < N; i++) {
					if (R[r_empty][i] == '1') {
						resp[i] += (1 << b);
					}
				}
			}
			std::vector<std::string> ans(N, std::string(N, '0'));
			for (int i = 0; i < N; i++) {
				ans[resp[i]][i] = '1';
			}
			return ans;
		};

		std::vector<std::string> Q0(N, std::string(N, '0'));
		for (int i = 1; i < N; i++) {
			Q0[i][0] = Q0[i][i] = '1';
		}
		auto R0 = query(Q0);
		if (R0[0][0] == '0') {
			return solve_empty_row(0);
		}

		std::vector<std::string> Q1(N, std::string(N, '0'));
		Q1[0][0] = '1';
		Q1[0][1] = '1';
		for (int i = 1; i < N; i++) {
			if (R0[i][i] == '1') {
				Q1[i][0] = '1';
			}
		}
		auto R1 = query(Q1);
		for (int i = 1; i < N; i++) {
			if (R0[i][i] == '0' && R1[i][0] == '0') {
				return solve_empty_row(i);
			}
		}
		// Just fill in this fake answer so it's in the same place
		R0[0][0] = R1[0][1];
		std::vector<int> resp(N);
		for (int i = 0; i < N; i++) {
			if (R0[i][i] == '1') {
				resp[i] = -2;
			}
		}
		for (int b = 0; (1 << b) < N; b++) {
			std::vector<std::string> Q(N, std::string(N, '0'));
			for (int i = 0; i < N; i++) {
				if (R0[i][i] == '0') {
					// binary search
					Q[i][0] = '1';
					for (int j = 1; j < N; j++) {
						if ((j-1) % (1 << b) == resp[i] && ((j-1) & (1 << b))) {
							Q[i][j] = '1';
						}
					}
				} else {
					int j = (i == 0 ? 1 : i);
					bool can_check = false;
					if (!((j-1) & (1 << b))) {
						if (j == 1) {
							assert(i == 0 || i == 1);
							if (i == (b & 1)) {
								can_check = true;
							}
						} else {
							can_check = true;
						}
					}
					if (can_check) {
						Q[i][j] = '1';
					}
				}
			}
			auto R = query(Q);
			for (int i = 0; i < N; i++) {
				if (R0[i][i] == '0') {
					if (R[i][0] == '1') {
						resp[i] += (1 << b);
					}
				} else {
					int j = (i == 0 ? 1 : i);
					if (Q[i][j] == '1') {
						int v;
						if (R[i][j] == '1') {
							v = j;
						} else {
							v = 0;
						}
						if (resp[i] == -2) resp[i] = v-1;
						assert(resp[i] == v-1);
					}
				}
			}
		}
		std::vector<std::string> ans(N, std::string(N, '0'));
		for (int i = 0; i < N; i++) ans[i][resp[i]+1] = '1';
		return ans;
	};

	constexpr bool TESTING = false;

	std::mt19937 mt(48);

	int T;
	if (TESTING) {
		T = 100;
	} else {
		cin >> T;
	}
	while (T--) {
		int N;
		if (TESTING) {
			N = std::uniform_int_distribution<int>(3, 10)(mt);
		} else {
			cin >> N;
		}
		std::vector<std::string> TESTING_ANS;
		if (TESTING) {
			TESTING_ANS = std::vector<std::string>(N, std::string(N, '0'));
			while (true) {
				double p = std::uniform_real_distribution<double>(0, 1)(mt);
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < N; j++) {
						TESTING_ANS[i][j] = std::bernoulli_distribution(p)(mt) ? '1' : '0';
					}
				}
				bool good = true;
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < N; j++) {
						bool found = false;
						for (int k = 0; k < N; k++) {
							if (TESTING_ANS[i][k] == '1' || TESTING_ANS[k][j] == '1') {
								found = true;
								break;
							}
						}
						if (!found) good = false;
					}
				}
				if (good) break;
			}
			cout << "N = " << N << '\n';
			cout << "ANSWER" << '\n';
			for (const auto& r : TESTING_ANS) cout <<r << '\n';
			cout << flush;
		}
		assert(N >= 3);
		const int max_queries = 2 + ceil_log_2(N);
		int num_queries = 0;
		auto query = [&](const std::vector<std::string>& g) -> std::vector<std::string> {
			num_queries++;
			assert(num_queries <= max_queries);
			assert(int(g.size()) == N);
			for (const auto& r : g) assert(int(r.size()) == N);
			cout << '?' << '\n';
			for (const auto& r : g) cout << r << '\n';
			cout << flush;
			if (TESTING) {
				std::vector<std::string> resp(N, std::string(N, '0'));
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < N; j++) {
						for (int k = 0; k < N; k++) {
							if (g[i][k] == g[i][j] && TESTING_ANS[i][k] == '1') resp[i][j] = '1';
							if (g[k][j] == g[i][j] && TESTING_ANS[k][j] == '1') resp[i][j] = '1';
						}
					}
				}
				cout << 0 << '\n';
				for (int i = 0; i < N; i++) {
					cout << resp[i] << '\n';
				}
				return resp;
			} else {
				int code; cin >> code;
				if (code != 0) exit(0);
				std::vector<std::string> resp(N);
				for (int i = 0; i < N; i++) {
					cin >> resp[i];
					assert(int(resp[i].size()) == N);
				}
				return resp;
			}
		};
		auto answer = [&](const std::vector<std::string>& g) -> void {
			assert(int(g.size()) == N);
			for (const auto& r : g) assert(int(r.size()) == N);
			cout << '!' << '\n';
			for (const auto& r : g) cout << r << '\n';
			cout << flush;
			if (TESTING) {
				int num_found = 0;
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < N; j++) {
						if (g[i][j] == '1') {
							assert(TESTING_ANS[i][j] == '1');
							num_found++;
						}
					}
				}
				assert(num_found >= N);
				int code = 0;
				cout << code << '\n';
				assert(code == 0);
			} else {
				int code; cin >> code;
				if (code != 0) exit(0);
			}
		};

		answer(solve(N, query));
	}

	return 0;
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

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

input:

1
3
0
111
101
111
0
111
111
101
0
110
101
111
0
111
011
110
0

output:

?
000
110
101
?
110
000
100
?
010
101
000
?
000
100
001
!
010
001
100

result:

ok correct! (1 test case)

Test #2:

score: 0
Accepted
time: 82ms
memory: 3440kb

input:

9898
3
0
111
110
111
0
111
111
111
0
111
111
111
0
111
111
111
0
3
0
111
111
111
0
111
111
111
0
111
111
111
0
111
101
111
0
3
0
111
111
111
0
101
111
111
0
111
111
111
0
011
111
111
0
3
0
111
101
111
0
101
111
111
0
111
111
111
0
011
011
110
0
3
0
111
111
010
0
111
111
111
0
111
111
010
0
111
111
0...

output:

?
000
110
101
?
110
100
100
?
010
000
000
?
000
010
001
!
010
010
001
?
000
110
101
?
110
100
100
?
010
000
000
?
000
010
001
!
010
100
001
?
000
110
101
?
110
100
100
?
101
000
000
?
100
010
001
!
001
010
001
?
000
110
101
?
110
000
100
?
101
101
000
?
100
100
001
!
001
001
100
?
000
110
101
?
110
...

result:

ok correct! (9898 test cases)

Test #3:

score: 0
Accepted
time: 37ms
memory: 3496kb

input:

10000
4
0
1111
1011
1111
1111
0
1111
1111
1111
1111
0
1111
1111
1111
1111
0
1111
0111
1111
1111
0
4
0
1111
1111
1111
1110
0
1111
1111
1111
1111
0
1011
1111
1111
0101
0
1111
1111
1101
0110
0
4
0
1111
1011
1111
1111
0
1111
1111
1111
1111
0
1111
1111
1111
1111
0
1111
0111
1111
1111
0
4
0
1111
1011
1111...

output:

?
0000
1100
1010
1001
?
1100
0000
1000
1000
?
0100
1010
0000
0001
?
0000
1000
0010
0000
!
0100
0010
0010
0001
?
0000
1100
1010
1001
?
1100
1000
1000
0000
?
0100
0000
0000
1010
?
0000
0100
0010
1001
!
1000
0100
1000
0100
?
0000
1100
1010
1001
?
1100
0000
1000
1000
?
0100
1010
0000
0001
?
0000
1000
00...

result:

ok correct! (10000 test cases)

Test #4:

score: 0
Accepted
time: 45ms
memory: 3556kb

input:

10000
4
0
1111
1111
1111
1111
0
1111
1111
1111
1111
0
1111
1111
1111
1111
0
1111
1111
1111
1111
0
4
0
1111
1011
1111
1111
0
1111
1111
1111
1111
0
1011
1111
1111
1110
0
1111
0111
1111
1111
0
4
0
1111
1111
1111
1111
0
1011
1111
1111
1111
0
1111
1111
1111
1111
0
0111
1011
1101
1111
0
4
0
1111
1111
1111...

output:

?
0000
1100
1010
1001
?
1100
1000
1000
1000
?
0100
0000
0000
0001
?
0000
0100
0010
0000
!
0100
0100
0010
0001
?
0000
1100
1010
1001
?
1100
0000
1000
1000
?
0100
1010
0000
0001
?
0000
1000
0010
0000
!
1000
0010
0010
1000
?
0000
1100
1010
1001
?
1100
1000
1000
1000
?
1010
0000
0000
0001
?
1000
0100
00...

result:

ok correct! (10000 test cases)

Test #5:

score: 0
Accepted
time: 69ms
memory: 3492kb

input:

10000
4
0
1111
1111
1111
1111
0
1111
1111
1111
1111
0
1111
1111
1111
1111
0
1111
1011
1111
1111
0
4
0
1111
1111
1101
1111
0
1111
1111
1111
1111
0
1111
1111
0101
1110
0
1111
1011
1111
1111
0
4
0
1111
1111
1111
1101
0
1111
1111
1111
1111
0
1111
1111
1111
1110
0
1111
1011
1111
1111
0
4
0
1111
1101
1011...

output:

?
0000
1100
1010
1001
?
1100
1000
1000
1000
?
0100
0000
0000
0001
?
0000
0100
0010
0000
!
0100
1000
0010
0001
?
0000
1100
1010
1001
?
1100
1000
0000
1000
?
0100
0000
1010
0001
?
0000
0100
1001
0000
!
0100
1000
0001
1000
?
0000
1100
1010
1001
?
1100
1000
1000
1000
?
0100
0000
0000
0001
?
0000
0100
00...

result:

ok correct! (10000 test cases)

Test #6:

score: 0
Accepted
time: 77ms
memory: 3440kb

input:

10000
4
0
1111
1111
1111
1111
0
1011
1111
1111
1111
0
1111
1111
1111
1111
0
0111
1111
1101
1111
0
4
0
1111
1111
1111
1110
0
1011
1111
1111
1111
0
1111
1111
1111
1111
0
0111
1011
1111
0111
0
4
0
1111
1111
1111
1110
0
1111
1111
1111
1111
0
1111
1111
1111
1111
0
1111
1111
1111
0111
0
4
0
1111
1111
1111...

output:

?
0000
1100
1010
1001
?
1100
1000
1000
1000
?
1010
0000
0000
0001
?
1000
0100
0010
0000
!
0010
0100
1000
0001
?
0000
1100
1010
1001
?
1100
1000
1000
0000
?
1010
0000
0000
1010
?
1000
0100
0010
1000
!
0010
1000
0010
0010
?
0000
1100
1010
1001
?
1100
1000
1000
0000
?
0100
0000
0000
1010
?
0000
0100
00...

result:

ok correct! (10000 test cases)

Test #7:

score: 0
Accepted
time: 85ms
memory: 5056kb

input:

7368
4
0
1111
1111
1111
1111
0
1111
1111
1111
1111
0
1111
1111
1111
1111
0
1111
1111
1111
1111
0
4
0
1111
1111
1111
1111
0
1111
1111
1111
1111
0
1111
1111
1111
1111
0
1111
1011
1111
1111
0
4
0
1111
1111
1111
1111
0
1111
1111
1111
1111
0
1111
1111
1111
1111
0
1111
1111
1111
1111
0
4
0
1111
1111
1111
...

output:

?
0000
1100
1010
1001
?
1100
1000
1000
1000
?
0100
0000
0000
0001
?
0000
0100
0010
0000
!
0100
0100
0010
0001
?
0000
1100
1010
1001
?
1100
1000
1000
1000
?
0100
0000
0000
0001
?
0000
0100
0010
0000
!
0100
1000
0010
0001
?
0000
1100
1010
1001
?
1100
1000
1000
1000
?
0100
0000
0000
0001
?
0000
0100
00...

result:

ok correct! (7368 test cases)

Test #8:

score: 0
Accepted
time: 132ms
memory: 4940kb

input:

10000
9
0
111111111
101111111
110111111
111111111
111101111
111110111
111111111
111111111
111111111
0
111111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
0
111101011
111111111
111111111
111111111
111111111
111111111
111111111
111111101
111111111
0
111111111
1111...

output:

?
000000000
110000000
101000000
100100000
100010000
100001000
100000100
100000010
100000001
?
110000000
000000000
000000000
100000000
000000000
000000000
100000000
100000000
100000000
?
010000000
101010101
101010101
000100000
101010101
101010101
000000000
000000010
000000000
?
000000000
100010001
10...

result:

ok correct! (10000 test cases)

Test #9:

score: 0
Accepted
time: 120ms
memory: 4824kb

input:

10000
5
0
11111
10111
11111
11111
11111
0
11111
11111
11111
11111
11111
0
10111
01010
11111
11111
11111
0
11111
11111
11011
11111
11111
0
10111
01111
11011
11111
11110
0
8
0
11111111
10111111
11111111
11111111
11110111
11111011
11111111
11111111
0
11111111
11111111
11111111
11111111
11111111
1111111...

output:

?
00000
11000
10100
10010
10001
?
11000
00000
10000
10000
10000
?
01000
10101
00000
00010
00000
?
00000
10010
00100
00000
00000
?
01000
10000
00100
00010
00001
!
10000
00010
10000
00010
10000
?
00000000
11000000
10100000
10010000
10001000
10000100
10000010
10000001
?
11000000
00000000
10000000
10000...

result:

ok correct! (10000 test cases)

Test #10:

score: 0
Accepted
time: 108ms
memory: 4844kb

input:

10000
9
0
111111111
111111111
111111111
111011111
111101111
111111111
111111111
111111111
111111111
0
111111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
0
111111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
0
111111111
1011...

output:

?
000000000
110000000
101000000
100100000
100010000
100001000
100000100
100000010
100000001
?
110000000
100000000
100000000
000000000
000000000
100000000
100000000
100000000
100000000
?
010000000
000000000
000000000
101010101
101010101
000001000
000000000
000000010
000000000
?
000000000
010000000
00...

result:

ok correct! (10000 test cases)

Test #11:

score: 0
Accepted
time: 144ms
memory: 4952kb

input:

10000
4
0
1111
1111
1111
1111
0
1111
1111
1111
1111
0
1111
1111
1111
1111
0
1111
1011
1111
1111
0
6
0
111111
111111
111111
111111
111111
111111
0
111111
111111
111111
111111
111111
111111
0
111111
111111
111111
111111
111111
111111
0
111111
111111
111111
111111
111111
111111
0
111111
111111
111111
1...

output:

?
0000
1100
1010
1001
?
1100
1000
1000
1000
?
0100
0000
0000
0001
?
0000
0100
0010
0000
!
0100
1000
0010
0001
?
000000
110000
101000
100100
100010
100001
?
110000
100000
100000
100000
100000
100000
?
010000
000000
000000
000100
000000
000001
?
000000
010000
001000
000000
000000
000001
?
010000
00000...

result:

ok correct! (10000 test cases)

Test #12:

score: 0
Accepted
time: 105ms
memory: 4824kb

input:

10000
6
0
111111
111111
111111
111111
111111
111111
0
111111
111111
111111
111111
111111
111111
0
111111
111111
111111
111111
111111
111111
0
111111
111111
111111
111111
111111
111111
0
111111
111111
111111
111111
111111
111111
0
9
0
111111111
111111111
111111111
111111111
111111111
111111111
111111...

output:

?
000000
110000
101000
100100
100010
100001
?
110000
100000
100000
100000
100000
100000
?
010000
000000
000000
000100
000000
000001
?
000000
010000
001000
000000
000000
000001
?
010000
000000
001000
000100
000010
000000
!
010000
010000
001000
000100
000010
000001
?
000000000
110000000
101000000
1001...

result:

ok correct! (10000 test cases)

Test #13:

score: 0
Accepted
time: 114ms
memory: 4452kb

input:

10000
6
0
111111
101111
110111
111011
100010
111110
0
110010
111111
111111
111111
100010
111111
0
101111
101010
101010
101010
111111
101010
0
111111
100010
100010
100010
111111
100010
0
101111
011111
011111
011111
111101
011111
0
8
0
11111111
11000110
10100110
11101111
10001110
11111011
10000110
111...

output:

?
000000
110000
101000
100100
100010
100001
?
110000
000000
000000
000000
100000
000000
?
010000
101010
101010
101010
000000
101010
?
000000
100010
100010
100010
000000
100010
?
010000
100000
100000
100000
000010
100000
!
100000
000010
000010
000010
100000
000010
?
00000000
11000000
10100000
1001000...

result:

ok correct! (10000 test cases)

Test #14:

score: 0
Accepted
time: 90ms
memory: 4264kb

input:

10000
6
0
111111
001111
010111
011011
011101
011110
0
111111
001111
111111
001111
001111
001111
0
111111
000000
111111
000000
111111
000000
0
111111
000101
111111
111010
111010
111010
0
111111
000000
111111
111111
000101
111111
0
9
0
011101111
101101111
110101111
111001111
111111111
111100111
111101...

output:

?
000000
110000
101000
100100
100010
100001
?
110000
000000
000000
000000
000000
000000
?
000000
111111
000000
111111
000000
111111
?
000000
111111
111111
000000
000000
000000
?
000000
111111
000000
000000
111010
000000
!
111010
000000
000101
000000
000000
000000
?
000000000
110000000
101000000
1001...

result:

ok correct! (10000 test cases)

Test #15:

score: 0
Accepted
time: 136ms
memory: 4428kb

input:

10000
9
0
111111111
111111111
111111111
111111111
111111111
111110111
111111011
111111111
111111110
0
111111111
111111111
111111111
111111111
111111111
111111111
011111111
111111111
011111111
0
111111111
111111111
111111111
111111111
111111111
111111111
110111111
111111111
111111011
0
111111111
1111...

output:

?
000000000
110000000
101000000
100100000
100010000
100001000
100000100
100000010
100000001
?
110000000
100000000
100000000
100000000
100000000
000000000
000000000
100000000
000000000
?
000000000
111111111
000000000
111111111
000000000
111111111
111111111
111111111
000000000
?
000000000
000000000
00...

result:

ok correct! (10000 test cases)

Test #16:

score: 0
Accepted
time: 128ms
memory: 4548kb

input:

10000
7
0
1111111
1111111
1010000
1111111
1111111
1111111
1111111
0
1111111
1111111
1111111
1111111
1111111
1111111
1111111
0
1011111
1111111
1111111
1110111
1111111
1111101
1111111
0
1111111
1011111
1111111
1111111
1111111
1111101
1111110
0
1011111
1111111
1111111
1110111
1111011
1111111
1111111
0
...

output:

?
0000000
1100000
1010000
1001000
1000100
1000010
1000001
?
1100000
1000000
1000000
1000000
1000000
1000000
1000000
?
0100000
0000000
0000000
0001000
0000000
0000010
0000000
?
0000000
0100000
0010000
0000000
0000000
0000010
0000001
?
0100000
0000000
0010000
0001000
0000100
0000000
0000000
!
1000000
...

result:

ok correct! (10000 test cases)

Test #17:

score: 0
Accepted
time: 110ms
memory: 4596kb

input:

10000
9
0
111111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
0
111111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
0
111111111
111111111
111111111
111011111
111111111
111111111
111111111
111111111
111111111
0
111111111
1111...

output:

?
000000000
110000000
101000000
100100000
100010000
100001000
100000100
100000010
100000001
?
110000000
100000000
100000000
100000000
100000000
100000000
100000000
100000000
100000000
?
010000000
000000000
000000000
000100000
000000000
000001000
000000000
000000010
000000000
?
000000000
010000000
00...

result:

ok correct! (10000 test cases)

Test #18:

score: 0
Accepted
time: 114ms
memory: 5068kb

input:

10000
9
0
010111111
100111111
111111111
111011111
110101111
110110111
110111011
110111101
110111110
0
010010001
010010001
111111111
111111111
101101110
010010001
101101110
010010001
101101110
0
111111111
000000000
101101110
010010001
000000000
000000000
101101110
010010001
000000000
0
000000000
1111...

output:

?
000000000
110000000
101000000
100100000
100010000
100001000
100000100
100000010
100000001
?
111111111
111111111
000000000
111111111
000000000
111111111
000000000
111111111
000000000
?
111111111
000000000
101101110
010010001
000000000
000000000
101101110
010010001
000000000
?
111111111
000000000
00...

result:

ok correct! (10000 test cases)

Test #19:

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

input:

10000
8
0
11111111
10111111
11011111
11101111
11111111
10110111
11111101
11111111
0
11110111
11111111
11111111
11111111
11111111
11111111
11111111
11111111
0
10111111
11111111
01110101
10111111
11111111
11111111
10111111
11111110
0
11111111
01110111
10110111
01110111
11111111
11111111
01110111
11111...

output:

?
00000000
11000000
10100000
10010000
10001000
10000100
10000010
10000001
?
11000000
00000000
00000000
00000000
10000000
10000000
00000000
10000000
?
01000000
10101010
10101010
10101010
00000000
00000100
10101010
00000001
?
00000000
10001000
10010001
10001000
00000000
00000100
10001000
00000000
?
01...

result:

ok correct! (10000 test cases)

Test #20:

score: 0
Accepted
time: 157ms
memory: 5064kb

input:

10000
7
0
1111111
0011111
0101111
0110111
0111011
0111101
0111110
0
0011111
1111111
1111111
1111111
1111111
1111111
1111111
0
1010101
1010101
1010101
1010101
1010101
1010101
1010101
0
1111111
0111111
1111111
0111111
0111111
1010101
1010101
0
0111111
0111111
0111111
1111111
0111111
0111111
0111111
0
...

output:

?
0000000
1100000
1010000
1001000
1000100
1000010
1000001
?
1100000
0000000
0000000
0000000
0000000
0000000
0000000
?
1010101
1010101
1010101
1010101
1010101
1010101
1010101
?
1000100
1000100
1000100
1000100
1000100
1000100
1000100
?
1000000
1000001
1000000
1000001
1000001
1000000
1000000
!
0000100
...

result:

ok correct! (10000 test cases)

Test #21:

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

input:

10000
9
0
010111111
100111111
111111111
110011111
110101111
110110111
110111011
110111101
110111110
0
000000000
000000000
111111111
000000000
111111111
000000000
111111111
000000000
111111111
0
111111111
000000000
111111111
000000000
000000000
000000000
111111111
000000000
000000000
0
000000000
1111...

output:

?
000000000
110000000
101000000
100100000
100010000
100001000
100000100
100000010
100000001
?
111111111
111111111
000000000
111111111
000000000
111111111
000000000
111111111
000000000
?
111111111
000000000
111111111
000000000
000000000
000000000
111111111
000000000
000000000
?
111111111
000000000
00...

result:

ok correct! (10000 test cases)

Test #22:

score: 0
Accepted
time: 159ms
memory: 5056kb

input:

10000
9
0
111111111
111111111
111111111
100101000
111111111
100001000
111111111
111111111
111111111
0
111111111
111111111
111111111
100001000
111111111
111111111
111111111
111111111
111111111
0
101111111
111111111
111111111
111011111
111111111
111111111
111111111
111111101
111111111
0
111111111
1011...

output:

?
000000000
110000000
101000000
100100000
100010000
100001000
100000100
100000010
100000001
?
110000000
100000000
100000000
100000000
100000000
100000000
100000000
100000000
100000000
?
010000000
000000000
000000000
000100000
000000000
000001000
000000000
000000010
000000000
?
000000000
010000000
00...

result:

ok correct! (10000 test cases)

Test #23:

score: 0
Accepted
time: 152ms
memory: 4956kb

input:

10000
6
0
111111
111111
111111
111011
111101
111110
0
111111
111111
111111
011111
011111
011111
0
111111
111111
111111
111111
111111
111111
0
111111
111111
111111
000000
111111
111111
0
111111
111111
111111
000000
111111
000000
0
7
0
0111111
1011111
1101111
1110111
1111011
1111111
1111111
0
1111111
...

output:

?
000000
110000
101000
100100
100010
100001
?
110000
100000
100000
000000
000000
000000
?
000000
111111
000000
111111
000000
111111
?
000000
000000
000000
111111
000000
000000
?
000000
000000
000000
111111
000000
111111
!
000000
111111
000000
000000
000000
000000
?
0000000
1100000
1010000
1001000
10...

result:

ok correct! (10000 test cases)

Test #24:

score: 0
Accepted
time: 110ms
memory: 3920kb

input:

10000
5
0
11111
00111
01011
01101
01110
0
11111
11111
11111
11111
11111
0
10111
11111
01111
11111
01111
0
11111
01111
01111
11101
11110
0
10111
01111
01111
01111
01111
0
5
0
11111
10111
11011
11101
11111
0
10111
11111
11111
11111
11111
0
01111
11111
01111
11111
11111
0
11110
01111
01111
11101
11111
...

output:

?
00000
11000
10100
10010
10001
?
11000
00000
00000
00000
00000
?
01000
10101
10101
10101
10101
?
00000
10001
10010
10001
10010
?
01000
10000
10000
10000
10000
!
10000
00100
01000
00001
00010
?
00000
11000
10100
10010
10001
?
11000
00000
00000
00000
10000
?
10101
10101
10101
10101
00000
?
10010
1000...

result:

ok correct! (10000 test cases)

Test #25:

score: 0
Accepted
time: 87ms
memory: 3956kb

input:

10000
6
0
111111
101111
110111
111111
111011
111110
0
101111
111111
111111
111111
111111
111111
0
111011
111011
011111
110101
111111
011111
0
011111
111111
011011
111111
111111
011011
0
011111
011111
111011
111110
111101
011111
0
6
0
111111
111111
110111
111011
111101
111110
0
101111
111111
111111
1...

output:

?
000000
110000
101000
100100
100010
100001
?
110000
000000
000000
100000
100000
000000
?
101010
101010
101010
000100
000000
101010
?
100010
100010
100100
000000
000000
100100
?
100000
100000
100001
000100
000010
100001
!
001000
000010
000001
000100
100000
010000
?
000000
110000
101000
100100
100010...

result:

ok correct! (10000 test cases)

Test #26:

score: 0
Accepted
time: 113ms
memory: 3952kb

input:

10000
7
0
1111111
1111111
1101111
1110111
1111011
1111101
1011111
0
1011111
1111111
1111111
1111111
1111111
1111111
1111111
0
1111111
1111111
0111111
1111111
0111111
1111111
1111111
0
1010111
1110011
0111111
0111111
1011011
0111111
1111110
0
0111111
1111111
1111110
0111111
0111111
1111101
1111111
0
...

output:

?
0000000
1100000
1010000
1001000
1000100
1000010
1000001
?
1100000
1000000
0000000
0000000
0000000
0000000
1000000
?
1010101
0000000
1010101
1010101
1010101
1010101
0000000
?
1000100
0100000
1001000
1000100
1001000
1000100
0000001
?
1000000
0000000
1000010
1000001
1000000
1000001
0000000
!
0000100
...

result:

ok correct! (10000 test cases)

Test #27:

score: 0
Accepted
time: 181ms
memory: 4884kb

input:

10000
8
0
11111111
00111111
01011111
01101111
01110111
01111011
01111101
01111110
0
11111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111
0
10111111
11111111
01111111
01111111
01111111
11111111
11111111
01111111
0
11111111
01111111
01111111
01111111
11110111
01111111
11101110
11110...

output:

?
00000000
11000000
10100000
10010000
10001000
10000100
10000010
10000001
?
11000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
?
01000000
10101010
10101010
10101010
10101010
10101010
10101010
10101010
?
00000000
10001000
10010001
10010001
10010001
10001000
10001000
10010001
?
01...

result:

ok correct! (10000 test cases)

Test #28:

score: 0
Accepted
time: 107ms
memory: 5076kb

input:

10000
8
0
11111111
10111111
11011111
11110100
11111100
11111011
11110110
11110101
0
10111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111
0
11111110
01110101
01110101
11101111
11111111
01110101
11111111
11011111
0
01110111
01111110
01111110
11111111
11111111
11111101
11101111
11111...

output:

?
00000000
11000000
10100000
10010000
10001000
10000100
10000010
10000001
?
11000000
00000000
00000000
10000000
10000000
00000000
10000000
10000000
?
10101010
10101010
10101010
00010000
00000000
10101010
00000000
00000001
?
10001000
10010001
10010001
00000000
00000000
10010001
00000010
00000000
?
10...

result:

ok correct! (10000 test cases)

Test #29:

score: 0
Accepted
time: 198ms
memory: 5104kb

input:

10000
8
0
11111111
10111111
11011111
11111011
11110111
11111111
11111101
11111110
0
10111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111
0
11111011
01111111
01111111
11101111
11111011
11010101
01111111
11111011
0
11101010
11110011
01111111
11111111
01111111
11100110
11110011
01111...

output:

?
00000000
11000000
10100000
10010000
10001000
10000100
10000010
10000001
?
11000000
00000000
00000000
10000000
00000000
10000000
00000000
00000000
?
10101010
10101010
10101010
00010000
10101010
00000100
10101010
10101010
?
10001000
10010001
10010001
00000000
10001000
00000100
10010001
10001000
?
10...

result:

ok correct! (10000 test cases)

Test #30:

score: 0
Accepted
time: 170ms
memory: 4900kb

input:

10000
8
0
11111111
10111111
11101101
11011101
11110111
11001101
11001111
11111110
0
10111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111
0
01011101
11101111
11111111
11110111
01011101
11111011
11111111
01011101
0
11010101
11011100
11110100
11111111
01101111
11111011
11010110
01101...

output:

?
00000000
11000000
10100000
10010000
10001000
10000100
10000010
10000001
?
11000000
00000000
10000000
10000000
00000000
10000000
10000000
00000000
?
10101010
10101010
00000000
00010000
10101010
00000100
00000000
10101010
?
10010001
10001000
00100000
00000000
10010001
00000100
00000010
10010001
?
10...

result:

ok correct! (10000 test cases)

Test #31:

score: 0
Accepted
time: 181ms
memory: 5116kb

input:

10000
8
0
11111111
00111111
01011111
01101111
01110111
01111011
01111101
01111110
0
11111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111
0
10111111
01111111
01111111
11111111
01111111
11111111
01111111
11111111
0
11111111
11110111
11110111
01111111
01111111
11101110
01111111
01111...

output:

?
00000000
11000000
10100000
10010000
10001000
10000100
10000010
10000001
?
11000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
?
01000000
10101010
10101010
10101010
10101010
10101010
10101010
10101010
?
00000000
10010001
10010001
10001000
10010001
10001000
10010001
10001000
?
01...

result:

ok correct! (10000 test cases)

Test #32:

score: 0
Accepted
time: 178ms
memory: 5068kb

input:

10000
9
0
111111111
101111111
110111111
111011111
111111111
111110111
111111011
111111101
111111110
0
111111111
111111111
111111111
111111111
101111111
111111111
111111111
111111111
111111111
0
110101010
011111111
011111111
101111111
111111111
101111111
011111111
101111111
101111111
0
111111111
0111...

output:

?
000000000
110000000
101000000
100100000
100010000
100001000
100000100
100000010
100000001
?
110000000
000000000
000000000
000000000
100000000
000000000
000000000
000000000
000000000
?
010000000
101010101
101010101
101010101
000000000
101010101
101010101
101010101
101010101
?
000000000
100100010
10...

result:

ok correct! (10000 test cases)

Test #33:

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

input:

10000
9
0
111111111
111111111
010111111
011011111
011101111
011110111
011111011
011111101
011111110
0
111111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
0
101111111
111111111
111111111
011111111
011111111
111111111
111111111
111111111
011111111
0
111111111
1110...

output:

?
000000000
110000000
101000000
100100000
100010000
100001000
100000100
100000010
100000001
?
110000000
100000000
000000000
000000000
000000000
000000000
000000000
000000000
000000000
?
010000000
000000000
101010101
101010101
101010101
101010101
101010101
101010101
101010101
?
000000000
010000000
10...

result:

ok correct! (10000 test cases)

Test #34:

score: 0
Accepted
time: 169ms
memory: 5020kb

input:

10000
9
0
111111111
101111111
110111111
111011111
111111111
111110111
111111011
111111101
111111110
0
101111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
0
011111111
111111111
111111111
111111111
111111111
011111111
111111111
011111111
011111111
0
111101110
0111...

output:

?
000000000
110000000
101000000
100100000
100010000
100001000
100000100
100000010
100000001
?
110000000
000000000
000000000
000000000
100000000
000000000
000000000
000000000
000000000
?
101010101
101010101
101010101
101010101
000000000
101010101
101010101
101010101
101010101
?
100100010
100010001
10...

result:

ok correct! (10000 test cases)

Test #35:

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

input:

10000
9
0
111111111
101111111
110111111
111011111
111101111
111110111
111111111
111111101
111111110
0
111111111
111111111
111111111
111111111
111111111
111111111
101111111
111111111
111111111
0
110101010
011111111
101111111
101111111
101111111
011111111
111111111
101111111
011111111
0
111111111
1111...

output:

?
000000000
110000000
101000000
100100000
100010000
100001000
100000100
100000010
100000001
?
110000000
000000000
000000000
000000000
000000000
000000000
100000000
000000000
000000000
?
010000000
101010101
101010101
101010101
101010101
101010101
000000000
101010101
101010101
?
000000000
100100010
10...

result:

ok correct! (10000 test cases)

Test #36:

score: 0
Accepted
time: 167ms
memory: 5100kb

input:

10000
9
0
111111111
111111011
110111111
111011111
111101111
111110111
111111111
111111101
111111110
0
101111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
0
111111111
111111111
011111011
111111111
011111011
011111011
111111111
111111111
011111011
0
111011001
1011...

output:

?
000000000
110000000
101000000
100100000
100010000
100001000
100000100
100000010
100000001
?
110000000
100000000
000000000
000000000
000000000
000000000
100000000
000000000
000000000
?
101010101
000000000
101010101
101010101
101010101
101010101
000000000
101010101
101010101
?
100010001
010000000
10...

result:

ok correct! (10000 test cases)

Test #37:

score: 0
Accepted
time: 114ms
memory: 3920kb

input:

10000
7
0
1111111
1011111
1111111
1110111
1111011
1111101
1111110
0
1011111
0111111
1111111
1111111
1111111
1111111
1111111
0
1111111
0110001
1111111
1111111
1111111
1111111
1111111
0
1111111
1010011
1111111
0111101
1111111
1111111
1111111
0
1111111
0101010
1111111
1111111
1011101
1111111
1111111
0
...

output:

?
0000000
1100000
1010000
1001000
1000100
1000010
1000001
?
1100000
0000000
1000000
0000000
0000000
0000000
0000000
?
0000000
1111111
0000000
1111111
0000000
1111111
0000000
?
0000000
1111111
1001110
0110001
0000000
0000000
1001110
?
0000000
1111111
0000000
0000000
0001100
0100000
1000010
!
0000100
...

result:

ok correct! (10000 test cases)

Test #38:

score: 0
Accepted
time: 133ms
memory: 3988kb

input:

10000
8
0
11111111
10111111
11111111
11111111
11110111
11111011
11111101
11111110
0
11111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111
0
11011101
11111111
11111111
10011101
01110111
01110111
10111111
10111111
0
11111111
01110111
11011111
11111111
01101111
11111111
01110111
01110...

output:

?
00000000
11000000
10100000
10010000
10001000
10000100
10000010
10000001
?
11000000
00000000
10000000
10000000
00000000
00000000
00000000
00000000
?
01000000
10101010
00000000
00010000
10101010
10101010
10101010
10101010
?
00000000
10001000
00100000
00000000
10010001
10010001
10001000
10001000
?
01...

result:

ok correct! (10000 test cases)

Test #39:

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

input:

10000
8
0
11111111
10111111
11011111
11101111
11110111
11111011
11111111
11111110
0
11111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111
0
10111111
01111101
11111111
01111101
01111101
01111101
11111111
11111111
0
11111111
11110111
11101111
01111111
11110111
01111111
11111101
01111...

output:

?
00000000
11000000
10100000
10010000
10001000
10000100
10000010
10000001
?
11000000
00000000
00000000
00000000
00000000
00000000
10000000
00000000
?
01000000
10101010
10101010
10101010
10101010
10101010
00000000
10101010
?
00000000
10010001
10001000
10010001
10010001
10010001
00000010
10001000
?
01...

result:

ok correct! (10000 test cases)

Test #40:

score: 0
Accepted
time: 172ms
memory: 3984kb

input:

10000
8
0
11111111
10111111
11011111
11101111
11110111
11111111
11111101
11111101
0
10111111
11111111
11111111
11111111
11111111
11111111
11111111
11111101
0
11111111
11111111
01111101
01111101
01111101
11111111
01111101
11111110
0
01111111
11111101
11111101
01111111
01111111
11111111
11111101
11111...

output:

?
00000000
11000000
10100000
10010000
10001000
10000100
10000010
10000001
?
11000000
00000000
00000000
00000000
00000000
10000000
00000000
10000000
?
10101010
10101010
10101010
10101010
10101010
00000100
10101010
00000001
?
10001000
10001000
10010001
10010001
10010001
00000100
10010001
00000000
?
10...

result:

ok correct! (10000 test cases)

Test #41:

score: 0
Accepted
time: 210ms
memory: 5100kb

input:

10000
9
0
111111111
111110111
010111111
011011111
111111111
111111111
011111011
011111101
011111110
0
111111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
0
101111111
111111111
111110111
111110111
111111111
110111010
011111111
111110111
111111111
0
111111111
1111...

output:

?
000000000
110000000
101000000
100100000
100010000
100001000
100000100
100000010
100000001
?
110000000
100000000
000000000
000000000
100000000
100000000
000000000
000000000
000000000
?
010000000
000000000
101010101
101010101
000000000
000001000
101010101
101010101
101010101
?
000000000
010000000
10...

result:

ok correct! (10000 test cases)

Test #42:

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

input:

10000
9
0
111111111
110111101
101111101
100111101
111101111
100111101
111111011
111111101
111111111
0
101111111
111111111
111111111
111111111
111111111
111111101
111111111
111111111
111111111
0
111111101
111111111
111111111
111111001
010111111
111110111
111111101
111111101
111111111
0
100111101
1101...

output:

?
000000000
110000000
101000000
100100000
100010000
100001000
100000100
100000010
100000001
?
110000000
100000000
100000000
100000000
000000000
100000000
000000000
000000000
100000000
?
101010101
000000000
000000000
000100000
101010101
000001000
101010101
101010101
000000000
?
100010001
010000000
00...

result:

ok correct! (10000 test cases)

Test #43:

score: 0
Accepted
time: 222ms
memory: 4960kb

input:

10000
9
0
111111111
101111111
111111111
111011111
111101111
111110111
111111111
111111101
111111110
0
101111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
0
111111111
111111111
111111111
111111111
011111111
111111111
111111111
111111111
111111111
0
011111111
0111...

output:

?
000000000
110000000
101000000
100100000
100010000
100001000
100000100
100000010
100000001
?
110000000
000000000
100000000
000000000
000000000
000000000
100000000
000000000
000000000
?
101010101
101010101
000000000
101010101
101010101
101010101
000000000
101010101
101010101
?
100010001
100010001
00...

result:

ok correct! (10000 test cases)

Test #44:

score: 0
Accepted
time: 120ms
memory: 3916kb

input:

10000
7
0
1111111
1111111
1101111
1110111
1111011
1111111
1111110
0
1011111
1111111
1111111
1111111
1111111
1111111
1111111
0
0111111
1111111
0111111
1111111
1111111
1111101
1111111
0
1111011
1111111
0111111
0111111
0111111
1111101
1111111
0
0111111
1111111
1111111
1111111
0111111
1111111
0111111
0
...

output:

?
0000000
1100000
1010000
1001000
1000100
1000010
1000001
?
1100000
1000000
0000000
0000000
0000000
1000000
0000000
?
1010101
0000000
1010101
1010101
1010101
0000010
1010101
?
1001000
0100000
1001000
1000100
1000100
0000010
1000100
?
1000000
0000000
1000010
1000001
1000001
0000000
1000000
!
0001000
...

result:

ok correct! (10000 test cases)

Test #45:

score: 0
Accepted
time: 130ms
memory: 3912kb

input:

10000
8
0
11111111
11111111
11011111
11101111
11111111
11111011
11111101
11111110
0
10111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111
0
01111101
11111111
01111101
11111111
11111111
01111101
01111101
11111111
0
01111111
10111111
11110111
11101110
11111111
01111111
11111111
01111...

output:

?
00000000
11000000
10100000
10010000
10001000
10000100
10000010
10000001
?
11000000
10000000
00000000
00000000
10000000
00000000
00000000
00000000
?
10101010
00000000
10101010
10101010
00000000
10101010
10101010
10101010
?
10010001
01000000
10010001
10001000
00000000
10010001
10010001
10001000
?
10...

result:

ok correct! (10000 test cases)

Test #46:

score: 0
Accepted
time: 127ms
memory: 3956kb

input:

10000
8
0
11111111
00111111
11111111
01101111
11111111
01111011
01111101
11111111
0
11111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111
0
10111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111
0
11111111
01111111
11111111
11111111
11111111
11111111
11111111
11111...

output:

?
00000000
11000000
10100000
10010000
10001000
10000100
10000010
10000001
?
11000000
00000000
10000000
00000000
10000000
00000000
00000000
10000000
?
01000000
10101010
00000000
10101010
00000000
10101010
10101010
00000001
?
00000000
10001000
00100000
10001000
00000000
10001000
10001000
00000000
?
01...

result:

ok correct! (10000 test cases)

Test #47:

score: 0
Accepted
time: 132ms
memory: 3920kb

input:

10000
8
0
11111111
10111111
11011111
11111111
11110111
11111011
11111101
11111110
0
10111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111
0
01111111
11111111
01111111
11101111
01111111
11111111
01111111
11111111
0
11111111
01111111
01111111
11111111
01111111
11101110
11111111
11111...

output:

?
00000000
11000000
10100000
10010000
10001000
10000100
10000010
10000001
?
11000000
00000000
00000000
10000000
00000000
00000000
00000000
00000000
?
10101010
10101010
10101010
00010000
10101010
10101010
10101010
10101010
?
10010001
10001000
10010001
00000000
10010001
10001000
10010001
10001000
?
10...

result:

ok correct! (10000 test cases)

Test #48:

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

input:

10000
9
0
111111111
101111111
110111111
111011111
111101111
111110111
111111111
111111101
111111111
0
101111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
0
111111111
111111111
011111111
111111111
011111111
011111111
111111111
111111111
111111111
0
111111111
1111...

output:

?
000000000
110000000
101000000
100100000
100010000
100001000
100000100
100000010
100000001
?
110000000
000000000
000000000
000000000
000000000
000000000
100000000
000000000
100000000
?
101010101
101010101
101010101
101010101
101010101
101010101
000000000
101010101
000000000
?
100010001
100010001
10...

result:

ok correct! (10000 test cases)

Test #49:

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

input:

10000
9
0
111111111
111111111
111111111
111111111
111101111
111110111
111111011
111111111
111111111
0
101111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
0
111111101
111111111
111111111
111011111
111111111
111111111
011101110
111111111
111111111
0
011101110
1111...

output:

?
000000000
110000000
101000000
100100000
100010000
100001000
100000100
100000010
100000001
?
110000000
100000000
100000000
100000000
000000000
000000000
000000000
100000000
100000000
?
101010101
000000000
000000000
000100000
101010101
101010101
101010101
000000010
000000000
?
100010001
010000000
00...

result:

ok correct! (10000 test cases)

Test #50:

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

input:

10000
9
0
111111111
111111111
110111111
111111111
111111111
111110111
111111011
111111101
111111111
0
111111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
0
111111111
111111111
011111110
111111111
111111111
111111111
111111111
111111111
111111111
0
111111111
1111...

output:

?
000000000
110000000
101000000
100100000
100010000
100001000
100000100
100000010
100000001
?
110000000
100000000
000000000
100000000
100000000
000000000
000000000
000000000
100000000
?
010000000
000000000
101010101
000100000
000000000
101010101
101010101
101010101
000000000
?
000000000
010000000
10...

result:

ok correct! (10000 test cases)

Test #51:

score: 0
Accepted
time: 113ms
memory: 3964kb

input:

10000
7
0
1111111
1111111
1111111
1111111
1111111
1111111
1111111
0
1111111
1111111
1111111
1111111
1111111
1111111
1111111
0
1111111
1111111
1111111
1111111
1111111
1111111
1111111
0
1111111
1111111
1111111
1111111
1111111
1111111
1111111
0
1111111
1111111
1111111
1111111
1111011
1111111
1111111
0
...

output:

?
0000000
1100000
1010000
1001000
1000100
1000010
1000001
?
1100000
1000000
1000000
1000000
1000000
1000000
1000000
?
0100000
0000000
0000000
0001000
0000000
0000010
0000000
?
0000000
0100000
0010000
0000000
0000000
0000010
0000001
?
0100000
0000000
0010000
0001000
0000100
0000000
0000000
!
0100000
...

result:

ok correct! (10000 test cases)

Test #52:

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

input:

10000
8
0
11111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111
0
11111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111
0
11111111
11111111
11111111
11111111
11111111
11111111
11111111
11111110
0
11111111
11111111
11111111
11111111
11111111
11111111
11111111
11111...

output:

?
00000000
11000000
10100000
10010000
10001000
10000100
10000010
10000001
?
11000000
10000000
10000000
10000000
10000000
10000000
10000000
10000000
?
01000000
00000000
00000000
00010000
00000000
00000100
00000000
00000001
?
00000000
01000000
00100000
00000000
00000000
00000100
00000010
00000000
?
01...

result:

ok correct! (10000 test cases)

Test #53:

score: 0
Accepted
time: 153ms
memory: 3908kb

input:

10000
8
0
11111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111
0
11111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111
0
11111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111
0
11111111
10111111
11011111
11111111
11111111
11111111
11111111
11111...

output:

?
00000000
11000000
10100000
10010000
10001000
10000100
10000010
10000001
?
11000000
10000000
10000000
10000000
10000000
10000000
10000000
10000000
?
01000000
00000000
00000000
00010000
00000000
00000100
00000000
00000001
?
00000000
01000000
00100000
00000000
00000000
00000100
00000010
00000000
?
01...

result:

ok correct! (10000 test cases)

Test #54:

score: 0
Accepted
time: 122ms
memory: 3912kb

input:

10000
8
0
11111111
10111111
11111111
11101111
11111111
11111111
11111111
11111111
0
11111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111
0
11111111
11111111
11111111
11111111
11111111
11111111
11111111
11111110
0
11111111
11111111
11111111
01111111
11111111
11111111
11111111
11111...

output:

?
00000000
11000000
10100000
10010000
10001000
10000100
10000010
10000001
?
11000000
00000000
10000000
00000000
10000000
10000000
10000000
10000000
?
01000000
10101010
00000000
10101010
00000000
00000100
00000000
00000001
?
00000000
10001000
00100000
10001000
00000000
00000100
00000010
00000000
?
01...

result:

ok correct! (10000 test cases)

Test #55:

score: 0
Accepted
time: 77ms
memory: 3952kb

input:

10000
8
0
11111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111
0
11111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111
0
11111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111
0
11111111
10111111
11111111
11111111
11111111
11111111
11111111
11111...

output:

?
00000000
11000000
10100000
10010000
10001000
10000100
10000010
10000001
?
11000000
10000000
10000000
10000000
10000000
10000000
10000000
10000000
?
01000000
00000000
00000000
00010000
00000000
00000100
00000000
00000001
?
00000000
01000000
00100000
00000000
00000000
00000100
00000010
00000000
?
01...

result:

ok correct! (10000 test cases)

Test #56:

score: 0
Accepted
time: 155ms
memory: 5192kb

input:

10000
9
0
111111111
111111111
111111111
111011111
111111111
111111111
111111111
111111111
111111111
0
111111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
0
111111111
111111111
111111111
010101010
111111111
111110111
111111111
111111111
111111111
0
111111111
1111...

output:

?
000000000
110000000
101000000
100100000
100010000
100001000
100000100
100000010
100000001
?
110000000
100000000
100000000
000000000
100000000
100000000
100000000
100000000
100000000
?
010000000
000000000
000000000
101010101
000000000
000001000
000000000
000000010
000000000
?
000000000
010000000
00...

result:

ok correct! (10000 test cases)

Test #57:

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

input:

10000
9
0
111111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
0
111111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
0
101111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
0
111111111
1011...

output:

?
000000000
110000000
101000000
100100000
100010000
100001000
100000100
100000010
100000001
?
110000000
100000000
100000000
100000000
100000000
100000000
100000000
100000000
100000000
?
010000000
000000000
000000000
000100000
000000000
000001000
000000000
000000010
000000000
?
000000000
010000000
00...

result:

ok correct! (10000 test cases)

Test #58:

score: 0
Accepted
time: 133ms
memory: 5052kb

input:

10000
9
0
111111111
111111111
111111111
111111111
111111111
111110111
111111111
111111111
111111111
0
111111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
0
111111111
111111111
111111111
111111111
111111111
111111111
111111111
111111101
111111111
0
111111111
1011...

output:

?
000000000
110000000
101000000
100100000
100010000
100001000
100000100
100000010
100000001
?
110000000
100000000
100000000
100000000
100000000
000000000
100000000
100000000
100000000
?
010000000
000000000
000000000
000100000
000000000
101010101
000000000
000000010
000000000
?
000000000
010000000
00...

result:

ok correct! (10000 test cases)

Test #59:

score: 0
Accepted
time: 91ms
memory: 5132kb

input:

10000
9
0
111111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
0
111111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
0
111111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
0
111111111
1111...

output:

?
000000000
110000000
101000000
100100000
100010000
100001000
100000100
100000010
100000001
?
110000000
100000000
100000000
100000000
100000000
100000000
100000000
100000000
100000000
?
010000000
000000000
000000000
000100000
000000000
000001000
000000000
000000010
000000000
?
000000000
010000000
00...

result:

ok correct! (10000 test cases)

Test #60:

score: 0
Accepted
time: 142ms
memory: 5064kb

input:

10000
7
0
1111111
1111111
1111111
1111111
1111111
1111111
1111111
0
1111111
1111111
1111111
1111111
1111111
1111111
1111111
0
1111111
1111111
1111111
1111111
1111111
1111111
1111111
0
1111111
1111111
1111111
1111111
1111111
1111111
1111111
0
1111111
1111111
1111111
1111111
1111011
1111111
1111111
0
...

output:

?
0000000
1100000
1010000
1001000
1000100
1000010
1000001
?
1100000
1000000
1000000
1000000
1000000
1000000
1000000
?
0100000
0000000
0000000
0001000
0000000
0000010
0000000
?
0000000
0100000
0010000
0000000
0000000
0000010
0000001
?
0100000
0000000
0010000
0001000
0000100
0000000
0000000
!
0100000
...

result:

ok correct! (10000 test cases)

Test #61:

score: 0
Accepted
time: 121ms
memory: 5108kb

input:

10000
7
0
1111111
1011111
1111110
1110111
1111111
1111111
1111111
0
1111111
1111111
1111111
1111111
1111111
1111111
1111111
0
1111111
1111111
1111111
1111111
1111111
1111111
1111111
0
1111111
1111111
1101111
1111111
1111111
1111111
1111111
0
1111111
0111111
1101111
0111111
1111011
1111111
1111111
0
...

output:

?
0000000
1100000
1010000
1001000
1000100
1000010
1000001
?
1100000
0000000
1000000
0000000
1000000
1000000
1000000
?
0100000
1010101
0000000
1010101
0000000
0000010
0000000
?
0000000
1000100
0010000
1000100
0000000
0000010
0000001
?
0100000
1000000
0010000
1000000
0000100
0000000
0000000
!
0100000
...

result:

ok correct! (10000 test cases)

Test #62:

score: 0
Accepted
time: 160ms
memory: 5056kb

input:

10000
9
0
111111111
101111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
0
111111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
0
111111111
111111111
111111111
111111111
111111111
111110111
111111111
111111111
111111111
0
111111111
1111...

output:

?
000000000
110000000
101000000
100100000
100010000
100001000
100000100
100000010
100000001
?
110000000
000000000
100000000
100000000
100000000
100000000
100000000
100000000
100000000
?
010000000
101010101
000000000
000100000
000000000
000001000
000000000
000000010
000000000
?
000000000
100010001
00...

result:

ok correct! (10000 test cases)

Test #63:

score: 0
Accepted
time: 137ms
memory: 4904kb

input:

10000
8
0
11111111
11111111
11111111
11111111
11111111
11111011
11111111
11111111
0
11111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111
0
10111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111
0
11111111
10111111
11111111
11111111
11111111
11111111
11111111
11111...

output:

?
00000000
11000000
10100000
10010000
10001000
10000100
10000010
10000001
?
11000000
10000000
10000000
10000000
10000000
00000000
10000000
10000000
?
01000000
00000000
00000000
00010000
00000000
10101010
00000000
00000001
?
00000000
01000000
00100000
00000000
00000000
10001000
00000010
00000000
?
01...

result:

ok correct! (10000 test cases)

Test #64:

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

input:

10000
9
0
111111111
101111111
111111111
111011111
111101111
111110111
111111111
111111111
111111110
0
111111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
0
101111111
111111111
111111111
111111111
111111111
111111111
111111111
111111101
011111111
0
111111111
0111...

output:

?
000000000
110000000
101000000
100100000
100010000
100001000
100000100
100000010
100000001
?
110000000
000000000
100000000
000000000
000000000
000000000
100000000
100000000
000000000
?
010000000
101010101
000000000
101010101
101010101
101010101
000000000
000000010
101010101
?
000000000
100010001
00...

result:

ok correct! (10000 test cases)

Test #65:

score: 0
Accepted
time: 146ms
memory: 4652kb

input:

10000
6
0
111111
101111
110111
111100
111101
111101
0
101111
111111
111111
111111
111111
111111
0
011101
111110
011101
110100
011101
111111
0
111100
011101
011111
111111
111100
111111
0
011111
011111
011110
111101
011111
111111
0
6
0
111111
001111
010111
011011
011101
011110
0
001111
111111
111111
1...

output:

?
000000
110000
101000
100100
100010
100001
?
110000
000000
000000
100000
000000
100000
?
101010
101010
101010
000100
101010
000001
?
100100
100010
100100
000000
100100
000001
?
100000
100000
100001
000100
100000
000000
!
000100
001000
010000
000100
000100
000001
?
000000
110000
101000
100100
100010...

result:

ok correct! (10000 test cases)

Test #66:

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

input:

10000
7
0
1111111
1110010
1101111
1111010
1111011
1111101
1110011
0
1111010
1111010
1111111
1111111
1111111
1111111
1111010
0
1011111
1111111
0111010
1101010
1110111
0111010
1111111
0
1111111
1011111
0110111
1111111
0111011
0110111
1111110
0
1011111
1111111
1110010
1111000
0111110
0111111
1111111
0
...

output:

?
0000000
1100000
1010000
1001000
1000100
1000010
1000001
?
1100000
1000000
0000000
1000000
0000000
0000000
1000000
?
0100000
0000000
1010101
0001000
1010101
1010101
0000000
?
0000000
0100000
1001000
0000000
1000100
1001000
0000001
?
0100000
0000000
1000010
0001000
1000001
1000010
0000000
!
1000000
...

result:

ok correct! (10000 test cases)

Test #67:

score: 0
Accepted
time: 117ms
memory: 3920kb

input:

10000
7
0
1111111
0011111
0101111
0110111
1111101
1111111
0111110
0
0011111
1111111
1111111
1111111
0111111
0111111
1111111
0
1111101
1111101
1111101
1111101
1111111
1111111
1111101
0
1111101
1111101
1111101
1111101
1111111
1111111
1111101
0
0111111
0111111
0111111
0111111
0111111
1111111
0111111
0
...

output:

?
0000000
1100000
1010000
1001000
1000100
1000010
1000001
?
1100000
0000000
0000000
0000000
1000000
1000000
0000000
?
1010101
1010101
1010101
1010101
0000000
0000010
1010101
?
1000100
1000100
1000100
1000100
0000000
0000010
1000100
?
1000000
1000000
1000000
1000000
0000100
0000000
1000000
!
0000100
...

result:

ok correct! (10000 test cases)

Test #68:

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

input:

10000
7
0
1111111
0011111
0101111
0110111
0111011
0111101
0111110
0
1111111
1111111
1111111
1111111
1111111
1111111
1111111
0
1111111
1011101
0111010
1011101
1011101
0111010
0111010
0
1111111
0111011
1111101
0111011
0111011
1111101
1111101
0
1111111
0111110
0111111
0111110
0111110
0111111
0111111
0
...

output:

?
0000000
1100000
1010000
1001000
1000100
1000010
1000001
?
1100000
0000000
0000000
0000000
0000000
0000000
0000000
?
0100000
1010101
1010101
1010101
1010101
1010101
1010101
?
0000000
1000100
1001000
1000100
1000100
1001000
1001000
?
0100000
1000001
1000000
1000001
1000001
1000000
1000000
!
0100000
...

result:

ok correct! (10000 test cases)

Test #69:

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

input:

10000
7
0
1111111
1011111
1101111
1001111
1111011
1001111
1111110
0
1011111
1111111
1111111
1001111
1111111
1111111
1111111
0
0101111
1111111
1011111
1110111
0101111
1001010
1011111
0
0110111
1111111
0111111
1111111
0110111
1001011
1001111
0
1001110
0111111
1001111
1110111
1001110
1111111
0111111
0
...

output:

?
0000000
1100000
1010000
1001000
1000100
1000010
1000001
?
1100000
0000000
0000000
1000000
0000000
1000000
0000000
?
1010101
1010101
1010101
0001000
1010101
0000010
1010101
?
1001000
1000100
1000100
0000000
1001000
0000010
1000100
?
1000010
1000000
1000001
0001000
1000010
0000000
1000000
!
0000010
...

result:

ok correct! (10000 test cases)

Test #70:

score: 0
Accepted
time: 134ms
memory: 3996kb

input:

10000
8
0
11111111
10111111
11011111
11111100
11110111
11111011
11111110
11111110
0
10111111
11111111
11111111
11111110
11111111
11111111
11111111
11111111
0
01111101
11111110
01111101
11101111
11111110
01111101
11111111
01111101
0
11110101
11101100
01111110
11111111
01111111
11110101
11100110
01111...

output:

?
00000000
11000000
10100000
10010000
10001000
10000100
10000010
10000001
?
11000000
00000000
00000000
10000000
00000000
00000000
10000000
00000000
?
10101010
10101010
10101010
00010000
10101010
10101010
00000000
10101010
?
10010001
10001000
10010001
00000000
10001000
10010001
00000010
10010001
?
10...

result:

ok correct! (10000 test cases)

Test #71:

score: 0
Accepted
time: 156ms
memory: 3988kb

input:

10000
8
0
11111111
10111111
11011111
11101111
11111111
11111011
11111101
11111110
0
11110111
11111111
11111111
11111111
10110111
11111111
11111111
11111111
0
11010101
01110111
01110111
10111111
11111111
01110111
10111111
10111111
0
11111111
11110111
01111111
01110111
11111111
11110111
01110111
01110...

output:

?
00000000
11000000
10100000
10010000
10001000
10000100
10000010
10000001
?
11000000
00000000
00000000
00000000
10000000
00000000
00000000
00000000
?
01000000
10101010
10101010
10101010
00000000
10101010
10101010
10101010
?
00000000
10010001
10010001
10001000
00000000
10010001
10001000
10001000
?
01...

result:

ok correct! (10000 test cases)

Test #72:

score: 0
Accepted
time: 139ms
memory: 3988kb

input:

10000
8
0
11111111
11111111
11011111
11101111
11111111
11111011
11111111
11111111
0
10111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111
0
11111111
11111111
01110111
01110111
11111111
01110111
11111111
11111111
0
01110111
10111111
01101110
01101110
11111111
01101110
11111111
11111...

output:

?
00000000
11000000
10100000
10010000
10001000
10000100
10000010
10000001
?
11000000
10000000
00000000
00000000
10000000
00000000
10000000
10000000
?
10101010
00000000
10101010
10101010
00000000
10101010
00000000
00000001
?
10001000
01000000
10010001
10010001
00000000
10010001
00000010
00000000
?
10...

result:

ok correct! (10000 test cases)

Test #73:

score: 0
Accepted
time: 102ms
memory: 3900kb

input:

10000
8
0
01011111
10011111
11111111
11001111
11110111
11011111
11011101
11011110
0
10000000
10000000
11111111
10000000
11111111
11111111
01111111
10000000
0
01111110
10010001
11111111
00010001
11111111
11111111
11111110
00010001
0
10000001
01111110
11111111
01111110
11111111
11111110
00000000
01111...

output:

?
00000000
11000000
10100000
10010000
10001000
10000100
10000010
10000001
?
11111111
11111111
00000000
11111111
00000000
11111111
00000000
11111111
?
11111111
00000000
01111111
10000000
00000000
00000000
01111111
10000000
?
11111111
00000000
00000000
00000000
00000001
10000000
01111110
00000000
!
00...

result:

ok correct! (10000 test cases)

Test #74:

score: 0
Accepted
time: 155ms
memory: 3956kb

input:

10000
8
0
11111111
11111111
11011111
11101111
11111111
11011101
11111111
11111111
0
11111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111
0
11111111
11111111
11111111
11111111
11111111
11111111
11111111
11111110
0
11111111
11111111
11111111
11111111
11111111
11111111
11111101
11111...

output:

?
00000000
11000000
10100000
10010000
10001000
10000100
10000010
10000001
?
11000000
10000000
00000000
00000000
10000000
10000000
10000000
10000000
?
01000000
00000000
10101010
10101010
00000000
00000100
00000000
00000001
?
00000000
01000000
10001000
10001000
00000000
00000100
00000010
00000000
?
01...

result:

ok correct! (10000 test cases)

Test #75:

score: 0
Accepted
time: 119ms
memory: 3912kb

input:

10000
8
0
11111111
10111101
11111101
11101101
11110101
11111001
11111111
11111100
0
10111111
01111111
11111111
01111111
01111111
01111111
11111111
01111111
0
11111111
00000000
11111111
00000000
11111111
00000000
11111111
00000000
0
11111111
11110011
11111111
00001100
00001100
00001100
11111111
00001...

output:

?
00000000
11000000
10100000
10010000
10001000
10000100
10000010
10000001
?
11000000
00000000
10000000
00000000
00000000
00000000
10000000
00000000
?
00000000
11111111
00000000
11111111
00000000
11111111
00000000
11111111
?
00000000
11111111
11111111
00000000
00000000
00000000
11111111
00000000
?
00...

result:

ok correct! (10000 test cases)

Test #76:

score: 0
Accepted
time: 126ms
memory: 4016kb

input:

10000
8
0
11111111
00111111
01011111
11111111
01110111
01111011
11111111
11111111
0
11111111
01111111
01111111
11111111
11111111
01111111
11111111
11111111
0
11111111
00011001
11100110
11111111
11111111
00011001
11111111
11111111
0
11111111
01011111
01000110
11111111
11111111
11100110
11100110
11111...

output:

?
00000000
11000000
10100000
10010000
10001000
10000100
10000010
10000001
?
11000000
00000000
00000000
10000000
00000000
00000000
10000000
10000000
?
00000000
11111111
00000000
11111111
00000000
11111111
00000000
11111111
?
00000000
11111111
11100110
00011001
00000000
00000000
11100110
00011001
?
00...

result:

ok correct! (10000 test cases)

Test #77:

score: 0
Accepted
time: 155ms
memory: 5052kb

input:

10000
9
0
111111111
101111111
110111111
110111111
111101111
111110111
111111011
111111101
111111110
0
101111111
111111111
111111111
110111111
111111111
111111111
111111111
111111111
111111111
0
111111111
010111111
111111111
111011111
010111111
010111111
010111111
111111111
010111111
0
110011101
1101...

output:

?
000000000
110000000
101000000
100100000
100010000
100001000
100000100
100000010
100000001
?
110000000
000000000
000000000
100000000
000000000
000000000
000000000
000000000
000000000
?
101010101
101010101
101010101
000100000
101010101
101010101
101010101
101010101
101010101
?
100010001
100100010
10...

result:

ok correct! (10000 test cases)

Test #78:

score: 0
Accepted
time: 183ms
memory: 5000kb

input:

10000
9
0
111111111
101111111
110111111
111111111
111101111
111110111
111111011
111111111
111111110
0
101111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
0
111111111
111111111
011111111
111011111
111111111
111111111
011111111
110101110
111111111
0
011111111
0111...

output:

?
000000000
110000000
101000000
100100000
100010000
100001000
100000100
100000010
100000001
?
110000000
000000000
000000000
100000000
000000000
000000000
000000000
100000000
000000000
?
101010101
101010101
101010101
000100000
101010101
101010101
101010101
000000010
101010101
?
100010001
100010001
10...

result:

ok correct! (10000 test cases)

Test #79:

score: 0
Accepted
time: 168ms
memory: 5048kb

input:

10000
9
0
111111111
001111111
101111101
100111101
011101111
011110111
111111111
011111101
011111110
0
001111111
111111111
011111111
011111111
111111111
111111111
011111111
111111111
111111111
0
010101111
111111111
111111111
001111100
101111101
010101111
111111111
010101111
010101111
0
100111110
1111...

output:

?
000000000
110000000
101000000
100100000
100010000
100001000
100000100
100000010
100000001
?
110000000
000000000
100000000
100000000
000000000
000000000
100000000
000000000
000000000
?
101010101
101010101
000000000
000100000
101010101
101010101
000000000
101010101
101010101
?
100100010
100010001
00...

result:

ok correct! (10000 test cases)

Test #80:

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

input:

10000
9
0
111111111
111111111
110111111
111011111
111101111
111111111
111111111
111111101
111111111
0
101111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
111111111
0
111111111
111111111
111111111
010111110
111111111
111111111
111111111
111111111
111111111
0
111111111
1011...

output:

?
000000000
110000000
101000000
100100000
100010000
100001000
100000100
100000010
100000001
?
110000000
100000000
000000000
000000000
000000000
100000000
100000000
000000000
100000000
?
101010101
000000000
101010101
101010101
101010101
000001000
000000000
101010101
000000000
?
100010001
010000000
10...

result:

ok correct! (10000 test cases)

Extra Test:

score: 0
Extra Test Passed