# Untitled

unknown
plain_text
6 months ago
26 kB
14
Indexable
Never
```Gold Mining
Given a map of gold mine which can be represented as a NxN matrix

In this map, there are several gold mines that locates on random places (maximum 4 mines each map). A camp will be setup in the map for mining the gold. Every day, workers will go from the camp to gold mines location. In order to reduce the cost, company want to setup the camp so that the distance from it to mining location is optimized.

Let consider below 5x5 map :

- Worker can not go through the rock

- It takes 1 hour to travel a cell in map

There are two mines, from start point (camp location), it would take 4h to go to each gold mine. Let's suppose the final cost will be the highest cost among them, then if we put the camp as above figure, the final cost will be 4.

Now, we consider other example :

In the 3rd example, the final cost will be minimum (1)

[Input]

The first line of input will be the number of test case T (T ≤ 50)

In each TC :

- The first line will give the size of map N (N ≤ 20) and the number of gold mines G (2 ≤ G ≤ 4)

- The next G lines will give location R (row) & C (column) of gold mine (1-base indexed)

- The next N lines will give the map's data : 1 represents the road & gold mines, 0 represents the rock (can not go through)

[Output]

Your program should output the Minimum final cost for traveling from camp to gold mines.

Case #1

1

Case #2

2

Case #3

2

Case #4

7

Case #5

6

[Constraints]

- You can move on 4 directions (up/left/down/right)

- You can not setup the camp on gold mine location or rock

- You can go pass a gold mine then go to other gold mine

- You must place camp so that workers can go to all gold mines

*** code
#include<iostream>
using namespace std;
int ans;
int N, G;
int golds;
int goldXY[25][2];
int map[25][25];

int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int visit[25][25];

void resetmap(){
for (int i = 0; i < 25; i++){
for ( int j = 0; j < 25; j++){
map[i][j] = -1;
visit[i][j] = 0;
}
}
golds = 0;
}

void resetvisit(){
for (int i = 0; i < 25; i++){
for ( int j = 0; j < 25; j++){
visit[i][j] = 0;
}
}
}

// queue
int qx[100000];
int qy[100000];
int front = -1;
int rear = -1;
bool isEmpty(){
return front == -1;
}
void push(int x, int y){
if (front == -1) front = 0;
rear++;
qx[rear] = x;
qy[rear] = y;
}
void pop(){
if (front >= rear) front = rear = -1;
else front++;
}

int BFS(int x, int y){
front = rear = -1;
push(x,y);
visit[x][y] = 1;
int cnt = 0;
int len = 0;
int go[25][25] = {0};
while (!isEmpty()){
int x1 = qx[front];
int y1 = qy[front];
pop();
for (int i = 0; i < 4; i++){
int x2 = x1 + dx[i];
int y2 = y1 + dy[i];
if (map[x2][y2] > 0 && x2>=0 && x2<N && y2>=0 && y2<N && visit[x2][y2] == 0){
visit[x2][y2] = 1;
push(x2,y2);
go[x2][y2] = go[x1][y1] + 1;
if (map[x2][y2] == 2) {
++cnt;
}
if(cnt == golds) {
len = go[x2][y2];
return len;
}
}
}
}
return 10000;
}

void inmap(){
cout << "map" << endl;
for (int i = 0; i < N; i++){
for (int j = 0; j < N; j++){
cout << map[i][j] << " " ;
}
cout << endl;
}
}

int main(){
//	freopen("input.txt","r",stdin);
int TC; cin >> TC;
for (int tc = 1; tc <= TC; tc++){
resetmap();
cin >> N >> G;
int idxG = 0;
for (int i = 0; i < G; i++){
int R, C; cin >> R >> C;
goldXY[idxG][0] = R-1;
goldXY[idxG][1] = C-1;
idxG++;
golds++;
}
for (int i = 0; i < N; i++){
for (int j = 0; j < N; j++){
cin >> map[i][j];
}
}
for (int i = 0; i < golds; i++){
map[goldXY[i][0]][goldXY[i][1]] = 2;
}

//inmap();

ans = 1000;
for (int i = 0; i < N; i++){
for (int j = 0; j < N; j++){
resetvisit();
if (map[i][j] == 0 || map[i][j] == 2 || visit[i][j] == 1) continue;
int len = BFS(i,j);
if (ans > len) ans = len;
}
}

cout << "Case #" << tc << endl;
cout << ans << endl;
}
return 0;
}

*** testcase
50
5 2
4 3
3 4
1 1 0 0 0
1 1 0 0 0
1 1 1 1 1
1 1 1 0 1
1 1 1 1 1
8 2
5 6
6 4
1 1 1 1 1 1 0 0
1 1 1 1 1 1 1 0
1 1 0 1 0 1 1 0
1 1 1 1 0 1 1 0
1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
10 3
8 2
5 3
7 1
0 0 0 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 0
1 0 0 1 0 0 0 0 1 0
1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 1 0 0 1 1
1 1 1 1 0 1 0 0 1 1
1 1 1 1 0 1 0 0 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 0 0 1 0 0 1 1
1 1 1 1 1 1 1 1 1 1
8 3
1 2
2 8
5 8
0 1 0 0 0 0 0 0
0 1 0 1 1 1 1 1
0 1 0 1 0 0 0 1
0 1 1 1 0 0 0 1
0 1 0 1 0 0 0 1
0 1 0 1 1 1 1 1
0 1 0 0 1 0 0 0
0 1 0 0 1 0 0 0
10 4
9 6
1 9
7 5
7 3
1 1 1 1 1 1 0 1 1 0
1 1 1 0 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 0 1 1 1
1 1 1 1 1 0 1 1 1 1
1 0 1 1 0 1 1 1 1 1
1 0 1 1 1 1 1 0 1 1
1 0 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1
1 0 1 0 1 1 1 1 0 1
10 4
10 4
6 7
4 5
4 9
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 0 1 1 1 1
1 1 0 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 1
1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 0
0 0 1 1 1 0 1 0 1 1
10 3
10 5
6 9
7 8
1 0 0 1 1 0 0 0 0 1
1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1
0 0 1 0 0 1 1 0 1 1
1 1 1 1 1 1 1 1 0 1
1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 0 1
1 1 1 1 1 1 1 1 0 0
10 3
5 2
4 6
6 5
1 0 1 1 1 1 1 0 1 1
1 1 0 1 1 0 1 1 1 1
1 0 0 1 1 0 1 1 1 1
1 1 1 1 1 1 0 0 1 1
1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 0 1
0 0 1 1 0 1 1 1 1 1
0 1 0 0 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1
10 3
9 5
1 3
7 4
0 1 1 1 1 0 1 0 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 0 1 1 1 1
1 1 1 0 1 1 1 1 1 0
1 1 1 1 1 0 0 1 1 1
1 0 1 1 1 1 1 1 1 1
0 0 1 1 1 1 1 1 1 1
0 0 0 1 0 1 1 0 1 1
0 0 0 0 1 1 1 1 1 0
0 0 0 1 1 1 1 1 1 1
10 3
1 10
6 2
4 6
0 1 1 1 1 1 0 1 0 1
1 1 1 1 0 1 1 1 0 1
0 0 1 1 0 0 1 0 1 1
0 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1
1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1
1 1 1 0 1 1 1 1 1 1
1 1 0 1 1 1 1 1 0 0
10 2
4 4
4 5
0 1 1 1 1 1 1 1 1 1
0 1 0 1 1 0 1 1 1 1
1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0
1 1 1 1 0 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1
0 1 1 1 1 1 0 1 1 1
10 4
7 4
9 4
4 6
4 8
1 1 1 0 0 1 0 1 1 1
1 1 1 1 1 1 1 0 1 1
1 0 1 1 1 1 1 0 1 1
0 0 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0
0 1 1 1 0 1 0 1 1 1
1 1 1 0 1 1 1 0 0 1
1 1 1 1 0 1 1 1 1 1
1 1 1 0 1 1 1 1 1 0
10 4
1 3
6 6
2 5
8 5
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 0 1 1 0 1
0 0 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1
0 1 0 1 1 1 1 1 1 0
0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1
10 2
3 2
6 7
1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 0 1 1 1 0
0 1 0 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 0 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 0 0 1 1 1 1 1
1 1 0 0 0 0 1 1 1 1
10 4
7 5
1 7
2 4
9 10
1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1
0 1 1 0 1 1 1 1 1 0
1 0 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1
10 2
4 5
2 2
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 0 1 1 1 1
1 0 1 1 1 1 1 1 1 1
1 1 1 0 1 0 1 1 0 1
1 1 1 1 1 1 1 1 0 1
1 1 1 0 1 1 1 1 1 1
10 2
8 5
10 7
1 1 1 1 1 0 1 1 1 1
1 0 1 0 1 1 1 1 1 1
1 0 1 0 1 1 1 0 1 1
1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1
1 1 0 0 1 1 1 1 1 1
1 1 1 0 0 0 1 1 1 1
1 1 1 0 1 1 1 1 1 1
10 2
2 4
10 5
0 0 1 1 1 1 1 1 1 1
1 1 0 1 0 1 1 1 1 1
1 1 1 1 1 1 0 0 1 0
1 1 1 0 1 1 0 1 1 1
1 1 1 1 1 1 1 0 1 0
1 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 0 1
1 1 0 1 1 1 1 1 1 1
0 1 1 1 1 1 1 0 1 1
1 1 0 1 1 1 1 1 1 1
10 2
7 8
3 8
1 1 1 1 1 1 0 1 1 1
1 0 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1
1 1 0 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 0 0 1 1 1
0 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 0 0 1 1 1
10 4
9 9
9 2
10 7
1 2
1 1 1 1 0 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0
12 3
4 3
6 6
6 11
0 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0 1 0
0 1 0 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 0 1 1 1
1 1 0 1 0 1 1 0 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 0 0 1 1 1 1 1
1 1 1 1 1 1 1 1 0 1 1 0
0 1 1 1 0 1 1 1 1 1 0 1
1 1 1 0 1 0 1 1 1 1 1 1
1 1 0 0 1 1 1 1 1 1 1 1
12 3
10 2
4 9
4 10
1 0 1 0 1 1 0 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1 0 1
1 0 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1 1 1 1 0
1 1 1 0 1 1 0 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 0 1 1 1 0 1
1 1 1 1 1 0 1 1 1 1 1 1
1 0 1 1 1 1 1 0 1 1 1 1
0 1 1 1 0 1 1 1 1 1 1 0
12 4
12 12
2 8
8 5
7 4
1 1 1 1 1 1 0 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1
1 1 0 0 0 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1 0 1
1 1 1 0 1 1 1 1 1 1 1 0
1 1 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 1 1 0
0 1 1 1 1 1 1 1 1 0 1 1
1 1 0 1 1 1 0 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1 1 0
1 1 1 1 0 0 1 1 1 0 1 1
1 1 1 0 1 1 1 1 1 0 1 1
12 4
11 3
10 5
6 12
12 7
1 0 0 1 1 1 0 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1
0 0 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
0 1 1 0 1 0 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
12 4
11 2
2 10
5 11
5 12
1 1 1 1 1 1 0 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 0 1 1 1 1 1 1 1 1
1 1 0 1 1 1 0 1 1 1 1 1
1 1 1 1 0 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1
12 2
9 8
7 9
1 1 1 1 1 1 1 1 1 0 0 0
1 0 1 1 1 1 0 0 1 1 0 0
1 1 1 1 1 0 0 1 1 0 0 1
1 1 1 1 1 0 1 0 1 0 1 1
1 0 1 1 1 1 1 1 1 1 1 0
1 1 1 0 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 0
1 0 1 1 1 1 0 1 1 1 1 1
1 0 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 0 1 1 1 1 1 1 0
12 2
7 9
10 8
1 0 1 1 1 1 0 1 1 1 1 1
1 1 1 1 0 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 0 0 1 1 1 1 1 1 0 1 1
1 0 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 0 1 1 0 1 1 1 1 1
1 1 1 1 1 1 1 1 0 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1
12 2
6 5
1 2
1 1 1 0 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 0
1 0 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1
0 1 1 1 1 1 1 1 0 1 1 0
1 1 1 0 1 1 0 1 1 1 1 1
1 0 1 1 0 1 1 1 0 1 0 1
0 1 1 1 1 1 0 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 0 1
1 0 1 1 1 1 1 0 1 1 1 1
1 0 1 1 1 1 1 1 1 1 0 1
12 4
7 6
7 12
5 5
5 4
0 0 0 0 0 0 1 1 1 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 1 1 1 0 0 0 0
0 0 0 0 1 1 1 0 1 0 1 1
0 0 0 1 1 1 1 1 1 1 0 1
0 1 0 1 0 1 1 1 1 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 0 1 1 0 0
1 1 1 1 1 1 1 0 1 1 1 0
1 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1
12 4
12 4
6 7
3 8
11 9
1 1 1 0 1 1 1 1 1 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 0 1 1 0 1 1
1 1 0 1 1 0 1 1 1 1 1 1
1 1 0 1 0 1 1 0 0 1 1 1
1 1 1 1 1 0 1 1 1 1 1 1
0 0 0 1 1 1 1 1 1 1 0 1
1 1 1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1 1 0
1 1 1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 0 1 1 1 0
15 3
8 6
8 5
12 7
1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
0 1 1 1 1 1 1 0 1 1 1 1 1 1 1
1 1 1 1 0 1 0 0 0 1 1 1 1 1 1
1 1 0 1 1 1 1 0 0 0 1 1 1 0 1
1 1 1 1 1 0 1 1 0 1 1 1 1 1 1
1 1 0 1 0 1 1 0 1 1 1 1 1 1 1
0 1 1 1 1 0 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1 1 1 1 1 0
1 1 1 1 1 0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 1 1 0
1 0 1 1 1 1 1 1 1 0 1 1 1 1 1
0 1 0 1 1 1 1 0 1 1 1 0 1 1 1
1 1 1 0 1 0 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
15 3
7 2
12 7
4 8
1 1 1 1 0 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1 1 0 1 1 1
1 1 0 1 1 0 1 1 1 1 0 0 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
1 1 0 1 0 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1 0 1 0 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 1 0 1
0 1 1 1 1 1 1 0 1 1 1 0 1 1 1
1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 1 1 0 1 1 1
1 1 1 1 1 0 1 1 1 1 1 1 1 1 1
15 2
6 4
7 3
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1 1 1 1 1 1
1 1 1 1 0 0 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 0 0 0 1
1 1 1 1 1 0 1 1 0 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 0 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 0 1 1 1 1 0
1 1 1 1 1 1 1 0 0 1 1 1 1 1 1
1 1 1 1 0 1 1 0 1 1 0 0 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
15 2
4 2
3 2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1 0 1 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 0 1 0 1 0 1 1 1
1 1 1 1 1 1 1 1 0 0 1 1 1 1 1
0 1 1 1 1 0 1 1 1 1 1 0 1 1 1
1 1 1 1 1 0 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 0 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 0 1 1 1 0 1 1
0 1 1 1 1 0 0 1 0 1 1 1 1 1 1
15 4
1 8
10 6
9 7
9 8
1 1 1 0 1 1 1 1 1 1 1 1 0 0 0
1 1 1 1 1 1 1 1 1 0 1 1 0 1 0
1 1 1 1 1 0 0 1 1 1 0 0 1 1 1
1 1 1 1 1 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1 1 0 1 1 1
1 0 1 1 1 0 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1 1 1 0
1 1 1 1 0 0 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1 0 1 1
1 0 1 1 1 0 1 1 1 1 1 1 1 1 1
1 1 0 1 1 0 1 0 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 0 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 0 1 1 1 1 1 1 1 1 1 1
15 3
2 12
12 14
12 5
0 1 1 1 1 1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 0 1 1 1 1 0 1 1 0 1
1 1 1 1 1 0 1 1 1 1 1 1 1 1 1
0 1 1 0 0 1 1 0 1 0 0 1 1 1 1
1 0 1 1 1 1 1 1 0 1 1 1 1 1 1
1 1 1 1 0 1 1 1 1 1 1 1 1 1 1
1 0 0 1 1 1 1 1 1 1 1 1 1 0 1
1 0 0 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 0 1 1 0 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
15 3
9 6
11 4
1 3
1 0 1 1 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 0 1 0 1 0 1 0
1 1 1 0 1 0 1 1 0 1 1 0 1 1 0
1 0 1 0 0 1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 0 1 1 1 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1 1 0 1 0 0 1 0
0 1 1 1 1 1 0 1 1 1 1 1 1 1 1
1 1 1 0 1 0 1 1 1 0 1 1 1 1 1
0 1 1 0 1 1 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 1 1 0 0
15 3
15 7
1 4
2 7
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 0 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1 0 0 1
1 1 1 1 1 0 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 0 1 1 1 1 1 1 1
0 1 1 0 1 1 1 1 1 0 0 1 0 1 1
1 1 1 1 1 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 0 1 0 1 1 1 1 0
1 1 1 1 1 1 1 1 0 0 1 1 1 1 0
1 0 1 1 1 1 1 0 0 0 0 1 1 1 0
15 4
8 8
1 5
1 12
6 12
1 1 0 1 1 1 1 1 1 1 1 1 1 1 0
1 0 1 0 1 1 1 1 1 1 1 1 1 0 0
1 1 1 0 1 1 1 1 1 1 1 1 0 1 1
1 1 1 0 0 0 0 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1 0 1 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 1 1 1 1 1 1
1 1 1 1 0 1 1 1 0 1 1 1 1 1 0
0 1 1 1 1 1 1 1 1 1 1 0 1 1 1
1 1 0 1 0 1 1 1 1 1 1 1 0 1 0
0 1 1 1 1 0 1 0 1 1 1 1 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
15 3
3 11
15 12
1 7
0 1 1 1 1 1 1 1 1 0 1 1 0 1 1
1 1 1 1 1 1 1 1 0 1 1 1 1 1 0
1 1 1 1 1 1 1 1 0 1 1 1 1 1 0
1 0 0 1 0 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 0 0 1 1 0 1 1
1 1 0 1 1 1 1 1 1 1 0 0 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 0 1 1 1 1 1 0 1 1 1 0
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1 1 0 1
1 0 1 1 1 1 1 1 0 0 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 0 1 0
20 2
6 12
12 11
1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1
1 1 0 1 0 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 0 1 1 0 1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 0 1
1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1 1 0 1 1
1 1 0 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 0 1
1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 0 0 1 1 0 1 1 1 1 1 0 0 1 1 1
1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 0 0
1 0 1 0 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1
0 1 1 1 0 1 1 1 1 1 1 0 1 1 0 1 1 1 0 1
1 1 1 1 0 0 1 1 0 0 1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 0 1 1
20 4
8 20
17 17
2 18
2 13
1 0 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 0 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0
1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 0
1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 0 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 0 1 0 1
1 0 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 0 1 1
20 2
18 6
5 17
1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 0 0 1
1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 0
1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 0 1 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 0 1 1 1 1
1 1 1 1 1 1 1 0 1 1 1 1 1 0 0 1 1 1 1 0
0 0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 0 1
1 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 0 0 0 0 1
0 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 1 0 0 1 1 1 0 1 1 1 1 0
20 3
8 11
11 14
13 16
0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1
0 1 1 0 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0
0 1 1 0 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 1
1 0 0 1 1 0 1 1 1 1 1 1 1 0 0 1 0 1 1 1
1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1
0 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 0 1 1 1 1 0 1 0 1 1 1 1 1 1 1 0 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
0 1 1 1 1 0 0 1 1 1 1 1 1 1 1 0 0 1 0 0
1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0
20 2
7 10
13 19
1 1 1 1 0 1 1 1 0 0 1 1 1 1 1 1 0 1 0 1
1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
1 1 0 1 0 1 1 1 1 1 1 1 0 0 1 1 1 0 1 1
0 1 1 1 1 1 1 1 0 0 1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1
1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1
1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 0 0 1 1
0 0 1 1 1 1 1 1 1 1 1 0 1 0 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 0 1 1
1 0 1 0 1 0 1 1 0 1 1 1 1 1 0 1 0 1 1 1
1 0 0 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1
1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1
20 3
6 2
10 7
14 2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 0
1 1 0 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1
0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1
0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1
1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1
1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 1
1 1 1 1 1 1 0 0 1 1 0 1 1 1 1 1 0 1 1 1
1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 0 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1
1 1 1 0 1 1 1 1 1 1 0 0 1 0 1 1 0 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
1 1 1 0 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1
1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1
20 3
9 8
8 12
7 12
1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 0
1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1
0 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 1 1
0 1 1 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1
1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1
1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1
1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0
1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 0 0 1 0 1 0 1 1 1 1 1 1 1
0 1 0 1 1 1 0 1 1 1 0 1 0 1 1 1 1 1 1 1
20 3
7 12
9 8
14 5
1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1
1 1 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 1
1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 0 1 1 1 1
1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 0 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1
1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0
1 1 1 0 1 0 1 1 1 1 0 1 1 1 1 1 1 1 0 1
1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 1
1 1 1 1 1 0 1 1 0 0 1 1 1 1 0 1 1 1 1 1
1 1 1 0 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 1 1 1 0
1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
0 1 0 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1
20 3
17 4
19 15
17 18
1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 0
1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0
1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0
1 1 1 1 1 1 0 1 1 1 1 0 1 0 1 0 1 1 1 1
1 1 1 1 0 1 1 0 1 0 1 1 1 1 1 1 0 1 1 1
1 1 1 0 1 1 1 0 0 1 0 1 0 1 1 1 0 1 1 1
1 1 0 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1
1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1
1 1 1 1 0 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 0 0 1 1 0 1 0 1
0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1
1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1
1 0 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 0 1
1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 0 1 0 1 1 0 0 1 1 0 0 0 1 1 1
20 3
4 20
5 19
20 16
1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 0 1 1
1 1 0 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 0
1 1 1 0 0 1 1 1 1 0 1 0 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 0 1 1 1 1 1 0 1 0 0 1 1 1 1
1 0 1 1 0 1 1 1 1 1 1 0 1 1 1 0 0 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1
0 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1
0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 1 1 1
1 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 1 0 0```