QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#202916#2477. ExcavationDelay_for_five_minutes#AC ✓7ms4512kbC++112.3kb2023-10-06 14:05:442023-10-06 14:05:44

Judging History

This is the latest submission verdict.

  • [2023-10-06 14:05:44]
  • Judged
  • Verdict: AC
  • Time: 7ms
  • Memory: 4512kb
  • [2023-10-06 14:05:44]
  • Submitted

answer

#include<bits/stdc++.h>
#define maxn 105
int n;
std::string c;
std::string str[maxn];
int id[maxn][maxn];
std::pair<int,int> pos[maxn * maxn];
int cnt;
bool vis[maxn * maxn];
std::vector<int> G[maxn * maxn];
std::pair<int,int> N[8] = {{-2,1},{-2,-1},{-1,-2},{-1,2},{1,2},{1,-2},{2,-1},{2,1}};
std::pair<int,int> K[8] = {{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1}};
void dfs(int u) {
	for(auto i:G[u]) {
		dfs(i);
		printf("%d %d %d %d\n",pos[i].first + 1,pos[i].second + 1,pos[u].first + 1,pos[u].second + 1);
	}

}
int main() {
	std::cin >> n >> c;
	for(int i = 0; i < n; i++) {
		std::cin >> str[i];
		for(int j = 0; j < n; j++) {
			if (str[i][j] != '.') {
				id[i][j] = ++cnt;
				pos[cnt] = {i,j};
			}
		}
	}
	std::queue<int> que;
	vis[0] = 1;
	std::pair<int,int> *dir = (c[0] == 'N' ? N : K); 
	que.push(1);
	vis[1] = 1;
	int C = 0;
	while(!que.empty()) {
		C++;
		int nowid = que.front();
		que.pop();
		std::pair<int,int> now = pos[nowid];
		// printf("%d %d\n",now.first,now.second);
		if (c[0] == 'R' || c[0] == 'Q') {
			for(int i = 0; i < n; i++) {
				if (!vis[id[now.first][i]]) {
					que.push(id[now.first][i]);
					vis[id[now.first][i]] = 1;
					G[nowid].push_back(id[now.first][i]);
				}
				if (!vis[id[i][now.second]]) {
					que.push(id[i][now.second]);
					vis[id[i][now.second]] = 1;
					G[nowid].push_back(id[i][now.second]);
				}
			}
		}
		if (c[0] == 'Q' || c[0] == 'B') {
			for(int i = -100; i <= 100; i++) {
				int x = now.first + i, y = now.second + i;
				if (x >= 0 && x < n && y >= 0 && y < n) {
					if (!vis[id[x][y]]) {
						que.push(id[x][y]);
						vis[id[x][y]] = 1;
						G[nowid].push_back(id[x][y]);
					}
				}
				x = now.first - i, y = now.second + i;
				if (x >= 0 && x < n && y >= 0 && y < n) {
					if (!vis[id[x][y]]) {
						que.push(id[x][y]);
						vis[id[x][y]] = 1;
						G[nowid].push_back(id[x][y]);
					}
				}
			}
		}
		if (c[0] == 'K' || c[0] == 'N') {
			for(int i = 0; i < 8; i++) {
				int x = now.first + dir[i].first, y = now.second + dir[i].second;
				if (x >= 0 && x < n && y >= 0 && y < n) {
					if (!vis[id[x][y]]) {
						que.push(id[x][y]);
						vis[id[x][y]] = 1;
						G[nowid].push_back(id[x][y]);
					}
				}
			}
		}
	}
	if (C < cnt) {
		printf("NO\n");
		return 0;
	}
	printf("YES\n");
	dfs(1);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3904kb

input:

5 K
.....
.....
.K...
...K.
.....

output:

NO

result:

ok 

Test #2:

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

input:

5 K
.....
.K...
.....
...K.
.....

output:

NO

result:

ok 

Test #3:

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

input:

5 K
.....
.....
.....
..K.K
.....

output:

NO

result:

ok 

Test #4:

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

input:

5 K
.....
.K...
.....
.K...
.....

output:

NO

result:

ok 

Test #5:

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

input:

5 K
.....
..K..
.K.K.
..K..
.....

output:

YES
4 3 3 4
3 4 2 3
3 2 2 3

result:

ok 

Test #6:

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

input:

5 K
..K.K
..K..
.K...
.K...
..KK.

output:

NO

result:

ok 

Test #7:

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

input:

5 Q
.Q...
.....
..Q..
.....
.....

output:

NO

result:

ok 

Test #8:

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

input:

5 Q
.....
....Q
.....
.....
..Q..

output:

NO

result:

ok 

Test #9:

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

input:

5 Q
Q....
.....
....Q
..Q..
.....

output:

NO

result:

ok 

Test #10:

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

input:

5 Q
Q....
....Q
.....
.....
.....

output:

NO

result:

ok 

Test #11:

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

input:

5 Q
....Q
.....
.....
.....
...Q.

output:

NO

result:

ok 

Test #12:

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

input:

5 R
.....
.....
...R.
R....
.....

output:

NO

result:

ok 

Test #13:

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

input:

5 R
.....
.R...
..R..
.....
.....

output:

NO

result:

ok 

Test #14:

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

input:

5 R
.....
....R
...R.
..R.R
...R.

output:

NO

result:

ok 

Test #15:

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

input:

5 R
R.R.R
.....
.....
.....
.R.R.

output:

NO

result:

ok 

Test #16:

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

input:

5 R
...R.
.....
.R.R.
.....
R....

output:

NO

result:

ok 

Test #17:

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

input:

5 B
.....
.....
.....
.B...
.B...

output:

NO

result:

ok 

Test #18:

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

input:

5 B
.....
..BB.
.....
.....
.....

output:

NO

result:

ok 

Test #19:

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

input:

5 B
.....
B...B
.....
....B
.....

output:

NO

result:

ok 

Test #20:

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

input:

5 B
B.B.B
.B.B.
B.B.B
.B.B.
...B.

output:

NO

result:

ok 

Test #21:

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

input:

5 B
B....
.B...
..B..
.BBB.
..B..

output:

NO

result:

ok 

Test #22:

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

input:

5 N
....N
...N.
..N..
.N...
N....

output:

NO

result:

ok 

Test #23:

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

input:

5 N
.....
.N...
.N...
.....
.....

output:

NO

result:

ok 

Test #24:

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

input:

5 N
.....
...NN
.....
.....
.....

output:

NO

result:

ok 

Test #25:

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

input:

5 N
.....
.....
.N.N.
..N..
.N...

output:

NO

result:

ok 

Test #26:

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

input:

5 N
N....
...N.
.N.N.
.....
.....

output:

NO

result:

ok 

Test #27:

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

input:

10 Q
QQQ.QQQQQQ
QQQ.QQQQQQ
QQQ.QQQQQQ
....QQQQQ.
..........
..........
..........
..........
..........
...Q......

output:

NO

result:

ok 

Test #28:

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

input:

10 B
B.B.B...B.
.B.B...B.B
..B...B.B.
.....B.B.B
....B.B.B.
.....B.B.B
B.....B.B.
.......B..
..........
..........

output:

NO

result:

ok 

Test #29:

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

input:

10 R
RRR.RRRRRR
RRR.RRRRRR
RRR.RRRRRR
....RRRRRR
....RRRRRR
....RRRRRR
..........
..........
..........
...R......

output:

NO

result:

ok 

Test #30:

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

input:

10 N
N.N...N...
....N.....
.N...N....
..........
......N...
.....N....
.......N..
..........
.N........
..........

output:

NO

result:

ok 

Test #31:

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

input:

10 K
KK...KKKKK
.K.KKKKKKK
..K..KKKKK
.....KKKKK
.....KKKKK
....K.....
...KK.....
..K..K....
.....K.K..
..........

output:

NO

result:

ok 

Test #32:

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

input:

10 Q
QQQ.QQQQQQ
QQQ.QQQQQQ
QQQ.QQQQQQ
....QQQQQ.
..........
..........
..........
..........
..........
..........

output:

YES
3 2 1 2
2 3 1 2
4 5 1 2
1 2 1 1
2 5 2 1
2 6 2 1
2 7 2 1
2 8 2 1
2 9 2 1
2 10 2 1
2 1 1 1
3 5 1 3
4 6 1 3
1 3 1 1
3 6 3 1
3 7 3 1
3 8 3 1
3 9 3 1
3 10 3 1
3 1 1 1
4 8 1 5
1 5 1 1
4 9 1 6
1 6 1 1
4 7 1 7
1 7 1 1
1 8 1 1
1 9 1 1
1 10 1 1
2 2 1 1
3 3 1 1

result:

ok 

Test #33:

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

input:

10 B
B.B.B...B.
.B.B...B.B
..B...B.B.
.....B.B.B
....B.B.B.
.....B.B.B
......B.B.
.......B..
..........
..........

output:

YES
1 3 2 2
2 2 1 1
2 4 3 3
1 5 3 3
3 3 1 1
4 6 5 5
3 7 5 5
2 8 5 5
1 9 5 5
5 5 1 1
5 7 6 6
4 8 6 6
3 9 6 6
2 10 6 6
6 6 1 1
6 8 7 7
5 9 7 7
4 10 7 7
7 7 1 1
7 9 8 8
6 10 8 8
8 8 1 1

result:

ok 

Test #34:

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

input:

10 R
RRR.RRRRRR
RRR.RRRRRR
RRR.RRRRRR
....RRRRRR
....RRRRRR
....RRRRRR
..........
..........
..........
..........

output:

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

result:

ok 

Test #35:

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

input:

10 N
N.N...N...
....N.....
.N...N....
..........
......N...
.....N....
.......N..
..........
..........
..........

output:

YES
6 6 7 8
7 8 5 7
5 7 3 6
3 6 1 7
1 7 2 5
2 5 1 3
1 3 3 2
3 2 1 1

result:

ok 

Test #36:

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

input:

10 K
KK...KKKKK
.K.KKKKKKK
..K..KKKKK
.....KKKKK
.....KKKKK
....K.....
...KK.....
..K..K....
.....K....
..........

output:

YES
1 2 1 1
1 10 1 9
2 10 1 9
1 9 1 8
3 10 2 9
2 9 1 8
1 8 1 7
4 10 3 9
3 9 2 8
2 8 1 7
1 7 1 6
5 10 4 9
4 9 3 8
3 8 2 7
2 7 1 6
1 6 2 5
5 9 4 8
4 8 3 7
3 7 2 6
2 6 2 5
5 8 4 7
5 7 4 7
9 6 8 6
8 6 7 5
7 5 6 5
8 3 7 4
7 4 6 5
6 5 5 6
5 6 4 7
4 7 3 6
4 6 3 6
3 6 2 5
2 5 2 4
2 4 3 3
3 3 2 2
2 2 1 1

result:

ok 

Test #37:

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

input:

2 K
K.
KK

output:

YES
2 2 1 1
2 1 1 1

result:

ok 

Test #38:

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

input:

1 B
B

output:

YES

result:

ok 

Test #39:

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

input:

2 B
BB
BB

output:

NO

result:

ok 

Test #40:

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

input:

3 B
BBB
BBB
BBB

output:

NO

result:

ok 

Test #41:

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

input:

5 B
BBBBB
BBBBB
BBBBB
BBBBB
BBBBB

output:

NO

result:

ok 

Test #42:

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

input:

17 B
BBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBB
BBBBBBB...

output:

NO

result:

ok 

Test #43:

score: 0
Accepted
time: 2ms
memory: 4236kb

input:

100 B
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...

output:

NO

result:

ok 

Test #44:

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

input:

100 B
....................................................................................................
....................................................................................................
...............................................................................................

output:

YES

result:

ok 

Test #45:

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

input:

100 B
....................................................................................................
....................................................................................................
...............................................................................................

output:

NO

result:

ok 

Test #46:

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

input:

100 B
.....B.....................B.....B......B......B...........................BB.B.......B....B.....B..
..........B..............B......BB...............B....................................B.....BB......
................B...............B........B..............B......B...B.B......B.........B.B......

output:

NO

result:

ok 

Test #47:

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

input:

100 B
......B...B.......B....B.......B.BB...B....B.....B...........BB.............B.BB....B.......B....BBB
.........B.B......B......B..........B....BB.................B....B........B.................B......B
B..B.BB.....B..B..........BB..BBB....B.B.B..B.B.BB...B...B......B....B...B.B..BB..BBBB.........

output:

NO

result:

ok 

Test #48:

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

input:

100 B
.B..B..B.B..B.........B..........B...B.BB.......B.B...BB...B...B.........B..B.BB..BB.B..B.B.....B..B
BB..BB.....B..B........B........B.BB.B....B.BBB......B...B..BB..B.B..........BB.B.....BBBB...B...B..
.....B.B.B...B....B.............B..BB.BB......BB.B...BBB.BB..B...B..........B..B.....BB........

output:

NO

result:

ok 

Test #49:

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

input:

3 B
BBB
B.B
BBB

output:

NO

result:

ok 

Test #50:

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

input:

19 B
BBBBBBBBBBBBBBBBBBB
B.................B
B.................B
B.................B
B.................B
B.................B
B.................B
B.................B
B.................B
B.................B
B.................B
B.................B
B.................B
B.................B
B.................

output:

NO

result:

ok 

Test #51:

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

input:

100 B
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
B..................................................................................................B
B..............................................................................................

output:

NO

result:

ok 

Test #52:

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

input:

3 B
B.B
.B.
B.B

output:

YES
3 1 2 2
1 3 2 2
2 2 1 1
3 3 1 1

result:

ok 

Test #53:

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

input:

21 B
B...................B
.B.................B.
..B...............B..
...B.............B...
....B...........B....
.....B.........B.....
......B.......B......
.......B.....B.......
........B...B........
.........B.B.........
..........B..........
.........B.B.........
........B...B........
.......B....

output:

YES
2 2 1 1
3 3 1 1
4 4 1 1
5 5 1 1
6 6 1 1
7 7 1 1
8 8 1 1
9 9 1 1
10 10 1 1
21 1 11 11
20 2 11 11
19 3 11 11
18 4 11 11
17 5 11 11
16 6 11 11
15 7 11 11
14 8 11 11
13 9 11 11
12 10 11 11
10 12 11 11
9 13 11 11
8 14 11 11
7 15 11 11
6 16 11 11
5 17 11 11
4 18 11 11
3 19 11 11
2 20 11 11
1 21 11 11
...

result:

ok 

Test #54:

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

input:

99 B
B.................................................................................................B
.B...............................................................................................B.
..B...............................................................................................

output:

YES
2 2 1 1
3 3 1 1
4 4 1 1
5 5 1 1
6 6 1 1
7 7 1 1
8 8 1 1
9 9 1 1
10 10 1 1
11 11 1 1
12 12 1 1
13 13 1 1
14 14 1 1
15 15 1 1
16 16 1 1
17 17 1 1
18 18 1 1
19 19 1 1
20 20 1 1
21 21 1 1
22 22 1 1
23 23 1 1
24 24 1 1
25 25 1 1
26 26 1 1
27 27 1 1
28 28 1 1
29 29 1 1
30 30 1 1
31 31 1 1
32 32 1 1
33...

result:

ok 

Test #55:

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

input:

29 B
B.BBB.BBB.BBB.BBB.BBB.BBB.BBB
B.B.B.B.B.B.B.B.B.B.B.B.B.B.B
B.B.B.B.B.B.B.B.B.B.B.B.B.B.B
B.B.B.B.B.B.B.B.B.B.B.B.B.B.B
B.B.B.B.B.B.B.B.B.B.B.B.B.B.B
B.B.B.B.B.B.B.B.B.B.B.B.B.B.B
B.B.B.B.B.B.B.B.B.B.B.B.B.B.B
B.B.B.B.B.B.B.B.B.B.B.B.B.B.B
B.B.B.B.B.B.B.B.B.B.B.B.B.B.B
B.B.B.B.B.B.B.B.B.B.B.B.B...

output:

NO

result:

ok 

Test #56:

score: 0
Accepted
time: 2ms
memory: 4292kb

input:

100 B
B.BBB.BBB.BBB.BBB.BBB.BBB.BBB.BBB.BBB.BBB.BBB.BBB.BBB.BBB.BBB.BBB.BBB.BBB.BBB.BBB.BBB.BBB.BBB.BBB.BB
B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.
B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B....

output:

NO

result:

ok 

Test #57:

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

input:

31 B
B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B
.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.
B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B
.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.
B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B
.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.
B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B
.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.
B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B
.B.B.B....

output:

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

result:

ok 

Test #58:

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

input:

100 B
B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.
.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B
B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B....

output:

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

result:

ok 

Test #59:

score: 0
Accepted
time: 3ms
memory: 4164kb

input:

100 B
.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B
B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.
.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B...

output:

YES
3 2 2 1
4 3 2 1
5 4 2 1
6 5 2 1
7 6 2 1
8 7 2 1
9 8 2 1
10 9 2 1
11 10 2 1
12 11 2 1
13 12 2 1
14 13 2 1
15 14 2 1
16 15 2 1
17 16 2 1
18 17 2 1
19 18 2 1
20 19 2 1
21 20 2 1
22 21 2 1
23 22 2 1
24 23 2 1
25 24 2 1
26 25 2 1
27 26 2 1
28 27 2 1
29 28 2 1
30 29 2 1
31 30 2 1
32 31 2 1
33 32 2 1
3...

result:

ok 

Test #60:

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

input:

1 K
K

output:

YES

result:

ok 

Test #61:

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

input:

2 K
KK
KK

output:

YES
1 2 1 1
2 2 1 1
2 1 1 1

result:

ok 

Test #62:

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

input:

3 K
KKK
KKK
KKK

output:

YES
1 3 1 2
2 3 1 2
1 2 1 1
3 3 2 2
3 2 2 2
3 1 2 2
2 2 1 1
2 1 1 1

result:

ok 

Test #63:

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

input:

5 K
KKKKK
KKKKK
KKKKK
KKKKK
KKKKK

output:

YES
1 5 1 4
2 5 1 4
1 4 1 3
3 5 2 4
2 4 1 3
1 3 1 2
4 5 3 4
3 4 2 3
2 3 1 2
1 2 1 1
5 5 4 4
5 4 4 4
5 3 4 4
4 4 3 3
5 2 4 3
4 3 3 3
5 1 4 2
4 2 3 3
3 3 2 2
4 1 3 2
3 2 2 2
3 1 2 2
2 2 1 1
2 1 1 1

result:

ok 

Test #64:

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

input:

17 K
KKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKK
KKKKKKK...

output:

YES
1 17 1 16
2 17 1 16
1 16 1 15
3 17 2 16
2 16 1 15
1 15 1 14
4 17 3 16
3 16 2 15
2 15 1 14
1 14 1 13
5 17 4 16
4 16 3 15
3 15 2 14
2 14 1 13
1 13 1 12
6 17 5 16
5 16 4 15
4 15 3 14
3 14 2 13
2 13 1 12
1 12 1 11
7 17 6 16
6 16 5 15
5 15 4 14
4 14 3 13
3 13 2 12
2 12 1 11
1 11 1 10
8 17 7 16
7 16 6...

result:

ok 

Test #65:

score: 0
Accepted
time: 2ms
memory: 4392kb

input:

100 K
KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK...

output:

YES
1 100 1 99
2 100 1 99
1 99 1 98
3 100 2 99
2 99 1 98
1 98 1 97
4 100 3 99
3 99 2 98
2 98 1 97
1 97 1 96
5 100 4 99
4 99 3 98
3 98 2 97
2 97 1 96
1 96 1 95
6 100 5 99
5 99 4 98
4 98 3 97
3 97 2 96
2 96 1 95
1 95 1 94
7 100 6 99
6 99 5 98
5 98 4 97
4 97 3 96
3 96 2 95
2 95 1 94
1 94 1 93
8 100 7 9...

result:

ok 

Test #66:

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

input:

100 K
....................................................................................................
....................................................................................................
...............................................................................................

output:

YES

result:

ok 

Test #67:

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

input:

100 K
....................................................................................................
....................................................................................................
...............................................................................................

output:

NO

result:

ok 

Test #68:

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

input:

100 K
....K....K.......K.........K...............K....................K...K...............................
..K...........................................................K..K.K.....K......KK....K.......K..K..
......K....K.......K.K................K.K.K......K.......K.......K...............K.............

output:

NO

result:

ok 

Test #69:

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

input:

100 K
...KK.............K..KK..K.....K...K..K.K..K....K.....K.K...........K.K.......K..K.....K.K.K.K...K.K
.........K........K..K.........K...K....KK...........K..K..............K....K.......K..........KK..K
K...........K...KK...K....K............K..K.........K..........K......K..KK...K.....KK..K......

output:

NO

result:

ok 

Test #70:

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

input:

100 K
K....K...KKK..KKK..K............K......K.K...K...K......KK...K...K...K..K..K......KKK....K........K.
KK......K.K......KK....K...KKKK..K.K.K.K....K..K...KK.K...........K..K.....K........K....KK.K...KK..
K..K..........KK....K...KK.K.K..........KK...KKK.KKKK.KK..K....KK.K...K.K.KK..KK.KK.......KK...

output:

NO

result:

ok 

Test #71:

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

input:

3 K
KKK
K.K
KKK

output:

YES
1 3 1 2
3 3 2 3
2 3 1 2
1 2 1 1
3 2 2 1
3 1 2 1
2 1 1 1

result:

ok 

Test #72:

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

input:

19 K
KKKKKKKKKKKKKKKKKKK
K.................K
K.................K
K.................K
K.................K
K.................K
K.................K
K.................K
K.................K
K.................K
K.................K
K.................K
K.................K
K.................K
K.................

output:

YES
1 19 1 18
19 19 18 19
18 19 17 19
17 19 16 19
16 19 15 19
15 19 14 19
14 19 13 19
13 19 12 19
12 19 11 19
11 19 10 19
10 19 9 19
9 19 8 19
8 19 7 19
7 19 6 19
6 19 5 19
5 19 4 19
4 19 3 19
3 19 2 19
2 19 1 18
1 18 1 17
1 17 1 16
1 16 1 15
1 15 1 14
1 14 1 13
1 13 1 12
1 12 1 11
1 11 1 10
1 10 1 ...

result:

ok 

Test #73:

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

input:

100 K
KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK
K..................................................................................................K
K..............................................................................................

output:

YES
1 100 1 99
100 100 99 100
99 100 98 100
98 100 97 100
97 100 96 100
96 100 95 100
95 100 94 100
94 100 93 100
93 100 92 100
92 100 91 100
91 100 90 100
90 100 89 100
89 100 88 100
88 100 87 100
87 100 86 100
86 100 85 100
85 100 84 100
84 100 83 100
83 100 82 100
82 100 81 100
81 100 80 100
80 1...

result:

ok 

Test #74:

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

input:

3 K
K.K
.K.
K.K

output:

YES
1 3 2 2
3 3 2 2
3 1 2 2
2 2 1 1

result:

ok 

Test #75:

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

input:

21 K
K...................K
.K.................K.
..K...............K..
...K.............K...
....K...........K....
.....K.........K.....
......K.......K......
.......K.....K.......
........K...K........
.........K.K.........
..........K..........
.........K.K.........
........K...K........
.......K....

output:

YES
1 21 2 20
2 20 3 19
3 19 4 18
4 18 5 17
5 17 6 16
6 16 7 15
7 15 8 14
8 14 9 13
9 13 10 12
10 12 11 11
21 21 20 20
20 20 19 19
19 19 18 18
18 18 17 17
17 17 16 16
16 16 15 15
15 15 14 14
14 14 13 13
13 13 12 12
12 12 11 11
21 1 20 2
20 2 19 3
19 3 18 4
18 4 17 5
17 5 16 6
16 6 15 7
15 7 14 8
14 ...

result:

ok 

Test #76:

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

input:

99 K
K.................................................................................................K
.K...............................................................................................K.
..K...............................................................................................

output:

YES
1 99 2 98
2 98 3 97
3 97 4 96
4 96 5 95
5 95 6 94
6 94 7 93
7 93 8 92
8 92 9 91
9 91 10 90
10 90 11 89
11 89 12 88
12 88 13 87
13 87 14 86
14 86 15 85
15 85 16 84
16 84 17 83
17 83 18 82
18 82 19 81
19 81 20 80
20 80 21 79
21 79 22 78
22 78 23 77
23 77 24 76
24 76 25 75
25 75 26 74
26 74 27 73
2...

result:

ok 

Test #77:

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

input:

29 K
K.KKK.KKK.KKK.KKK.KKK.KKK.KKK
K.K.K.K.K.K.K.K.K.K.K.K.K.K.K
K.K.K.K.K.K.K.K.K.K.K.K.K.K.K
K.K.K.K.K.K.K.K.K.K.K.K.K.K.K
K.K.K.K.K.K.K.K.K.K.K.K.K.K.K
K.K.K.K.K.K.K.K.K.K.K.K.K.K.K
K.K.K.K.K.K.K.K.K.K.K.K.K.K.K
K.K.K.K.K.K.K.K.K.K.K.K.K.K.K
K.K.K.K.K.K.K.K.K.K.K.K.K.K.K
K.K.K.K.K.K.K.K.K.K.K.K.K...

output:

YES
1 3 2 3
1 5 1 4
1 7 2 7
1 9 1 8
1 11 2 11
1 13 1 12
1 15 2 15
1 17 1 16
1 19 2 19
1 21 1 20
1 23 2 23
1 25 1 24
1 27 2 27
1 29 1 28
29 29 28 29
28 29 27 29
27 29 26 29
26 29 25 29
25 29 24 29
24 29 23 29
23 29 22 29
22 29 21 29
21 29 20 29
20 29 19 29
19 29 18 29
18 29 17 29
17 29 16 29
16 29 15...

result:

ok 

Test #78:

score: 0
Accepted
time: 2ms
memory: 4456kb

input:

100 K
K.KKK.KKK.KKK.KKK.KKK.KKK.KKK.KKK.KKK.KKK.KKK.KKK.KKK.KKK.KKK.KKK.KKK.KKK.KKK.KKK.KKK.KKK.KKK.KKK.KK
K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.
K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K....

output:

YES
1 3 2 3
1 5 1 4
1 7 2 7
1 9 1 8
1 11 2 11
1 13 1 12
1 15 2 15
1 17 1 16
1 19 2 19
1 21 1 20
1 23 2 23
1 25 1 24
1 27 2 27
1 29 1 28
1 31 2 31
1 33 1 32
1 35 2 35
1 37 1 36
1 39 2 39
1 41 1 40
1 43 2 43
1 45 1 44
1 47 2 47
1 49 1 48
1 51 2 51
1 53 1 52
1 55 2 55
1 57 1 56
1 59 2 59
1 61 1 60
1 63...

result:

ok 

Test #79:

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

input:

31 K
K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K
.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.
K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K
.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.
K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K
.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.
K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K
.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.
K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K
.K.K.K....

output:

YES
1 31 2 30
3 31 2 30
2 30 1 29
1 29 2 28
5 31 4 30
4 30 3 29
3 29 2 28
2 28 1 27
1 27 2 26
7 31 6 30
6 30 5 29
5 29 4 28
4 28 3 27
3 27 2 26
2 26 1 25
1 25 2 24
9 31 8 30
8 30 7 29
7 29 6 28
6 28 5 27
5 27 4 26
4 26 3 25
3 25 2 24
2 24 1 23
1 23 2 22
11 31 10 30
10 30 9 29
9 29 8 28
8 28 7 27
7 2...

result:

ok 

Test #80:

score: 0
Accepted
time: 2ms
memory: 4256kb

input:

100 K
K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.
.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K
K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K....

output:

YES
2 100 1 99
1 99 2 98
4 100 3 99
3 99 2 98
2 98 1 97
1 97 2 96
6 100 5 99
5 99 4 98
4 98 3 97
3 97 2 96
2 96 1 95
1 95 2 94
8 100 7 99
7 99 6 98
6 98 5 97
5 97 4 96
4 96 3 95
3 95 2 94
2 94 1 93
1 93 2 92
10 100 9 99
9 99 8 98
8 98 7 97
7 97 6 96
6 96 5 95
5 95 4 94
4 94 3 93
3 93 2 92
2 92 1 91
...

result:

ok 

Test #81:

score: 0
Accepted
time: 2ms
memory: 4204kb

input:

100 K
.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K
K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.
.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K...

output:

YES
1 100 2 99
3 100 2 99
2 99 1 98
1 98 2 97
5 100 4 99
4 99 3 98
3 98 2 97
2 97 1 96
1 96 2 95
7 100 6 99
6 99 5 98
5 98 4 97
4 97 3 96
3 96 2 95
2 95 1 94
1 94 2 93
9 100 8 99
8 99 7 98
7 98 6 97
6 97 5 96
5 96 4 95
4 95 3 94
3 94 2 93
2 93 1 92
1 92 2 91
11 100 10 99
10 99 9 98
9 98 8 97
8 97 7 ...

result:

ok 

Test #82:

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

input:

1 N
N

output:

YES

result:

ok 

Test #83:

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

input:

2 N
NN
NN

output:

NO

result:

ok 

Test #84:

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

input:

3 N
NNN
NNN
NNN

output:

NO

result:

ok 

Test #85:

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

input:

5 N
NNNNN
NNNNN
NNNNN
NNNNN
NNNNN

output:

YES
2 2 3 4
5 5 3 4
3 4 1 5
1 5 2 3
3 3 1 4
1 4 3 5
4 3 3 5
5 4 3 5
3 5 2 3
1 2 3 1
5 2 3 1
3 1 2 3
2 1 4 2
4 2 2 3
2 5 4 4
4 4 2 3
2 3 1 1
1 3 3 2
4 5 2 4
2 4 3 2
5 1 3 2
4 1 5 3
5 3 3 2
3 2 1 1

result:

ok 

Test #86:

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

input:

17 N
NNNNNNNNNNNNNNNNN
NNNNNNNNNNNNNNNNN
NNNNNNNNNNNNNNNNN
NNNNNNNNNNNNNNNNN
NNNNNNNNNNNNNNNNN
NNNNNNNNNNNNNNNNN
NNNNNNNNNNNNNNNNN
NNNNNNNNNNNNNNNNN
NNNNNNNNNNNNNNNNN
NNNNNNNNNNNNNNNNN
NNNNNNNNNNNNNNNNN
NNNNNNNNNNNNNNNNN
NNNNNNNNNNNNNNNNN
NNNNNNNNNNNNNNNNN
NNNNNNNNNNNNNNNNN
NNNNNNNNNNNNNNNNN
NNNNNNN...

output:

YES
3 16 1 17
1 17 2 15
1 16 3 17
5 16 3 17
3 17 2 15
4 14 2 15
2 17 4 16
6 17 4 16
4 16 2 15
2 15 1 13
2 14 3 12
3 12 1 13
1 15 3 14
4 17 2 16
2 16 3 14
7 16 5 15
5 15 3 14
3 14 1 13
1 13 2 11
3 15 1 14
1 14 3 13
1 12 3 13
5 17 4 15
6 14 4 15
8 17 6 16
6 16 4 15
4 15 3 13
5 12 3 13
11 17 9 16
9 16 ...

result:

ok 

Test #87:

score: 0
Accepted
time: 3ms
memory: 4512kb

input:

100 N
NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN
NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN
NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN...

output:

YES
3 100 4 98
5 100 4 98
4 98 2 99
4 100 2 99
2 99 1 97
1 100 2 98
2 98 3 96
3 96 1 97
1 99 3 98
2 100 3 98
7 100 5 99
5 99 3 98
3 98 1 97
1 97 2 95
3 99 1 98
1 98 3 97
1 96 3 97
6 98 4 99
6 100 4 99
4 99 3 97
5 96 3 97
9 100 7 99
7 99 5 98
5 98 3 97
3 97 2 95
4 94 2 95
2 97 4 96
8 98 6 97
6 97 4 9...

result:

ok 

Test #88:

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

input:

100 N
....................................................................................................
....................................................................................................
...............................................................................................

output:

YES

result:

ok 

Test #89:

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

input:

100 N
....................................................................................................
....................................................................................................
...............................................................................................

output:

NO

result:

ok 

Test #90:

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

input:

100 N
........N.....NN...........N.N........N......N......N............NN........N.N..........N........N..
...........N..................N...........N....NN........N................N.......................N.
N..........N...........................N..N.................N......N.................N.........

output:

NO

result:

ok 

Test #91:

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

input:

100 N
.N...NN..N..N..N.N....NN........N..N.N..N..N......N...NN...N........N...................NN..........
....N....N...N.NNN...NN.NNN....NN................N...............N..........N.N....N.........N.N..N.
...NN..N......N....NN........N..N...N.....N......................N.N.N.......N...NN.....N.N....

output:

NO

result:

ok 

Test #92:

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

input:

100 N
......N...N.N.NN........NN.NN.........NN...NNN.NN..NNNN..N.N..NN....NN...N....N.N....NNN........N...
.NNNNNN.....NN......N.N..N.N........N.N......NNNNN.....N..NN..N.....N.N...N.N..N.....N..N.N.N.......
NN.....NNN..........N..N..NN....NN......NN.....N.N........NN....NN.NN..N.N...N...N.N....NN.....

output:

NO

result:

ok 

Test #93:

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

input:

3 N
NNN
N.N
NNN

output:

YES
3 3 1 2
1 2 3 1
3 1 2 3
2 3 1 1
2 1 1 3
1 3 3 2
3 2 1 1

result:

ok 

Test #94:

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

input:

19 N
NNNNNNNNNNNNNNNNNNN
N.................N
N.................N
N.................N
N.................N
N.................N
N.................N
N.................N
N.................N
N.................N
N.................N
N.................N
N.................N
N.................N
N.................

output:

NO

result:

ok 

Test #95:

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

input:

100 N
NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN
N..................................................................................................N
N..............................................................................................

output:

NO

result:

ok 

Test #96:

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

input:

3 N
N.N
.N.
N.N

output:

NO

result:

ok 

Test #97:

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

input:

21 N
N...................N
.N.................N.
..N...............N..
...N.............N...
....N...........N....
.....N.........N.....
......N.......N......
.......N.....N.......
........N...N........
.........N.N.........
..........N..........
.........N.N.........
........N...N........
.......N....

output:

NO

result:

ok 

Test #98:

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

input:

99 N
N.................................................................................................N
.N...............................................................................................N.
..N...............................................................................................

output:

NO

result:

ok 

Test #99:

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

input:

29 N
N.NNN.NNN.NNN.NNN.NNN.NNN.NNN
N.N.N.N.N.N.N.N.N.N.N.N.N.N.N
N.N.N.N.N.N.N.N.N.N.N.N.N.N.N
N.N.N.N.N.N.N.N.N.N.N.N.N.N.N
N.N.N.N.N.N.N.N.N.N.N.N.N.N.N
N.N.N.N.N.N.N.N.N.N.N.N.N.N.N
N.N.N.N.N.N.N.N.N.N.N.N.N.N.N
N.N.N.N.N.N.N.N.N.N.N.N.N.N.N
N.N.N.N.N.N.N.N.N.N.N.N.N.N.N
N.N.N.N.N.N.N.N.N.N.N.N.N...

output:

YES
1 29 2 27
2 29 3 27
4 29 3 27
3 27 1 28
1 28 3 29
3 29 2 27
2 27 1 25
1 25 2 23
1 27 2 25
2 25 3 23
6 29 5 27
5 27 4 25
4 25 3 23
3 23 1 24
1 24 3 25
5 29 4 27
4 27 3 25
3 25 2 23
2 23 1 21
1 21 2 19
1 23 2 21
2 21 3 19
8 29 7 27
7 27 6 25
6 25 5 23
5 23 4 21
4 21 3 19
3 19 1 20
1 20 3 21
7 29 6...

result:

ok 

Test #100:

score: 0
Accepted
time: 2ms
memory: 4316kb

input:

100 N
N.NNN.NNN.NNN.NNN.NNN.NNN.NNN.NNN.NNN.NNN.NNN.NNN.NNN.NNN.NNN.NNN.NNN.NNN.NNN.NNN.NNN.NNN.NNN.NNN.NN
N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.
N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N....

output:

YES
2 99 1 97
1 97 2 95
1 99 2 97
1 100 3 99
3 99 2 97
2 97 3 95
5 99 4 97
4 97 3 95
3 95 1 96
1 96 3 97
4 99 3 97
3 97 2 95
2 95 1 93
1 93 2 91
1 95 2 93
2 93 3 91
7 99 6 97
6 97 5 95
5 95 4 93
4 93 3 91
3 91 1 92
1 92 3 93
6 99 5 97
5 97 4 95
4 95 3 93
3 93 2 91
2 91 1 89
1 89 2 87
1 91 2 89
2 89 ...

result:

ok 

Test #101:

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

input:

31 N
N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N
.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.
N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N
.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.
N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N
.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.
N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N
.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.
N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N
.N.N.N....

output:

NO

result:

ok 

Test #102:

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

input:

100 N
N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.
.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N
N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N....

output:

NO

result:

ok 

Test #103:

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

input:

100 N
.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N
N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.
.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N.N...

output:

NO

result:

ok 

Test #104:

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

input:

1 Q
Q

output:

YES

result:

ok 

Test #105:

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

input:

2 Q
QQ
QQ

output:

YES
1 2 1 1
2 1 1 1
2 2 1 1

result:

ok 

Test #106:

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

input:

3 Q
QQQ
QQQ
QQQ

output:

YES
3 2 1 2
2 3 1 2
1 2 1 1
2 1 1 1
1 3 1 1
3 1 1 1
2 2 1 1
3 3 1 1

result:

ok 

Test #107:

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

input:

5 Q
QQQQQ
QQQQQ
QQQQQ
QQQQQ
QQQQQ

output:

YES
3 2 1 2
4 2 1 2
5 2 1 2
2 3 1 2
3 4 1 2
4 5 1 2
1 2 1 1
2 4 2 1
2 5 2 1
4 3 2 1
5 4 2 1
2 1 1 1
5 3 1 3
3 5 1 3
1 3 1 1
3 1 1 1
1 4 1 1
4 1 1 1
1 5 1 1
5 1 1 1
2 2 1 1
3 3 1 1
4 4 1 1
5 5 1 1

result:

ok 

Test #108:

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

input:

17 Q
QQQQQQQQQQQQQQQQQ
QQQQQQQQQQQQQQQQQ
QQQQQQQQQQQQQQQQQ
QQQQQQQQQQQQQQQQQ
QQQQQQQQQQQQQQQQQ
QQQQQQQQQQQQQQQQQ
QQQQQQQQQQQQQQQQQ
QQQQQQQQQQQQQQQQQ
QQQQQQQQQQQQQQQQQ
QQQQQQQQQQQQQQQQQ
QQQQQQQQQQQQQQQQQ
QQQQQQQQQQQQQQQQQ
QQQQQQQQQQQQQQQQQ
QQQQQQQQQQQQQQQQQ
QQQQQQQQQQQQQQQQQ
QQQQQQQQQQQQQQQQQ
QQQQQQQ...

output:

YES
3 2 1 2
4 2 1 2
5 2 1 2
6 2 1 2
7 2 1 2
8 2 1 2
9 2 1 2
10 2 1 2
11 2 1 2
12 2 1 2
13 2 1 2
14 2 1 2
15 2 1 2
16 2 1 2
17 2 1 2
2 3 1 2
3 4 1 2
4 5 1 2
5 6 1 2
6 7 1 2
7 8 1 2
8 9 1 2
9 10 1 2
10 11 1 2
11 12 1 2
12 13 1 2
13 14 1 2
14 15 1 2
15 16 1 2
16 17 1 2
1 2 1 1
2 4 2 1
2 5 2 1
2 6 2 1
2...

result:

ok 

Test #109:

score: 0
Accepted
time: 7ms
memory: 4192kb

input:

100 Q
QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ
QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ
QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ...

output:

YES
3 2 1 2
4 2 1 2
5 2 1 2
6 2 1 2
7 2 1 2
8 2 1 2
9 2 1 2
10 2 1 2
11 2 1 2
12 2 1 2
13 2 1 2
14 2 1 2
15 2 1 2
16 2 1 2
17 2 1 2
18 2 1 2
19 2 1 2
20 2 1 2
21 2 1 2
22 2 1 2
23 2 1 2
24 2 1 2
25 2 1 2
26 2 1 2
27 2 1 2
28 2 1 2
29 2 1 2
30 2 1 2
31 2 1 2
32 2 1 2
33 2 1 2
34 2 1 2
35 2 1 2
36 2 1...

result:

ok 

Test #110:

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

input:

100 Q
....................................................................................................
....................................................................................................
...............................................................................................

output:

YES

result:

ok 

Test #111:

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

input:

100 Q
....................................................................................................
....................................................................................................
...............................................................................................

output:

NO

result:

ok 

Test #112:

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

input:

100 Q
Q...........................................................Q...............Q.......................
.....Q...Q..Q............Q.......Q...................Q..............Q..Q...Q....Q..Q................
.......Q...Q.....Q.......Q...............................QQ.Q.......Q........Q...Q.Q...........

output:

YES
5 9 11 9
34 9 11 9
37 9 11 9
84 9 11 9
85 9 11 9
8 6 11 9
29 27 11 9
35 33 11 9
39 37 11 9
68 66 11 9
71 69 11 9
100 98 11 9
11 9 11 1
3 18 11 18
17 18 11 18
35 18 11 18
37 18 11 18
83 18 11 18
95 18 11 18
3 26 11 18
22 29 11 18
28 35 11 18
60 67 11 18
77 84 11 18
11 18 11 1
17 60 11 60
44 60 11...

result:

ok 

Test #113:

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

input:

100 Q
.............QQ..QQ...Q.....Q.Q.......Q.....Q..Q......Q...QQ......Q.......Q.QQQ.....Q....Q......Q...
.....QQQ...Q.......QQ.........Q......Q.....QQ...Q...Q.....Q........Q.....QQ....Q...........Q......Q.
QQ.......Q..Q........Q........Q.......Q.....Q..........Q..Q..Q.......Q........QQQ.QQ...Q.......

output:

YES
12 11 13 11
25 11 13 11
32 11 13 11
13 11 13 14
31 17 13 17
35 17 13 17
46 17 13 17
49 17 13 17
50 17 13 17
97 17 13 17
100 17 13 17
2 6 13 17
17 21 13 17
23 27 13 17
46 50 13 17
61 65 13 17
70 74 13 17
80 84 13 17
91 95 13 17
96 100 13 17
13 17 13 14
19 25 13 19
47 53 13 19
63 69 13 19
83 89 13...

result:

ok 

Test #114:

score: 0
Accepted
time: 3ms
memory: 4412kb

input:

100 Q
Q.Q..QQ....QQ.QQQ.QQ..QQ..Q...Q....Q..Q..QQQ.Q.Q...QQ..Q.Q..............Q.....QQ.Q..Q..Q.....Q..Q...
...........Q.Q.QQQ.......QQ.Q..Q..Q...Q....Q...QQ.QQ............Q.QQQ.........Q....QQ............QQ.
Q..QQQQ.Q....Q.....Q......Q..Q.Q....Q.Q.Q.....Q....Q......QQ..Q.....Q.....QQQ.....Q.....Q..Q...

output:

YES
5 3 1 3
7 55 7 3
7 72 7 3
7 78 7 3
7 84 7 3
7 98 7 3
7 99 7 3
55 51 7 3
59 55 7 3
64 60 7 3
73 69 7 3
74 70 7 3
79 75 7 3
7 3 1 3
9 10 9 3
9 49 9 3
9 68 9 3
9 83 9 3
9 91 9 3
20 14 9 3
53 47 9 3
56 50 9 3
60 54 9 3
73 67 9 3
74 68 9 3
75 69 9 3
82 76 9 3
9 3 1 3
14 3 1 3
67 45 25 3
81 59 25 3
91...

result:

ok 

Test #115:

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

input:

3 Q
QQQ
Q.Q
QQQ

output:

YES
3 2 1 2
2 3 1 2
1 2 1 1
2 1 1 1
1 3 1 1
3 1 1 1
3 3 1 1

result:

ok 

Test #116:

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

input:

19 Q
QQQQQQQQQQQQQQQQQQQ
Q.................Q
Q.................Q
Q.................Q
Q.................Q
Q.................Q
Q.................Q
Q.................Q
Q.................Q
Q.................Q
Q.................Q
Q.................Q
Q.................Q
Q.................Q
Q.................

output:

YES
19 2 1 2
18 19 1 2
1 2 1 1
2 19 2 1
19 18 2 1
2 1 1 1
19 3 1 3
17 19 1 3
1 3 1 1
3 19 3 1
19 17 3 1
3 1 1 1
19 4 1 4
16 19 1 4
1 4 1 1
4 19 4 1
19 16 4 1
4 1 1 1
19 5 1 5
15 19 1 5
1 5 1 1
5 19 5 1
19 15 5 1
5 1 1 1
19 6 1 6
14 19 1 6
1 6 1 1
6 19 6 1
19 14 6 1
6 1 1 1
19 7 1 7
13 19 1 7
1 7 1 1...

result:

ok 

Test #117:

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

input:

100 Q
QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ
Q..................................................................................................Q
Q..............................................................................................

output:

YES
100 2 1 2
99 100 1 2
1 2 1 1
2 100 2 1
100 99 2 1
2 1 1 1
100 3 1 3
98 100 1 3
1 3 1 1
3 100 3 1
100 98 3 1
3 1 1 1
100 4 1 4
97 100 1 4
1 4 1 1
4 100 4 1
100 97 4 1
4 1 1 1
100 5 1 5
96 100 1 5
1 5 1 1
5 100 5 1
100 96 5 1
5 1 1 1
100 6 1 6
95 100 1 6
1 6 1 1
6 100 6 1
100 95 6 1
6 1 1 1
100 7 ...

result:

ok 

Test #118:

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

input:

3 Q
Q.Q
.Q.
Q.Q

output:

YES
1 3 1 1
3 1 1 1
2 2 1 1
3 3 1 1

result:

ok 

Test #119:

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

input:

21 Q
Q...................Q
.Q.................Q.
..Q...............Q..
...Q.............Q...
....Q...........Q....
.....Q.........Q.....
......Q.......Q......
.......Q.....Q.......
........Q...Q........
.........Q.Q.........
..........Q..........
.........Q.Q.........
........Q...Q........
.......Q....

output:

YES
20 2 1 21
19 3 1 21
18 4 1 21
17 5 1 21
16 6 1 21
15 7 1 21
14 8 1 21
13 9 1 21
12 10 1 21
10 12 1 21
9 13 1 21
8 14 1 21
7 15 1 21
6 16 1 21
5 17 1 21
4 18 1 21
3 19 1 21
2 20 1 21
1 21 1 1
21 1 1 1
2 2 1 1
3 3 1 1
4 4 1 1
5 5 1 1
6 6 1 1
7 7 1 1
8 8 1 1
9 9 1 1
10 10 1 1
11 11 1 1
12 12 1 1
13...

result:

ok 

Test #120:

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

input:

99 Q
Q.................................................................................................Q
.Q...............................................................................................Q.
..Q...............................................................................................

output:

YES
98 2 1 99
97 3 1 99
96 4 1 99
95 5 1 99
94 6 1 99
93 7 1 99
92 8 1 99
91 9 1 99
90 10 1 99
89 11 1 99
88 12 1 99
87 13 1 99
86 14 1 99
85 15 1 99
84 16 1 99
83 17 1 99
82 18 1 99
81 19 1 99
80 20 1 99
79 21 1 99
78 22 1 99
77 23 1 99
76 24 1 99
75 25 1 99
74 26 1 99
73 27 1 99
72 28 1 99
71 29 1...

result:

ok 

Test #121:

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

input:

29 Q
Q.QQQ.QQQ.QQQ.QQQ.QQQ.QQQ.QQQ
Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q
Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q
Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q
Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q
Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q
Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q
Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q
Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q
Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q...

output:

YES
2 3 2 1
2 5 2 1
2 7 2 1
2 9 2 1
2 11 2 1
2 13 2 1
2 15 2 1
2 17 2 1
2 19 2 1
2 21 2 1
2 23 2 1
2 25 2 1
2 27 2 1
2 29 2 1
4 3 2 1
6 5 2 1
8 7 2 1
10 9 2 1
12 11 2 1
14 13 2 1
16 15 2 1
18 17 2 1
20 19 2 1
22 21 2 1
24 23 2 1
26 25 2 1
28 27 2 1
2 1 1 1
5 3 1 3
6 3 1 3
7 3 1 3
8 3 1 3
9 3 1 3
10 ...

result:

ok 

Test #122:

score: 0
Accepted
time: 4ms
memory: 4156kb

input:

100 Q
Q.QQQ.QQQ.QQQ.QQQ.QQQ.QQQ.QQQ.QQQ.QQQ.QQQ.QQQ.QQQ.QQQ.QQQ.QQQ.QQQ.QQQ.QQQ.QQQ.QQQ.QQQ.QQQ.QQQ.QQQ.QQ
Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.
Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q....

output:

YES
2 3 2 1
2 5 2 1
2 7 2 1
2 9 2 1
2 11 2 1
2 13 2 1
2 15 2 1
2 17 2 1
2 19 2 1
2 21 2 1
2 23 2 1
2 25 2 1
2 27 2 1
2 29 2 1
2 31 2 1
2 33 2 1
2 35 2 1
2 37 2 1
2 39 2 1
2 41 2 1
2 43 2 1
2 45 2 1
2 47 2 1
2 49 2 1
2 51 2 1
2 53 2 1
2 55 2 1
2 57 2 1
2 59 2 1
2 61 2 1
2 63 2 1
2 65 2 1
2 67 2 1
2 6...

result:

ok 

Test #123:

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

input:

31 Q
Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q
.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.
Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q
.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.
Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q
.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.
Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q
.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.
Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q
.Q.Q.Q....

output:

YES
5 3 1 3
7 3 1 3
9 3 1 3
11 3 1 3
13 3 1 3
15 3 1 3
17 3 1 3
19 3 1 3
21 3 1 3
23 3 1 3
25 3 1 3
27 3 1 3
29 3 1 3
31 3 1 3
2 4 1 3
3 5 1 3
4 6 1 3
5 7 1 3
6 8 1 3
7 9 1 3
8 10 1 3
9 11 1 3
10 12 1 3
11 13 1 3
12 14 1 3
13 15 1 3
14 16 1 3
15 17 1 3
16 18 1 3
17 19 1 3
18 20 1 3
19 21 1 3
20 22 1...

result:

ok 

Test #124:

score: 0
Accepted
time: 4ms
memory: 4160kb

input:

100 Q
Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.
.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q
Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q....

output:

YES
5 3 1 3
7 3 1 3
9 3 1 3
11 3 1 3
13 3 1 3
15 3 1 3
17 3 1 3
19 3 1 3
21 3 1 3
23 3 1 3
25 3 1 3
27 3 1 3
29 3 1 3
31 3 1 3
33 3 1 3
35 3 1 3
37 3 1 3
39 3 1 3
41 3 1 3
43 3 1 3
45 3 1 3
47 3 1 3
49 3 1 3
51 3 1 3
53 3 1 3
55 3 1 3
57 3 1 3
59 3 1 3
61 3 1 3
63 3 1 3
65 3 1 3
67 3 1 3
69 3 1 3
71...

result:

ok 

Test #125:

score: 0
Accepted
time: 4ms
memory: 4100kb

input:

100 Q
.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q
Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.
.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q.Q...

output:

YES
3 6 3 2
3 8 3 2
3 10 3 2
3 12 3 2
3 14 3 2
3 16 3 2
3 18 3 2
3 20 3 2
3 22 3 2
3 24 3 2
3 26 3 2
3 28 3 2
3 30 3 2
3 32 3 2
3 34 3 2
3 36 3 2
3 38 3 2
3 40 3 2
3 42 3 2
3 44 3 2
3 46 3 2
3 48 3 2
3 50 3 2
3 52 3 2
3 54 3 2
3 56 3 2
3 58 3 2
3 60 3 2
3 62 3 2
3 64 3 2
3 66 3 2
3 68 3 2
3 70 3 2
3...

result:

ok 

Test #126:

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

input:

1 R
R

output:

YES

result:

ok 

Test #127:

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

input:

2 R
RR
RR

output:

YES
2 2 1 2
1 2 1 1
2 1 1 1

result:

ok 

Test #128:

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

input:

3 R
RRR
RRR
RRR

output:

YES
2 2 1 2
3 2 1 2
1 2 1 1
2 3 2 1
2 1 1 1
3 3 1 3
1 3 1 1
3 1 1 1

result:

ok 

Test #129:

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

input:

5 R
RRRRR
RRRRR
RRRRR
RRRRR
RRRRR

output:

YES
2 2 1 2
3 2 1 2
4 2 1 2
5 2 1 2
1 2 1 1
2 3 2 1
2 4 2 1
2 5 2 1
2 1 1 1
3 3 1 3
4 3 1 3
5 3 1 3
1 3 1 1
3 4 3 1
3 5 3 1
3 1 1 1
4 4 1 4
5 4 1 4
1 4 1 1
4 5 4 1
4 1 1 1
5 5 1 5
1 5 1 1
5 1 1 1

result:

ok 

Test #130:

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

input:

17 R
RRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRR
RRRRRRR...

output:

YES
2 2 1 2
3 2 1 2
4 2 1 2
5 2 1 2
6 2 1 2
7 2 1 2
8 2 1 2
9 2 1 2
10 2 1 2
11 2 1 2
12 2 1 2
13 2 1 2
14 2 1 2
15 2 1 2
16 2 1 2
17 2 1 2
1 2 1 1
2 3 2 1
2 4 2 1
2 5 2 1
2 6 2 1
2 7 2 1
2 8 2 1
2 9 2 1
2 10 2 1
2 11 2 1
2 12 2 1
2 13 2 1
2 14 2 1
2 15 2 1
2 16 2 1
2 17 2 1
2 1 1 1
3 3 1 3
4 3 1 3
...

result:

ok 

Test #131:

score: 0
Accepted
time: 3ms
memory: 4240kb

input:

100 R
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR...

output:

YES
2 2 1 2
3 2 1 2
4 2 1 2
5 2 1 2
6 2 1 2
7 2 1 2
8 2 1 2
9 2 1 2
10 2 1 2
11 2 1 2
12 2 1 2
13 2 1 2
14 2 1 2
15 2 1 2
16 2 1 2
17 2 1 2
18 2 1 2
19 2 1 2
20 2 1 2
21 2 1 2
22 2 1 2
23 2 1 2
24 2 1 2
25 2 1 2
26 2 1 2
27 2 1 2
28 2 1 2
29 2 1 2
30 2 1 2
31 2 1 2
32 2 1 2
33 2 1 2
34 2 1 2
35 2 1 ...

result:

ok 

Test #132:

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

input:

100 R
....................................................................................................
....................................................................................................
...............................................................................................

output:

YES

result:

ok 

Test #133:

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

input:

100 R
....................................................................................................
....................................................................................................
...............................................................................................

output:

NO

result:

ok 

Test #134:

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

input:

100 R
..........R............R....R....R.....R.RR.............R..........................R................
...R....R..........R......................R.R.......R......R.....................R..R.....R.R...R.R.
..........R...R........R..................R..R..............R...RR....R...R............R.......

output:

YES
18 3 18 15
18 55 18 15
18 83 18 15
18 95 18 15
18 15 3 15
22 15 3 15
24 15 3 15
51 15 3 15
63 15 3 15
66 15 3 15
85 15 3 15
92 31 92 15
92 95 92 15
92 97 92 15
92 15 3 15
3 15 3 11
3 24 3 11
3 43 3 11
13 46 3 46
19 46 3 46
22 46 3 46
23 46 3 46
28 46 3 46
38 39 38 46
38 45 38 46
38 46 3 46
60 46...

result:

ok 

Test #135:

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

input:

100 R
R.....R.R..........R..R.....R....R.....RR.RR.RR.R.R...R.RR.R....RR................R.....R.R.R.....R.
....R...R.........R................R..........R...........R....R.......R.R..R.R.R.......RRRR.RRRR.R.
..R.......R....RRR.......R.........R....R.........R.RRR....R.....RRR.R.R..R..R.R....R....RRR...

output:

YES
8 6 4 6
12 6 4 6
27 6 4 6
34 6 4 6
36 6 4 6
39 6 4 6
40 6 4 6
43 6 4 6
47 6 4 6
50 6 4 6
54 6 4 6
57 6 4 6
59 6 4 6
64 6 4 6
75 6 4 6
96 6 4 6
97 6 4 6
99 6 4 6
100 6 4 6
4 6 4 1
5 10 4 10
6 10 4 10
22 10 4 10
34 10 4 10
46 10 4 10
51 10 4 10
54 10 4 10
59 10 4 10
65 10 4 10
70 10 4 10
74 10 4 1...

result:

ok 

Test #136:

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

input:

100 R
...R...R.....R........R....RRRR.R.RR.RR......R....R.R..R....RR.R.R..RR......RR...R....R...R...RRR...
....RR...R.R.R.R.R.RRR..R....R..R.R...RR.....R.R...RRR..R......R..R...R....R..RR.RRRR.R..RR..R....R.
R..R..RR.....R....RR.....RRRR..R..R.R.RRR.R...R.RRR.RR...R....R..R......R...........RR..R.R....

output:

YES
5 1 3 1
8 1 3 1
11 1 3 1
19 1 3 1
20 1 3 1
30 1 3 1
31 1 3 1
39 1 3 1
42 1 3 1
44 1 3 1
52 1 3 1
55 1 3 1
59 1 3 1
63 1 3 1
64 1 3 1
67 1 3 1
68 1 3 1
78 1 3 1
82 1 3 1
85 1 3 1
92 1 3 1
94 1 3 1
95 1 3 1
3 1 3 4
9 7 3 7
11 7 3 7
13 7 3 7
18 7 3 7
23 7 3 7
26 7 3 7
36 7 3 7
39 7 3 7
43 7 3 7
47 ...

result:

ok 

Test #137:

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

input:

3 B
B..
B..
..B

output:

NO

result:

ok 

Test #138:

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

input:

3 R
RRR
R.R
RRR

output:

YES
3 2 1 2
1 2 1 1
2 3 2 1
2 1 1 1
3 3 1 3
1 3 1 1
3 1 1 1

result:

ok 

Test #139:

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

input:

19 R
RRRRRRRRRRRRRRRRRRR
R.................R
R.................R
R.................R
R.................R
R.................R
R.................R
R.................R
R.................R
R.................R
R.................R
R.................R
R.................R
R.................R
R.................

output:

YES
19 2 1 2
1 2 1 1
2 19 2 1
2 1 1 1
19 3 1 3
1 3 1 1
3 19 3 1
3 1 1 1
19 4 1 4
1 4 1 1
4 19 4 1
4 1 1 1
19 5 1 5
1 5 1 1
5 19 5 1
5 1 1 1
19 6 1 6
1 6 1 1
6 19 6 1
6 1 1 1
19 7 1 7
1 7 1 1
7 19 7 1
7 1 1 1
19 8 1 8
1 8 1 1
8 19 8 1
8 1 1 1
19 9 1 9
1 9 1 1
9 19 9 1
9 1 1 1
19 10 1 10
1 10 1 1
10 1...

result:

ok 

Test #140:

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

input:

100 R
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
R..................................................................................................R
R..............................................................................................

output:

YES
100 2 1 2
1 2 1 1
2 100 2 1
2 1 1 1
100 3 1 3
1 3 1 1
3 100 3 1
3 1 1 1
100 4 1 4
1 4 1 1
4 100 4 1
4 1 1 1
100 5 1 5
1 5 1 1
5 100 5 1
5 1 1 1
100 6 1 6
1 6 1 1
6 100 6 1
6 1 1 1
100 7 1 7
1 7 1 1
7 100 7 1
7 1 1 1
100 8 1 8
1 8 1 1
8 100 8 1
8 1 1 1
100 9 1 9
1 9 1 1
9 100 9 1
9 1 1 1
100 10 1...

result:

ok 

Test #141:

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

input:

3 R
R.R
.R.
R.R

output:

NO

result:

ok 

Test #142:

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

input:

21 R
R...................R
.R.................R.
..R...............R..
...R.............R...
....R...........R....
.....R.........R.....
......R.......R......
.......R.....R.......
........R...R........
.........R.R.........
..........R..........
.........R.R.........
........R...R........
.......R....

output:

NO

result:

ok 

Test #143:

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

input:

99 R
R.................................................................................................R
.R...............................................................................................R.
..R...............................................................................................

output:

NO

result:

ok 

Test #144:

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

input:

29 R
R.RRR.RRR.RRR.RRR.RRR.RRR.RRR
R.R.R.R.R.R.R.R.R.R.R.R.R.R.R
R.R.R.R.R.R.R.R.R.R.R.R.R.R.R
R.R.R.R.R.R.R.R.R.R.R.R.R.R.R
R.R.R.R.R.R.R.R.R.R.R.R.R.R.R
R.R.R.R.R.R.R.R.R.R.R.R.R.R.R
R.R.R.R.R.R.R.R.R.R.R.R.R.R.R
R.R.R.R.R.R.R.R.R.R.R.R.R.R.R
R.R.R.R.R.R.R.R.R.R.R.R.R.R.R
R.R.R.R.R.R.R.R.R.R.R.R.R...

output:

YES
2 3 2 1
2 5 2 1
2 7 2 1
2 9 2 1
2 11 2 1
2 13 2 1
2 15 2 1
2 17 2 1
2 19 2 1
2 21 2 1
2 23 2 1
2 25 2 1
2 27 2 1
2 29 2 1
2 1 1 1
3 3 1 3
4 3 1 3
5 3 1 3
6 3 1 3
7 3 1 3
8 3 1 3
9 3 1 3
10 3 1 3
11 3 1 3
12 3 1 3
13 3 1 3
14 3 1 3
15 3 1 3
16 3 1 3
17 3 1 3
18 3 1 3
19 3 1 3
20 3 1 3
21 3 1 3
22...

result:

ok 

Test #145:

score: 0
Accepted
time: 2ms
memory: 4160kb

input:

100 R
R.RRR.RRR.RRR.RRR.RRR.RRR.RRR.RRR.RRR.RRR.RRR.RRR.RRR.RRR.RRR.RRR.RRR.RRR.RRR.RRR.RRR.RRR.RRR.RRR.RR
R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.
R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R....

output:

YES
2 3 2 1
2 5 2 1
2 7 2 1
2 9 2 1
2 11 2 1
2 13 2 1
2 15 2 1
2 17 2 1
2 19 2 1
2 21 2 1
2 23 2 1
2 25 2 1
2 27 2 1
2 29 2 1
2 31 2 1
2 33 2 1
2 35 2 1
2 37 2 1
2 39 2 1
2 41 2 1
2 43 2 1
2 45 2 1
2 47 2 1
2 49 2 1
2 51 2 1
2 53 2 1
2 55 2 1
2 57 2 1
2 59 2 1
2 61 2 1
2 63 2 1
2 65 2 1
2 67 2 1
2 6...

result:

ok 

Test #146:

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

input:

31 R
R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R
.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.
R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R
.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.
R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R
.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.
R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R
.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.
R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R
.R.R.R....

output:

NO

result:

ok 

Test #147:

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

input:

100 R
R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.
.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R
R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R....

output:

NO

result:

ok 

Test #148:

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

input:

100 R
.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R
R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.
.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R.R...

output:

NO

result:

ok