QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#184097#2030. Paint by Letterspaul2008#10 12ms5692kbC++141.1kb2023-09-20 12:39:352024-07-04 02:05:19

Judging History

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

  • [2024-07-04 02:05:19]
  • 评测
  • 测评结果:10
  • 用时:12ms
  • 内存:5692kb
  • [2023-09-20 12:39:35]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int N=1005;

bool can[N][N];
char a[N][N];
pair <int,int> q[N*N];
int dx[4]={0,1,-1,0};
int dy[4]={1,0,0,-1};

void bfs(int x,int y,char t)
{
	int l=1,r=0;
	can[x][y]=false, q[++r]=make_pair(x,y);
	while(l<=r)
	{
		int x=q[l].first,y=q[l].second;
		l++;
		for(int i=0;i<4;i++)
		{
			int newx=x+dx[i],newy=y+dy[i];
			if(can[newx][newy] && a[newx][newy]==t)
				can[newx][newy]=false, q[++r]=make_pair(newx,newy);
		}
	}
}

int main()
{
	int n,m,q;
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> m >> q;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin >> a[i][j];

	for(int i=1;i<=q;i++)
	{
		int x1,y1,x2,y2;
		cin >> x1 >> y1 >> x2 >> y2;
		for(int i=x1;i<=x2;i++)
			for(int j=y1;j<=y2;j++)
				can[i][j]=true;

		int ans=0;
		for(int i=x1;i<=x2;i++)
			for(int j=y1;j<=y2;j++)
				if(can[i][j])
					ans++, bfs(i,j,a[i][j]);

		cout << ans << endl;

		for(int i=x1;i<=x2;i++)
			for(int j=y1;j<=y2;j++)
				can[i][j]=false;
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 5
Accepted
time: 1ms
memory: 5692kb

input:

4 8 9
ABBAAAAA
ABAAAABA
CAADABBA
AAAAAAAA
1 1 4 8
3 5 3 8
1 3 2 4
1 4 2 5
1 1 3 3
4 4 4 4
2 6 4 8
3 5 4 6
1 6 3 8

output:

6
3
2
1
4
1
3
2
2

result:

ok 9 lines

Test #2:

score: 5
Accepted
time: 12ms
memory: 5608kb

input:

50 45 1000
BBBAAAAABBABAABBBBAABBBBABBAABBAABABBBBBBABAB
BABABBBAAAAAAABAABABBBAABABBBBABABBBABBBBBABA
ABBAAAABAABBBABABBAABBBBBAABAAABAABABAAAABAAB
BBABBABABAAABBAAABBABBABABABAAAAAAAAABAAAABBB
BBABBBABBAAABBBAABBAABAAABBBBBBBBAABABBBBABAB
BABABAAAABBBBBBABBABAAABBAAABBBBBBABBBABBAABB
BBAAABAAAAAAA...

output:

40
26
121
20
23
85
12
247
51
24
17
13
48
29
35
6
19
2
26
26
158
100
18
46
36
42
28
9
149
119
4
5
65
105
23
57
30
14
39
43
44
83
17
1
29
41
10
10
33
132
30
21
39
10
16
38
127
57
22
177
15
6
84
65
17
21
28
44
14
22
44
32
96
34
9
1
98
31
35
94
79
16
80
17
30
20
20
49
50
55
9
29
6
37
16
30
14
36
88
5
58...

result:

ok 1000 lines

Test #3:

score: 0
Time Limit Exceeded

input:

1000 1000 1000
JBBBJQJJBJZJJJSJWJJLJJJJJYJJDJDJJJHJKJDDJQJGGJAJQJJSJJJJZJJJJJPPPPPJJJJCJYJJGJJJJVJJJAJJAJHJUJJJJEEEJRJFFJJJJPPPJJWJBJJJJJJXJJJJYJLJJBJDJJJJVJEJFFFFFJJQJLJJNJJMJQJJYYJVJJKJJJHHJJEJJJSJJJJJJJJJJJJJJJYRMRRZRSRVVVVVVVVVDDVWVYVUVJJVQVUVKVLVVHHVVLVVAAVVWVDVVNVSVFVVVVHVNVVVVCVXXXVWVRVVVVVQV...

output:

41215
98045
13006
15385
181643
130328
6971
9714
12717
135813
164970
10514
67084
54684
5931
4119
21250
14437
7930
24602
64285
171517
19932
104818
35480
12387
55940
24200
64003
8490
10434
91309
12559
9367
11315
14214
47159
24946
38811
65328
46819
74067
60620
62612
445
45156
72503
39848
64885
10332
729...

result:


Test #4:

score: 0
Time Limit Exceeded

input:

1000 1000 1000
RRWRRZRRBRRRMRRRRRRRRQRRRRRYRRRRRRQRSRNNRURDRRRIRRRRSRFRRRRURRRRRKKRPPRMRGREERCRSRCRXXXRHRRRJRRRJRRTRNNRRRHRIRRRRWRRRRRRRBRRRRERRRRJRDDDRRRRRRPRRYRRQRRRRRROORRRGRURRRRKRRRRRRRRRRRRDRRRRRRRRRRFRBRNRRRBBRRNRRURRMRRNRRGRRRRRURRRFRRRRRRSSSRRYRGRRRGRURHRRYRRSRRRRURRURNRRRLRORQQRBBRRMRXRSSX...

output:

72696
20530
46499
40798
12058
109488
13521
82375
53595
84135
6260
45616
67445
34187
64419
42491
42951
79192
6925
19525
38752
144229
61230
14985
90122
34969
14577
11438
172374
26744
26982
32936
35236
66682
70647
29132
55886
15693
41597
24098
7793
48979
28233
47609
16907
58159
91435
72190
31184
78728
...

result:


Test #5:

score: 0
Time Limit Exceeded

input:

1000 1000 1000
BPPPPPPPPPPPPPSPPPQPPIPTPJPPPCPZPZPPPCPPQPPDPPZPXPPPPPPPOPHPBBBPPPPPVPPPPUUUPNPQPPAPPPPPPPSPIPPCPWPQPPPUUPDPNPHPPPGGPPPNNPPPPWPPPUPPPPUPPPPOPOPPPBPNPGPBPYPZPOPPPPPPJPPSPCCCPPQQPPPPPPPPPPPPFPNPPPEEPPPPPPPHPPTPPPNPPTTTPPPPPPZPPSPOOOPWPDPPPWPKPPZPGPHPPKPPPJPPJPOOPPAAPUPPOPPYPPTTPPPZPPSPP...

output:

96531
5337
34788
114265
64995
10289
28001
77386
17468
26652
1273
36676
63736
8717
47904
151107
127350
60438
131362
2606
17207
47321
3431
44642
5860
2274
21712
25076
31843
24831
8084
348
76173
39264
16906
3722
8551
19569
78501
17394
1904
14463
1285
27075
25399
4295
26677
128214
5227
176895
9490
48316...

result:


Test #6:

score: 0
Time Limit Exceeded

input:

1000 1000 1000
OOTYEVJGBKKAGHFFHQRPELAEERXBQEEBBXDDCHTHHBBUGSSKVJJMKZAXSHRMBLLUYRIISQUQQFJJOXOKKUQSCHRUUGTRIVGPGYVUIYVYKHNRGJJSIZZXPLLSRSGQMJQQZYDDQQPZVVKKMSTLAOIIJEMWXTMTBYFYYBIDYOOPNXQQPFDDYZZAXXWTQBJJAKKTIIVDHBBPPQXXTTGSDOCDDUUCQQAAWTTDDBOOHJVVAANKFXJMCYYSZJJVIESXNNQQHHEYXXWCEDUCWTEDTLPUVICCHDDQR...

output:

302479
106429
25287
4519
313626
312524
287417
687
230670
122029
34961
169381
157276
143151
131419
166693
10551
198116
18073
32617
8332
138450
205679
48182
174741
7806
18199
27331
265343
320892
15686
4401
21905
274362
2750
49150
64235
14936
17755
1189
131625
66631
329
17225
107267
194722
40146
13971
...

result:


Test #7:

score: 0
Time Limit Exceeded

input:

1000 1000 1000
IBVGGWZZWUFRZYCCGNNTTAJDDVMOETRYJGGAIAGVYLILTTCFFBBVKPPSFOTJTEULLTKKHGPPFFDNNWJGZJKJAASWQGKKZNZIDDWAABBUYWENFRCVVWWTTWFIILLGGLKKBZAAJJPPNRRQAQCKHKSACHHKWKKFYYJJWWBBCRRJJZPUUZZRYCXZVCTUTYYBVVLQTACCYYEVUUOOVXXNUUIRDDAOCCAAVVYYBVVKUGGWUCQBZTTEFFVMUUWAAPBBYYFOGPRWECLLFVZZBVGHDDSQFYYZZFQOI...

output:

543596
16041
384508
136233
106870
78150
119063
392949
65919
11784
181503
8401
290508
2338
454461
103782
120173
95257
127133
194273
62428
270721
4530
169495
2356
116953
259941
105790
1088
284541
98998
36559
9056
545711
36750
70665
236849
217434
12997
182316
49426
31781
170875
39980
26270
51092
501468...

result:


Test #8:

score: 0
Time Limit Exceeded

input:

1000 1000 1000
HEMKGSSPNZYBEHHYIICGQZINEIOYUYZQROFTPJAVVAAVVXIISSBBYLAWYYOAAQLSPFIWYYHZZWQNGGEEOWWSHQQJADDBEEYFOBKOORRPEVGGECCMOFFBPPUSSERBBAOEELGIXAUKNNWAAPLLIRXTPXXGGHKIKYJVVGJTLWBQKKZOLWIIDGROSXBEMGGNBQDTDDQQCWYPVBXRPKHXXWQAAFZZNNZKKMJEPZYNJMWERKKRWSQQRNQXKIYCVFJGGZZGWWXTTIXQQKOLLNOIBBYFGGWOOYOYV...

output:

174777
7416
279333
165389
49215
34155
480268
69004
2636
86985
16974
42091
443252
243314
72600
61090
126571
379476
167756
57247
77598
317400
59751
110217
173026
21823
13982
409698
128408
251512
117204
126402
170897
97493
5729
202726
387790
4235
85752
324241
87238
79127
39585
89205
547332
465980
77171...

result:


Test #9:

score: 0
Time Limit Exceeded

input:

1000 1000 1000
RRYDXXPWWEAEEAXPPPRRWGWSJJXXMBBBIIPMPMEKKVVVOZBBYYWEATTLMWHQQZUQQKHHHQZWWNNNOOWDWKVUCCAAAOISSYYHOOPCCAAHGGGZNOIIGTSUUUMMWZZMQXQJUFMURSSPPRBBCOLMMLXXXOOOHTSSPPYYDJJAAMMDAQJJJGGGEQQBBKLZZGGFZZZMMFJPPXXXZKLKLFCYYZTZZZIUKKKXAVAAVRNNSHAHHTHPXHZEZEOOGGYTRDIIIFIIHUBBBHSTNCCRIRHLLXMAOEBWBKIKV...

output:

52507
51626
264566
290150
49781
42333
23737
76419
22919
56983
61231
3306
10664
115216
3893
448
13806
37616
101562
124127
119489
164681
16414
55778
10729
26400
451
12369
10713
96073
80825
381274
159381
147183
310048
55082
1630
75017
138421
145623
144158
103748
71876
20646
51442
12779
114122
14469
117...

result:


Test #10:

score: 0
Time Limit Exceeded

input:

1000 1000 1000
NNNKJYRPXSTJJKVVVZJJYYYGGHLHDWCCGGLJOOEEEUUAURRRFKKTTTUUUJJGGYUSSSTJWWREEWUMMGKQIIVVAZARLRAAEQQKXXSJJJQRUJJJOGNNAAQDDBEBBWWWRRGSRRBXXIISGGGHIIOOFFFSDQQQRHKKKPPTASSVKTDDEFAFJGJGOAOVVVXUUBKTRXXXBBAAKKYIILLYHHTTIRRMMWWOUBBYKKOOORAVVHHJJOHHXXPPXXMHXXROOERCKCMMOFYYYKKZLLNNNAAOOOEEZLKEETTHH...

output:

146826
118055
14296
30714
3019
78465
115619
325653
28630
237444
22357
218173
89573
233839
224685
268437
238487
48162
162488
256905
59087
44904
61773
62905
32341
135612
9933
36648
67494
43282
57591
42903
18705
434
47128
360128
5832
48548
309107
48551
237183
18235
280100
68333
5197
40793
378
255333
10...

result:


Test #11:

score: 0
Time Limit Exceeded

input:

1000 1000 1000
SSSNNUDHWWWMMJPFFCJSSGGZCHBHJJJLVRVOOPHHWWVXFFQQUSSPSSSHHJMMHQQACCMBBPPSCCXEZZAPPYQQQHHVVYBKBVVUOOJJJGGGZUHZMHHHTTZLZFFKKSWIITEEESWWJJBTKFFDIDBBDFFORRKWTMWEESSTYMYYYVVKKKHHJWEXJJWQASYHJDXGGMTTCCMLLVVVHIKICADAPDDDYYNNKDGGPVQMNCCCKNNEEWKSLFFFLLLREEIFLGGXUUCTTGYYWWWRRRIWWVYOJJOUPPQBBBUUY...

output:

5185
21238
243592
267066
76146
168668
173528
180998
18885
262889
62216
13699
221325
230227
376136
108389
50021
46902
59543
155395
183278
12778
75764
186581
56608
236771
26063
130409
204796
135238
75185
211925
165002
311158
258379
40568
59486
128910
78594
306799
100832
154951
191518
78786
14260
18105...

result:


Test #12:

score: 0
Time Limit Exceeded

input:

1000 1000 1000
DDDDDDDLLLLLLLLLLLLAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
1
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
1
1
1
1
1
2
1
1
1
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
1
1
1
1
1
1
1
3
1
1
1
1
1
1
1
1
1
1
2
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
5
13
22
12
1
15
8
8
19
8
14
5
27
14
12
17
25
3
17
...

result:


Test #13:

score: 0
Time Limit Exceeded

input:

1000 1000 1000
VVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG...

output:

1
1
1
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
2
1
1
1
1
1
1
1
1
1
1
1
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
2
1
1
1
2
2
1
1
1
1
2
1
1
1
1
1
2
2
1
1
1
1
1
1
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
1
1
1
1
1
1
1
1
1
1
2
2
1
1
1
1
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
2
1
1
1
1
1
1
8
3
19
7
13
17
14
9
5
20
24
1
15
3
12
27
21
28
25
...

result:


Test #14:

score: 0
Time Limit Exceeded

input:

1000 1000 1000
PPPPPPPPPPPPPPPPPSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH...

output:

1
1
1
1
1
1
1
1
2
1
1
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
1
1
1
1
1
1
2
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
1
1
1
1
1
1
1
1
2
1
1
1
1
1
1
1
1
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
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
8
22
6
10
4
9
25
12
13
11
9
27
12
6
5
5
17
22
3
14...

result:


Test #15:

score: 0
Time Limit Exceeded

input:

1000 1000 1000
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
1
1
1
1
2
1
1
1
1
1
1
1
1
1
2
2
1
1
1
1
1
2
1
1
3
1
1
1
1
1
2
1
1
1
1
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
1
1
1
1
1
1
1
1
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
5
2
10
10
6
12
7
27
16
4
13
3
1
14
22
3
8
7
7
4
20...

result:


Test #16:

score: 0
Time Limit Exceeded

input:

994 992 1000
KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK...

output:

1
1
1
1
1
1
2
1
1
1
1
1
1
1
1
1
1
2
3
1
3
1
1
1
1
1
3
1
1
2
1
1
1
1
1
1
1
1
1
1
1
2
3
1
1
1
2
1
1
1
1
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
5
1
1
1
1
1
1
1
1
1
1
1
2
1
1
2
1
1
1
1
1
1
1
2
2
1
1
1
1
1
1
1
1
1
1
1
4
1
2
1
1
1
2
1
1
1
1
1
1
1
1
3
1
2
1
1
1
2
1
76
48
25
81
51
65
109
11
18
14
18
47
21
3
22
104
1...

result:


Test #17:

score: 0
Time Limit Exceeded

input:

980 995 1000
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

output:

1
7
1
1
1
4
1
13
1
5
1
1
1
1
1
2
4
9
1
2
1
1
1
1
1
1
2
18
9
2
1
10
29
1
1
2
2
10
16
1
1
14
1
1
8
1
1
16
1
1
4
1
1
1
1
1
1
1
1
1
1
1
1
2
1
10
1
1
1
1
1
3
3
1
1
1
1
5
2
1
1
3
11
5
1
1
1
2
1
1
1
2
1
2
1
1
1
1
1
1
21
1
1
1
1
1
1
1
1
1
3
1
1
17
1
10
1
1
10
1
1
1
1
1
3
234
246
1385
4890
5877
11966
402
231...

result:


Test #18:

score: 0
Time Limit Exceeded

input:

980 995 1000
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW...

output:

2
3
1
1
2
2
1
1
1
7
1
1
1
1
1
1
1
1
1
1
1
1
1
2
3
3
1
1
1
2
1
1
3
1
1
1
12
1
2
1
1
1
1
1
1
1
2
1
3
2
2
1
1
2
1
1
1
1
1
2
1
3
2
1
1
1
1
1
2
1
1
1
17
1
1
2
1
8
1
1
4
1
1
2
1
1
2
1
3
1
1
1
1
1
2
2
1
8
1
3
1
2
1
2
2
1
3
2
2
1
2
1
1
11
1
2
2
1
1
1
1
5
1
2
1
9
2705
2356
9410
21
3690
3651
1258
7937
3918
18...

result:


Test #19:

score: 0
Time Limit Exceeded

input:

994 990 1000
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII...

output:

1
1
1
1
1
1
1
2
1
1
1
1
1
1
1
1
1
2
2
1
1
2
1
1
1
1
1
1
1
1
2
1
2
3
1
3
1
1
1
2
1
2
1
2
2
1
2
2
2
1
1
1
1
4
3
1
1
1
1
2
1
1
2
1
1
2
1
1
1
1
2
1
1
1
1
1
1
2
1
1
2
1
9
2
1
1
1
1
1
1
2
1
1
3
1
2
1
1
1
1
1
2
2
1
1
1
1
1
1
1
1
1
2
1
8
1
8
19
1
2
1
1
1
1
1
39
47
1661
30
17
12
3860
23
10684
60
584
68
2714
...

result:


Test #20:

score: 0
Time Limit Exceeded

input:

984 992 1000
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS...

output:

1
2
1
1
1
2
1
1
1
3
1
2
1
1
1
1
1
1
1
1
1
1
2
1
1
1
2
1
1
1
1
1
2
1
2
1
1
1
1
1
1
1
1
1
3
1
1
1
1
1
1
1
2
1
1
1
1
2
1
1
2
2
1
2
2
1
1
1
1
1
1
1
1
1
1
2
2
1
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
1
1
1
1
1
1
1
1
2
1
1
2
1
1
1
1
1
1
1
1
4
1
1
1
1
1
1
8
48
5
22
7
11
7
57
37
52
42
6
6
4
9
39
27
31
70
4...

result: