QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#69233#5108. Prehistoric ProgramsrivalqAC ✓231ms46404kbC++142.5kb2022-12-25 18:02:272022-12-25 18:02:29

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-25 18:02:29]
  • 评测
  • 测评结果:AC
  • 用时:231ms
  • 内存:46404kb
  • [2022-12-25 18:02:27]
  • 提交

answer

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

#define rep(i,a,n)     for(int i=a;i<n;i++)
#define ll             long long
#define int            long long
#define pb             push_back
#define all(v)         v.begin(),v.end()
#define endl           "\n"
#define x              first
#define y              second
#define gcd(a,b)       __gcd(a,b)
#define mem1(a)        memset(a,-1,sizeof(a))
#define mem0(a)        memset(a,0,sizeof(a))
#define sz(a)          (int)a.size()
#define pii            pair<int,int>
#define hell           1000000007
#define elasped_time   1.0 * clock() / CLOCKS_PER_SEC



template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.x>>a.y;return in;}
template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.x<<" "<<a.y;return out;}
template<typename T,typename T1>T maxs(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T mins(T &a,T1 b){if(b<a)a=b;return a;}


int solve(){
 		int n; cin >> n;
 		vector<pair<int,pii>> vec1, vec2;
 		for(int i = 0; i < n; i++){
 			string s; cin >> s;
 			int bal = 0, mn = 0, mx = 0;
 			for(auto j: s){
 				if(j == '(') bal++;
 				else bal--;
 				mins(mn,bal);
 				maxs(mx,bal);
 			}
 			if(bal >= 0){
 				vec1.push_back({i,{bal,mn}});
 			}else{
 				reverse(all(s));
 				int tmp = 0, mn = 0;
 				for(auto j: s){
 					if(j == '(') tmp--;
	 				else tmp++;
	 				mins(mn,tmp);
 				}
 				vec2.push_back({i,{bal,mn}});
 			}
 		}
 		sort(all(vec1),[&](auto &a, auto &b){
 			return a.y.y > b.y.y;
 		});
 		sort(all(vec2),[&](auto &a, auto &b){
 			return a.y.y < b.y.y;
 		});
 		int sum = 0;
 		vector<int> ans;
 		for(auto [i,p]: vec1){
 			auto [bal,mn] = p;
 			if(sum + mn < 0){
 				cout << "impossible" << endl;
 				return 0;
 			} 
 			ans.push_back(i + 1);
 			sum += bal;
 		}
 		for(auto [i,p]: vec2){
 			auto [bal,mn] = p;
 			if(sum + mn < 0){
 				cout << "impossible" << endl;
 				return 0;
 			} 
 			ans.push_back(i + 1);
 			sum += bal;
 		}
 		if(sum != 0){
 			cout << "impossible" << endl;
 			return 0;
 		}
 		for(auto i: ans) cout << i << endl;
 return 0;
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #ifdef SIEVE
    sieve();
    #endif
    #ifdef NCR
    init();
    #endif
    int t=1;//cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
 

詳細信息

Test #1:

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

input:

50000
(
(
))))()))()(()))()()()))()(((((()(((()))()(((()))((()(())))))(()(
)
(
)
(((
(
(
(
(
(
()
(
)
(
)((())()((
)))))(
(
)
))
)()
(
)
)
)()(
(
(
()
(
)
(
)()((((())()))())(
(
(
)(
(
(
(()())())
)
)
(
(
(
)((())))((())))))))))((((()()))()))))))))((()())()))
)
)()
)
)
)
)
)
())(())))))()(()((()(())...

output:

31744
31767
31765
31764
31763
31759
31757
31755
31754
31753
31750
31747
31768
31743
31740
31738
31736
31734
31727
31726
31722
31721
31711
31710
31796
31818
31817
31815
31814
31812
31809
31806
31803
31801
31799
31798
31705
31795
31794
31793
31789
31787
31785
31784
31782
31777
31775
31634
31658
31656
...

result:

ok good plan

Test #2:

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

input:

1000
(
))(()))
((((())())))((())(()))(
)(
)
)))
))((()(((((((())()(())()())))(()(())()())))))))((()((()())()())(())))()((()())
)((()()()(())(()))()(())()))(()))))())))))))))))))()))(()()(())(()))())()()))))(())()()()((())(()))(())))))))(()()())()))()())))()()))))))(
)))(((
(
)))()()())))
(
(((())(((...

output:

554
576
575
573
570
566
564
563
562
561
560
557
577
553
544
535
534
524
522
517
516
514
511
502
619
655
653
652
650
646
640
638
636
632
628
626
498
617
615
611
604
598
596
595
590
585
584
387
422
420
414
410
408
406
399
398
397
396
390
426
386
384
382
381
379
377
372
371
356
347
345
460
496
489
481
...

result:

ok good plan

Test #3:

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

input:

2
()
()

output:

1
2

result:

ok good plan

Test #4:

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

input:

2
((
))

output:

1
2

result:

ok good plan

Test #5:

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

input:

2
)(
()

output:

impossible

result:

ok impossible

Test #6:

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

input:

3
()
(
)

output:

1
2
3

result:

ok good plan

Test #7:

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

input:

3
)(
(
)

output:

2
1
3

result:

ok good plan

Test #8:

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

input:

5
))(
(()
)(
(
)

output:

2
4
3
1
5

result:

ok good plan

Test #9:

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

input:

3
((
))())
(

output:

1
3
2

result:

ok good plan

Test #10:

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

input:

6
)
()
()()()
((
)
)

output:

impossible

result:

ok impossible

Test #11:

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

input:

500
(
)
)
(
)(
(
(
)
))(
(
(
(
(
)
)
(
(
)
(
(
)
(
()(()
(
)())
(
(
)
(
)()((
(
)
(
)
)
(
(
(
)
(
(
)
)
)(
(
(
)
)
(
)
(
(
(
)
(
(
())))
(
(
(
)
(
)
)
(
(
)
)
(
(
(
(
(
()
(
(
(
(
(
((
)
(
(
)
(
(
(
)
())
(
(
(
)
(
(
(
)
)
(
)
)
(
)
(
(
(
(
)
(
)
)
)
)
(
)
)))()(
(
)
)
(
)
)(
)
(
)
)
))
(
(
(
(
(
(
...

output:

334
290
296
297
304
308
309
311
315
318
320
321
325
327
329
330
288
338
339
340
343
344
345
348
349
350
351
353
356
357
360
362
262
232
234
239
1
241
242
243
247
248
249
251
253
254
256
258
366
264
265
268
269
271
274
275
277
282
283
284
285
286
287
467
434
435
436
437
438
439
440
442
443
445
449
45...

result:

ok good plan

Test #12:

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

input:

50
)
)
((((()())())))(())(())
()(((()))
(((()))(()
()(((
))
)
)()))(()(()())(((((()
(
)
)
)((
)()((
())()))
(())))()
(((
))))(()
()(())(()))())()
)
)
(
(
(
(
((())()())())))(((())
()(
(()(())()((()
()(((()())))())()(
)
)((()
(
)
((
)
()(
(
(
)
)))((())
)
()))()(((()(()
((
((()))(())(()())(()())())()...

output:

4
43
38
37
36
34
32
28
27
25
24
23
22
17
10
6
5
3
14
29
31
13
46
42
9
45
26
50
47
44
40
18
39
1
49
48
2
7
8
41
11
16
35
33
30
12
21
20
19
15

result:

ok good plan

Test #13:

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

input:

50
)
(
)()(
())(
()()(((((())(
)(())(()((())(()(()))(())())))))(())()))()())))))()(()()))(())))(()(((())(())()((())())()())(())())))()((()(()(())((()()))))()((((())()())((()))))((()()(())))))(()(())(()(()((())(()(())((()())))())(()))()())))()()((((()()((()()))((())())))()(())((()()((()((())())(()(()...

output:

15
33
40
28
26
41
2
18
16
13
11
8
5
46
47
19
42
44
37
10
4
3
29
21
6
31
23
12
30
50
49
48
45
43
39
38
36
35
34
32
1
27
25
24
22
20
17
14
9
7

result:

ok good plan

Test #14:

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

input:

150
))(()))(())(())))()))())()()()(())(((())))()))))()
)))()(()()(()((())())))(()(()(())((())))(((()(((())()()())))()())(((((((()))((())((())(())())(()))()(()()()()((((()))(()())))()(()((()(()(((((()((()())()))((((()))()))(()(((()()(((()(((()(((())(())())(()((()))))))()())((()(())())))((()()(()(((()...

output:

79
38
40
140
136
48
49
52
53
130
60
69
73
149
84
87
92
94
98
100
103
104
105
106
111
120
148
15
17
14
143
12
20
11
24
142
7
6
28
4
37
141
32
35
117
10
5
96
93
91
89
23
137
135
27
51
133
129
61
62
70
16
102
147
77
29
122
3
125
2
9
25
86
18
41
43
47
56
115
134
150
59
45
30
85
19
55
21
33
8
121
126
71
...

result:

ok good plan

Test #15:

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

input:

150
)))(
(()
(())((())))(()))()(()
((((()(((()))()(((((())()(()()((((()))((((()(())()(()))(()(())())(())(())))(((()))(())()))()((())((()(()(())())))))()(((()(()()())()))))()))(()(()()()(()(())()))))()))(((((())(()())((()()((((()))))(())())(())(())((()()(())))((((())((((()))()))()))))))))()())))))
(
...

output:

98
51
52
56
58
61
64
2
70
86
87
89
94
66
100
104
118
121
127
128
129
141
142
148
149
150
37
26
32
19
36
15
14
10
42
49
46
4
5
44
8
50
16
18
117
113
112
107
145
102
23
29
55
84
80
75
74
53
136
63
39
76
114
82
34
90
88
85
144
21
13
140
41
7
62
45
40
111
97
96
79
81
139
116
20
78
108
125
130
137
115
72...

result:

ok good plan

Test #16:

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

input:

150
)()((
)
)))())))
)()())((()(()())((())()))(()))(())((((((((()()(())())(()(((()))())()((()((())())))))))()((()))))((()(((()(((((()))()))((()((()()))(())))))()))))()())()()())(())(())(()))())((((((()()()))()((((()))))))((())()))()(()((()(())(())(())()())(())
()()
)
(())()))(())(()((())()()())())((...

output:

106
60
65
67
68
74
75
81
84
89
92
93
97
98
99
5
108
110
111
115
117
118
122
123
129
130
131
136
140
149
48
36
30
27
45
50
52
55
8
58
127
11
57
124
19
24
9
26
1
31
100
42
63
56
70
46
88
119
146
128
14
15
120
82
114
35
91
101
37
107
133
43
32
90
78
12
44
61
112
7
64
109
125
85
72
144
41
22
20
95
28
16...

result:

ok good plan

Test #17:

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

input:

750
(()()((()((((())()((()))()()))()))(()()(()))(()(())()))((((((
)))))))
)
((()()()(())((()(()())(())(((()((((()))(()(())((())(()())(())())))())))()(())()))((()(()((((()(()))(()())()((()()()))))(())())(())())())()((()(
)
)
(
)()(((()(())))()))))(((((((()))()()()(()())))(()())(()((
(
)
)(()))
((())(...

output:

437
470
469
468
461
455
450
446
442
441
440
473
434
432
429
427
426
425
419
418
417
495
530
526
522
518
516
512
504
502
500
414
494
492
491
490
489
485
481
477
475
348
378
374
371
369
368
362
361
360
358
357
379
345
343
341
338
335
333
332
331
330
395
409
408
407
406
405
401
400
397
396
541
394
392
...

result:

ok good plan

Test #18:

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

input:

100
)
)
)
(
)
(
))))()
)
(
(
(
(
)
)
)
)
(
(
(
(
())
(
)
)
)((
)
(
(
(
)
(
(
)
)
)
)
()((
(
)
)
)
)(((
((((
(
)
(
)
((
)
(
(
)
(
())(()))
)
)
(
)
(
(
(
(
)))()()
)
(
(
(
(
)
(
)
)
)
(
)
)
)
)
(
)
(
(
)
(
)
(
(
(
)
)
(
)
)
(
)((((
)
)
()((()()(()))))
)
(

output:

70
51
53
57
59
60
61
62
65
66
67
68
50
74
79
81
82
84
86
87
88
91
94
100
27
6
9
10
11
12
17
18
19
20
22
4
28
29
31
32
37
38
43
44
46
48
25
42
95
77
54
55
56
58
63
64
69
71
72
73
75
76
52
78
80
83
85
89
90
92
93
96
97
98
99
26
2
3
5
7
8
13
14
15
16
21
23
24
1
30
33
34
35
36
39
40
41
45
47
49

result:

ok good plan

Test #19:

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

input:

100
)
()(
(
)
(
)
(
(
)
)
)(()
)
)))
)
)
(
(
(
)
(
(
)
(
)
(
(
(
))(
(
(
))((
(
)
(
))())
)
(()
)
)
(
)
(
(
)
)
(
)
(
))
(
(
)
)
(
)
)
)
)
(
())
)
(
(
)
)
(
)
(
))
(
)
)
(
(
(((
(
(
(()
)
)()())(()((()((())
(
)
)
(
(
)
)
(
)
(
)
(
))(
)
(
(
(
)
(
(((())

output:

impossible

result:

ok impossible

Test #20:

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

input:

100
)
)
()))((((
))()
(
(
(
)
(
)
(
(
)
()
(
(
)
)
(
)
(
(
)
)
)
(
)
)
(
(
)
)
(
)
)
)
)
(
(
)
((
(
(
)
)
(
(
)
(
)
(()((
)
(
)
)
(()))()()())))()()((
(
)
)
(
(
(
)
)
(
(
)
(
(
(
)
(
(
)
)(
(
)
)
)
(
(())())(()
)
)
(
()
((
(
)
)
)
)
(
)
(
(
)
)
(
())
)(

output:

72
51
53
57
60
61
62
65
66
68
69
70
5
73
76
80
84
85
86
87
92
94
95
98
47
6
7
9
11
12
14
15
16
19
21
22
26
29
30
33
38
39
41
42
43
46
49
75
81
100
3
56
78
52
54
55
58
59
63
64
67
71
74
77
50
79
82
83
88
89
90
91
93
96
97
99
27
2
4
8
10
13
17
18
20
23
24
25
1
28
31
32
34
35
36
37
40
44
45
48

result:

ok good plan

Test #21:

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

input:

100
(
(
)
(
)
(
(
(
(
)
)
)
)
()
)(
)
)
(
(
)
(
(
)
)
)
(
)
(
(
))))
(
)
(
)
(
(
(
()()(
)
())
(
(
)
)
(
(
)
(
(
)
)
(
(
(
(
(
)
(
(
(((
)
)
)
))))
(
))(
)
)
()
())()
)
)
(
)))
(
)((()))(
(
(((
((
(
)
(
(
)
(
)
)
()
)()
)
)
()))()(
)(())(
)
(
(
(
(
)(
)

output:

75
49
52
53
54
55
56
58
59
60
65
69
73
2
77
78
79
80
82
83
85
88
95
96
97
98
26
6
7
4
8
9
14
1
18
19
21
22
48
28
29
31
33
35
36
37
38
41
42
45
46
99
93
15
76
92
66
74
57
61
62
63
64
67
68
70
71
72
51
81
84
86
87
89
90
91
94
100
25
5
10
11
12
13
16
17
20
23
24
3
27
30
32
34
39
40
43
44
47
50

result:

ok good plan

Test #22:

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

input:

1000
(())())()(((())()())(((()(()))((()((((()())))())))))(()(()((())(((()))()(()
)
(
)
()
)
)((()))))
)
((((((()))()())))))((()(
((
()(()())))(()
)()
(
((
(
)
)
)(()
)))(
)
))
(
(()))))
)(())(((())((((
)
)
(
(
())))(())
(((
(
(((
())()(
()())
)
)
)
(
))))())(
)
))(
)
())(()(()))))()(()((())((((()())...

output:

impossible

result:

ok impossible

Test #23:

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

input:

1000
))(()))
(
)))(
)
((
()))()))))()()(
))))((((((((()()(())((()()
(
)
)()(()
(
()))))()
(
(()(()(((()())(((((((())()()())())(())()))))((()((())((((((()(()()
)(()())((()))
(((
)
)
(
)((
(
(
)
(
)
()(())(((
(
)
(
(
)
()(()(()()(()()((()))())((()())))))((())(((()()(())(()()())(()()(((())()(()((((((((...

output:

impossible

result:

ok impossible

Test #24:

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

input:

4000
(
)
))
)()))))(
(
)
(
)
)
)
)((()((
(
)
)()(
)
)
)
)
(
)
(
)
)
(
()))((()))))()((()(
(
)))
(
)
(
(
(
(
)
)()(()()(()()))))())
)
)
)(((
)
)
)
)
(
(
)
))()()))((())
(
(
)
(
))(
(
)
)
(
)
)
())(
)
(
(
(
)
())))(())((()(()()((()((
(
)
)
(
)
)
)
)
)
)
)
)
(
)
(()))))(
)
)
(
())))(((())()(
(
(
()(
(
...

output:

impossible

result:

ok impossible

Test #25:

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

input:

1000000
)
(
)()(((()))(
(
(
(
)
(
(
)
)
(((())((()(()((())
(
)
)(
)
)
))))(()))()())(()((()))(()()()))()()()))))))))(())))((((()(()()))((((((()((((()()(
)
((
)
)
(
)
())()()((
)
)))(())((()))((()()))(()(())())))())))())))(()()(
(
()(
(
(
()()
)
))
)
(
(
(
)
)
)
(
)
(
)
)
)
)(()))()))
(
)
)))
(
)
(
(...

output:

641462
641493
641489
641488
641485
641484
641480
641479
641476
641474
641473
641471
641469
641465
641464
641494
641461
641460
641459
641456
641454
641453
641451
641448
641446
641445
641443
641441
641437
641436
641523
641555
641548
641547
641546
641545
641544
641542
641541
641536
641533
641532
641530...

result:

ok good plan

Test #26:

score: 0
Accepted
time: 42ms
memory: 19500kb

input:

1
((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

impossible

result:

ok impossible

Test #27:

score: 0
Accepted
time: 51ms
memory: 19428kb

input:

1
))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))...

output:

impossible

result:

ok impossible

Test #28:

score: 0
Accepted
time: 19ms
memory: 19468kb

input:

1
((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

1

result:

ok good plan

Test #29:

score: 0
Accepted
time: 41ms
memory: 19424kb

input:

1
((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

impossible

result:

ok impossible

Test #30:

score: 0
Accepted
time: 42ms
memory: 19504kb

input:

1
((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

impossible

result:

ok impossible

Test #31:

score: 0
Accepted
time: 21ms
memory: 14672kb

input:

2
))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))...

output:

2
1

result:

ok good plan

Test #32:

score: 0
Accepted
time: 18ms
memory: 14776kb

input:

2
)()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()(...

output:

impossible

result:

ok impossible

Test #33:

score: 0
Accepted
time: 25ms
memory: 19512kb

input:

3
)()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()(...

output:

3
1
2

result:

ok good plan

Test #34:

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

input:

1000000
((((((((((
((((((((((
((((((((((
((((((((((
((((((((((
((((((((((
((((((((((
((((((((((
((((((((((
((((((((((
((((((((((
((((((((((
((((((((((
((((((((((
((((((((((
((((((((((
((((((((((
((((((((((
((((((((((
((((((((((
((((((((((
((((((((((
((((((((((
((((((((((
((((((((((
((((((((((
((((((...

output:

impossible

result:

ok impossible

Test #35:

score: 0
Accepted
time: 112ms
memory: 27584kb

input:

1000000
))))))))))
))))))))))
))))))))))
))))))))))
))))))))))
))))))))))
))))))))))
))))))))))
))))))))))
))))))))))
))))))))))
))))))))))
))))))))))
))))))))))
))))))))))
))))))))))
))))))))))
))))))))))
))))))))))
))))))))))
))))))))))
))))))))))
))))))))))
))))))))))
))))))))))
))))))))))
))))))...

output:

impossible

result:

ok impossible

Test #36:

score: 0
Accepted
time: 124ms
memory: 42564kb

input:

1000000
))))))))))
((((((((((
))))))))))
((((((((((
))))))))))
((((((((((
))))))))))
((((((((((
))))))))))
((((((((((
))))))))))
((((((((((
))))))))))
((((((((((
))))))))))
((((((((((
))))))))))
((((((((((
))))))))))
((((((((((
))))))))))
((((((((((
))))))))))
((((((((((
))))))))))
((((((((((
))))))...

output:

666658
666688
666686
666684
666682
666680
666678
666676
666674
666672
666670
666668
666666
666664
666662
666660
666690
666656
666654
666652
666650
666648
666646
666644
666642
666640
666638
666636
666634
666632
666630
666720
666750
666748
666746
666744
666742
666740
666738
666736
666734
666732
666730...

result:

ok good plan

Test #37:

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

input:

999999
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)...

output:

833328
833343
833342
833341
833340
833339
833338
833337
833336
833335
833334
833333
833332
833331
833330
833329
833344
833327
833326
833325
833324
833323
833322
833321
833320
833319
833318
833317
833316
833315
833314
833359
833374
833373
833372
833371
833370
833369
833368
833367
833366
833365
833364...

result:

ok good plan

Test #38:

score: 0
Accepted
time: 231ms
memory: 42408kb

input:

1000000
)(
()(()))()((
)())
)()((((((
((((
))))))))()())((()(
)((
)())
))()((()
()
(
)(
()(
(((()((()())(()))(((())(((
)()()
)))(
(((
(()(()(())))(())))(((((
())())((()))(
(())
(()
()))(()(())()())(
())((
)))))))))
())()((())))(
()())((((()())()
((
()())
()((())
)()))))))))()())()))())
()())
)()())
...

output:

792159
360775
792142
360773
792148
792149
792150
792153
792154
575472
360779
360759
360756
360755
360754
360752
360751
575473
360746
360791
360812
360810
669464
360806
360805
360802
792137
360795
360793
575474
360789
669463
360787
792140
360785
792141
360783
360782
792196
360713
792181
792182
792184...

result:

ok good plan

Test #39:

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

input:

1000000
)()))))(()(((()
()((((()))
)())
)
()()(
()
())()((())))))())()(())(())
())))()())((
)()()((()((())
)
)()(
()()(
((())((
)(
(
)((()((()((()(())(()())
))()
())
()()()
(())
))()(()(()()()()((
(())))()((((()()(
(())
)())((()))
))(()
()()()(()(()()((((())))((())))(()()(()))))
(()()))()(())))()))(...

output:

564089
564128
564127
564119
564115
564114
564113
564111
564109
564106
564103
564102
564096
564135
564086
564082
564078
564077
564076
564071
564070
564069
564066
564061
564060
564163
564190
564187
564182
564181
564180
564179
564175
564174
564173
564172
564168
564059
564161
564160
564159
564156
564155...

result:

ok good plan

Test #40:

score: 0
Accepted
time: 32ms
memory: 3712kb

input:

564
)())((())((()))))(()())((((()()(()(()))(()((((()()))(((()))(()()()(()((()()()()((()))))((())))()(()((())(()())))))))())))(((())()()()))))()((((()()))()(()()())))(()()(())((())((()())(()()())()(((()))()())())))(((()(((((()())()())))()()((())))()()()(()()))()(()()()(((())())))(()(()(()((())()((()(...

output:

305
287
163
542
253
358
108
360
367
105
236
537
469
307
93
95
541
329
65
528
243
17
563
359
267
513
100
465
445
356
75
134
514
113
26
302
44
547
265
555
281
54
405
531
342
340
286
153
139
133
451
301
421
350
11
52
483
408
463
32
255
24
299
330
553
529
235
533
81
510
223
443
43
373
137
552
327
190
49...

result:

ok good plan

Test #41:

score: 0
Accepted
time: 36ms
memory: 4136kb

input:

109
)(()((())()(())())))))((()(((()((()()())))()))()()()()))(()(()()((()()())())()))())(((()()))(()))))(()((()((()()(((()))()((((()(()()()(()))))))))())((())(())()((()))))((())()()())))))(())))())()())))())()(()))))(())()(((()((((()))))((()())()())())))())((()(()())()())((((()()(()((()))(())((()((()...

output:

48
12
75
7
81
36
33
76
99
16
10
105
59
108
70
22
15
5
69
87
9
55
84
3
66
80
78
39
8
46
21
96
95
53
51
6
62
64
13
23
97
27
52
65
28
68
88
2
31
1
34
19
25
32
4
77
100
30
11
86
20
14
50
35
73
67
47
58
56
94
26
103
91
17
54
101
107
109
93
63
82
24
92
57
98
60
40
79
41
71
102
106
74
37
18
104
49
42
38
83...

result:

ok good plan

Test #42:

score: 0
Accepted
time: 33ms
memory: 5532kb

input:

64026
)()()()))((())((()(())())(()()())))(())))()))()(((())())))()))(()(()())((())((()(()))))()))())()(()(()))))())))(()()()()(((((()()()))))))((((()(()(())()))((()))))()())())(()(((()))))()))())))(()()()(())))((((())(())())(()()))()))))(())))()(((())()()()())()))))(())()(()(((())(()()()()((()()((()...

output:

32512
32421
32424
32434
32437
11636
56817
56814
11623
11622
32474
11617
32493
56807
32500
32509
11645
32519
32534
32535
32542
11587
11585
56801
32559
32568
32569
11571
32571
32573
11562
32574
11690
11730
61472
32262
32265
11719
32268
11714
32281
11712
32283
56844
61481
32299
32310
32314
11559
32322
...

result:

ok good plan

Test #43:

score: 0
Accepted
time: 150ms
memory: 34304kb

input:

741507
)))((())))))()))(()()())((()((
))())
()
)(((()))()((()()(()())(())(((
(()))())()))))((
))(
)()
((()((()()()))(
(()(
(()())())(
)
)
(((()()(()(
()()(((
)(())))((((()((()()))))(()())(()))())((()((()((((()))()()(
()))
())())())))(()))(
())))()(
)(
(())()()())()())()((()))(
(())
)))()()
)
)(())()...

output:

554281
554302
281615
554297
281618
281621
554295
281623
281630
281632
554289
281639
554283
281643
281610
554280
554279
281651
281655
281660
554275
554269
281665
281666
554267
281669
554260
281671
554333
281546
554377
554375
281550
554363
554359
554356
554355
554353
554346
554344
281576
554337
554254...

result:

ok good plan

Test #44:

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

input:

32
())((())(()(((())())()())((())(()(((((((()))()(())))))())(())))((())((((()))(()(()(()(()))()(())())((()())(()((((((()(()(()()(()))()(())(()(()()))()())))()((()()(()(())))((()(()(()))))())()()(())(())(())()))(((()((((()())(()()()()()())()())())((()(()(()()
()
()))()()()(()())()((())))()((()()(()()...

output:

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

result:

ok good plan

Test #45:

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

input:

8
())(()()))))()(()))))()()(()()(())))((())))))(((())))))())((((()))((()))((())))()()))()(())(()(()()()(()())()(()((())()))(((((()(((()((()()((()()(())(()())()((()))))())()())(()))())(((((((()())(())))(()))))(())(())(()))))))(()(((()((()((((()))(()(((()))()))()())(((()))(((())(())))))(((())()()()))(...

output:

6
3
7
2
1
4
5
8

result:

ok good plan

Test #46:

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

input:

32
()))()(()))()()()()()(())((()()(()))(()
(()())())()))()(())())))()(()())()((()(()(()))()(()((((((((()))()))))((((())()))()((((()))((())()(()(()((()()()))))()()())()()((()(()()(((()))()))((()(()()(((()((())((((((((()())()(((()(()))(
)))()()()((())()()
())))((()))(()(((()((()()()))(()
)((()))))()))...

output:

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

result:

ok good plan

Test #47:

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

input:

53
))(((((())))))))((()()())()))())())())())(())())(())())(((()((()())(()(())))())(((
()()))((())))()))()(())))()))()(()(())))((())((((((()))()(()))))))))((()))))))))((())()))(()))())()()(()))()())()())())()(())(((()(
)())
()))))()))()(()()))()))(()((((()))(()))())(((()))(()()()))(())))(())))()(((((...

output:

27
52
44
40
38
36
30
29
25
24
19
18
17
14
7
13
12
22
5
32
41
37
42
47
11
15
4
21
26
31
1
49
33
2
50
16
53
46
45
43
39
28
10
23
8
6
51
34
35
20
9
48
3

result:

ok good plan

Test #48:

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

input:

25
)()((()())()))())))(((())))(())(()))))(()(()))((()()())(()((()())))(())())())())((()((()()(())))))))()((())())(()()(()()()())()())(()((()())(((())))()))(())()()()()((()))()(((())(())())((()((()))))(()(((()(())()()(((()))(()())(()))((())()))()))())(((()))))()()()((())((())()))()(())()(((((()())(((...

output:

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

result:

ok good plan

Test #49:

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

input:

90
))))((()()()))())))(
()())((((())))()))((())()()))))())(()()()(()))())))))((())())))()))(()())((())()(())))((((()(()()()())))()()))()(()())))())(((
))))())))()))))()((()(())(()((())(())()(()())))))()((()))((()()(()())()((()())((()()(()()(())())())()()(()))((()((()()(()()(()((()()()()))(())))))())...

output:

6
83
79
62
50
45
44
43
36
33
24
23
21
15
63
60
77
56
18
42
4
84
19
34
90
39
78
12
52
53
31
30
27
59
61
70
54
40
37
9
86
87
76
22
7
14
57
74
49
81
8
75
16
80
73
51
35
89
69
2
88
72
66
3
20
46
65
28
5
1
13
11
55
48
47
41
82
85
10
25
17
71
68
67
32
64
58
26
38
29

result:

ok good plan

Test #50:

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

input:

16
))))))(((()(())()()(()((()()((())(()()(())))((())))))))(())(()))()((())((()(()()))())((())))()()()((()()))(((()()))()()))))()())))()))(((((()))(()()((()(()()()((((((()()(((((()(())))())()(())()())()(()(())()))()()()))(()(()))(())))(()))(((())))((((((()))(()((((())()())()(())()))()))(())()))))())(...

output:

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

result:

ok good plan

Test #51:

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

input:

28
(())((()(()
(()))())()()()()(())()()(()
(()()))()))()))()((()()()()))()((()))))))())))(()))))(())())()()(()(((((((()((())))(()))(())))())(((())))))))))))))))))))))))))))))))))))))))))))))))
)())())((((()((()()(()(()
)(()()((()((())((()()))())
(((()((((()())((((()())(())))())(()))))))((())()))))()...

output:

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

result:

ok good plan

Test #52:

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

input:

14
))(())()((((()((()((()(()))))())))((()()((())(((()))(())))((())(())(()(()(())(
(()()())(()(())(()()))))))))())())()))())))())()(()))())))())(((())()(((((()())(()())()(()
()))))()((()()()(()())(())()(((()))()())((((()(()()())))(()))(()()()())(())())())))()))((()())()))(((((()()((()(()))()()))()()(...

output:

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

result:

ok good plan

Test #53:

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

input:

3711
(
)(
)(
(
)(()
((
(
(
))
(
))())
(
)((
)
)
))))
)
)
(
)
((
(
)((
()
(
(
()))
()(()
)(()((
)
(
)
)((
)))))
(
)(
)(((
)((((((
)
((
()()()(((
)
)()
)(
)()())
(
((
(((
)
(
)(
)
)(
((
)(()
)
(
(()())))))(
(
(
()(
())
(
)((
)
()(
)
)((
()
(
)
)())
)(
()(
)(
)
)))))(
)(
(
()()
(
)))(((
)
)(()()(
(
(()...

output:

2283
2328
2326
2320
2317
2316
2307
2306
2305
2298
2297
2293
2291
2288
2284
2330
2282
2278
2276
2274
2273
2271
2270
2269
2268
2266
2264
2263
2262
2259
2363
2400
2396
2394
2393
2392
2390
2387
2384
2383
2381
2380
2374
2368
2367
2257
2355
2354
2353
2350
2345
2343
2342
2341
2340
2339
2338
2336
2335
2178
...

result:

ok good plan

Test #54:

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

input:

7863
(
)
)
)
)
))
(
(
(
)
)
(
(
)
((
(
)
)
(
(
)
(
(
(
)
(
)
)
)
)
(
)
(
)
)
)
(
(
)
)
)
)
(
((
(
)
((
(
)
))
(
)
((
(
)
(
)
(
(
(
(
(
)
)
(
)
(
()
)
)
(
(
)
)
(
)
)
(
(
)
)
)
(
)
))
(
)
)
)
)
(
(
(
(
(
(
)
(
(
)
)
(
)
(
(
)
(
(
()
)
(
)
)
)
(
(
)
)
)
(
((
(
)
)(
()
)
)
)(
(
)
)
)
)
(
)
(
(
)
(
(
)
...

output:

5152
5121
5122
5123
5124
5125
5126
5128
5131
5137
5138
5139
5140
5144
5146
5149
5120
5153
5155
5160
5161
5164
5165
5167
5171
5172
5176
5178
5179
5180
5185
5186
5078
5046
5049
5052
5053
5057
5058
5060
5061
5063
5069
5071
5072
5073
5074
5075
5190
5082
5084
5085
5086
5088
5092
5101
5103
5104
5106
5107
...

result:

ok good plan

Test #55:

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

input:

2272
)
)
(
)
)
(()()
(
))()((()((
)
()(
))
))
(
)((
()
)(((
(()))()
))(((((
)
)
)()((((
(()(((
)())()
()(()
)(
)()(((
()
(((
))
))
()
(
(
()
)
(
(
(
((((()()((()
((
)
(
)
)((
)((
)((
((
((
(
((
(
())
)
(
()
(
)()(())
)
())(
(())()
(())((
))
)()()())
(()))(
()
(
)(
())
())()((
)((
))
((((
(()(
))()()...

output:

1393
1412
1411
1410
1403
1402
1401
1397
1394
1413
1391
1389
1387
1386
1385
1384
1383
1382
1430
1448
1442
1440
1439
1438
1436
1433
1431
1377
1429
1428
1426
1425
1423
1420
1414
1318
1342
1341
1339
1337
1331
1329
1320
1319
1347
1315
1313
1312
1310
1306
1302
1301
1300
1359
1374
1373
1372
1368
1367
1363
...

result:

ok good plan

Test #56:

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

input:

4127
)
)(
)
(
)
)
()(
)
)(
(
)
))
)())
((
((
)()(
(
(
(
)
)
((())
(
(
(
)(
)((
)((
)()
)
))
(
(
)
(
)
)
(
(
)
((
((
()
(
())
(
(
))
(
(
(
(
()
)
())
)(
))
)
(
))
)(
)
(((
(
)
)
(
()
)(
)
(
(
(
)
(
((
(
)))
(
(
)(
(((
)(
())
)
()
)
)
)
)
()((
()
)()
(
(
(
(
(
)
)(
(
)()
)
)
(
(
()(((
()
))
((
()
)
)
...

output:

2638
2622
2623
2624
2625
2628
2629
2634
2637
2616
2639
2640
2642
2643
2644
2645
2647
2599
2587
2588
2589
2590
2591
2594
2597
2598
2648
2600
2603
2605
2606
2608
2611
2615
2700
2683
2684
2686
2691
2693
2694
2696
2698
2682
2701
2703
2705
2706
2714
2715
2716
2586
2679
2677
2676
2671
2670
2669
2663
2660
...

result:

ok good plan

Test #57:

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

input:

5314
)
)
((
(
(
)
)()
)
(
)
)))
(((()(
)
()(
())
)
(
(
()
)))
)
)(
()
(
(
()(
(
(
))
(())
)((
))
(
))
)(
(
(
(
(((
(
((
(
)
(
((
(
)
))(
)
))
(
)
))(
(
(
)))
))
(
)(
(
(((
)))
(())((
)(
())(
(
()
()
(
(
(
)(
)
(
)
)
))
(()
)()
()
(
(
(
())
()(
)
(
)
(
(
(
(
)
)(
)()(
)
)
)(
)
)
(
(
)(
((
)()
))
)
(
...

output:

3062
3039
3042
3043
3045
4801
4797
3052
3060
4796
4806
4793
3064
3066
3067
3069
3072
3073
3074
4792
3021
3011
3012
4808
3014
3015
3016
3017
3019
4807
3078
3023
3024
3026
3028
3030
3031
3032
3033
3035
4780
4785
3120
3121
3122
4783
3124
3125
4781
3131
4787
4778
3136
3137
3141
3143
3144
4777
3149
3150
...

result:

ok good plan

Test #58:

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

input:

3465
(
)
)
(()
(
)()
(
(
)
)
)((
)((
(
)
)))
((
)
)
)(()
(
((
)
)(
(((((
(
)
(
))(
(
(()
))()(
)
))
(
(
(
))
)(
(
((
(
(
)
)
(
)
)
(
)
())
(
(
((
)
)(
)
(
)
)()((
(
)(
)))
(
)
)
(((
)
))(
()
)))
)))
(
(
)
)
)
)()))
)
((
(((()
)
)
)
)
(
))(
)
(
)
)
))(()((
()
)))
(
(
(
)
)(
(
)((((
)()
)
)
(
))((
())...

output:

2174
2203
2202
2201
2200
2199
2197
2195
2194
2193
2187
2181
2179
2176
2175
2204
2171
2168
2167
2166
2165
2163
2161
2160
2158
2151
2148
2142
2140
2229
2255
2251
2250
2248
2246
2243
2241
2238
2237
2236
2233
2232
2230
2137
2227
2223
2222
2221
2220
2219
2218
2217
2216
2214
2213
2207
2206
2038
2066
2062
...

result:

ok good plan

Test #59:

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

input:

3992
)())(()(
((
))
((())
(())
)()
)
()(
(
)
(
((
(
)()
(
()))
)((
())
(
)
()
(
(()))
)(
((
(
)
(())(
((
))
((
)
)
)
)
())
(
(((
(
()
)
()))(()
(
)(
))
(
(()(
()
(
)
()))
)(
)(
())))(
)())
(
))
(
(((
)
))
(
(
)((
()
)
(((
)
(
))
)
()
(
)
(
(((((
(
)
((()()((())
))
(
()()
)(
(
)(
)(
(
(
)
)(())(
)(((...

output:

2471
2505
2504
2501
2499
2498
2494
2490
2489
2487
2484
2478
2477
2476
2473
2472
2510
2469
2465
2462
2459
2458
2451
2447
2446
2445
2440
2436
2434
2431
2430
2428
2553
2581
2577
2576
2575
2574
2571
2570
2569
2568
2564
2562
2560
2558
2557
2555
2424
2551
2550
2549
2547
2542
2537
2534
2528
2524
2522
2520
...

result:

ok good plan

Test #60:

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

input:

127
)))()())))))))()((
))((()(((
))(()((())))((()()(((()(()(()(()()(((())(())())(())
)()((())()(())))()))())()(()()))
))((()())((((((
()()()((
(())(()((()((()(()))())(((())())())))())(()(
)(()))))()))()(((()(()()()()()()))(
)((())())
()(()()(()(())))())())))))))
)()))()(())())()))))())
((()))))))()(...

output:

125
73
69
68
66
95
97
98
102
105
106
110
122
22
6
7
34
84
77
86
87
71
94
65
14
56
55
18
113
112
107
36
35
27
96
118
91
90
72
3
78
74
2
5
40
44
124
28
103
63
70
64
93
83
75
23
80
100
61
67
45
43
119
120
42
13
24
88
41
114
54
53
19
85
32
104
21
17
59
60
8
57
99
49
101
81
1
30
26
37
12
62
126
82
46
31
...

result:

ok good plan

Test #61:

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

input:

7074
(
(
)
(
(
(
(
)
)
)
(
)
)
(
)
)
(
(
(
(
)
(
)
)
)
(
(
)
)
))
(
(
)
)
(
(
(
(
(
(
(
)
)
)
)
(
)
(
)
(
)
)
(
)
(
)
()
)
(
)
(
)
(
(
(
)
)
)
(
)
(
(
)
)
)
(
)
(
(
)
)
(
(
(
(
)
)
)
((
)
(
()
)
)
)
)
(
(
(
)
(
)
((
)
)
)
(
(
(
(
(
)
)
(
(
(
(
)
)
(
(
(
(
(
)
(
)
(
)
)
(
)
(
(
(
(
(
(
)
)
(
)
)
)
)
...

output:

4692
4659
4662
4664
4668
4669
4672
4677
4680
4681
4682
4683
4685
4690
4654
4694
4696
4698
4700
4703
4704
4706
4709
4715
4716
4721
4723
4724
4626
4606
4608
4609
4610
4611
4612
4613
4619
4620
4621
4622
4623
4625
4728
4628
4630
4631
4632
4634
4637
4638
4640
4644
4645
4646
4650
4651
4810
4786
4788
4790
...

result:

ok good plan

Test #62:

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

input:

61
)
)
(
)
)
((
)
)
)
)
(
(
(
)(
))
(
(
(
))
()
)
)
)(
(
(
()
)
(
(
((
(
)(((
()(
(
(
))
)
))
)
(
))
)
(
(
(
(
)()
)
)
(
(
()
(
)
)()
)
(
)
(
(
))(

output:

46
3
33
34
35
40
43
44
45
31
50
51
52
53
57
59
60
20
6
11
12
13
16
17
18
30
24
25
26
28
29
23
14
32
61
36
58
56
55
54
49
48
47
42
41
39
38
37
1
27
22
21
19
15
10
9
8
7
5
4
2

result:

ok good plan

Test #63:

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

input:

11
))()()(
))
(
(
(()
(()
)(()())((
)))()((
(())
())((
))

output:

3
4
5
6
9
7
10
8
1
2
11

result:

ok good plan

Test #64:

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

input:

86
)
)
)
)
(
)
)
)
((
)
(
)
)
(
)
)
)
((
)
)
)
)
)
)
)
)
(
)
)
(
(
)
)
(
)
)
(
(
(
)
(
(
)
(
)
)
(
(
(
)
(
(
)
(
)
(
(
)
)
(
(
(
)
(
()
(
(
)
(
(
(
(
)
(
)
(
(
()
(
(
)
(
)
(
(
)

output:

71
57
60
61
62
64
65
66
67
69
70
56
72
74
76
77
78
79
80
82
84
85
39
9
11
14
18
27
30
31
34
37
38
5
41
42
44
47
48
49
51
52
54
53
29
32
33
35
36
40
43
45
46
50
28
55
58
59
63
68
73
75
81
83
86
16
2
3
4
6
7
8
10
12
13
15
1
17
19
20
21
22
23
24
25
26

result:

ok good plan

Test #65:

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

input:

45
)
)
((
)
)
(
)
(
(
)
(
)
)
((
))
(
)
(
)
((
(
(
))
((
)
)
)
(
)
)
)
(
(
(
(
)
)(
(
)
)
)
(
(
(
)

output:

24
44
43
42
38
35
34
33
32
28
3
22
21
20
18
16
14
11
9
8
6
37
23
45
41
40
39
36
31
30
29
27
26
25
1
19
17
15
13
12
10
7
5
4
2

result:

ok good plan

Test #66:

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

input:

20
((
)
)))
(
)((
)
(
((()()
(
)(()
(
(
)))
))
))
()(
(
((
())))
(

output:

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

result:

ok good plan

Test #67:

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

input:

10
((
(
)
))
)
)
(
(
)
(

output:

1
2
7
8
10
3
4
5
6
9

result:

ok good plan

Test #68:

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

input:

14
)()((())(()
(())
)(()(())((()())
())((())(()()(((())
()(()
)(
))(((
))
(((())
(())
)))))
)
()))(()(()
())

output:

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

result:

ok good plan

Test #69:

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

input:

3
())(())()()(
(()
((())))

output:

2
1
3

result:

ok good plan

Test #70:

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

input:

1
(

output:

impossible

result:

ok impossible

Test #71:

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

input:

1
)

output:

impossible

result:

ok impossible

Test #72:

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

input:

1
)(

output:

impossible

result:

ok impossible

Test #73:

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

input:

1
()

output:

1

result:

ok good plan

Test #74:

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

input:

2
(
)

output:

1
2

result:

ok good plan

Test #75:

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

input:

2
)
(

output:

2
1

result:

ok good plan

Test #76:

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

input:

6
()
)(
((
))
(()
())

output:

1
3
5
2
4
6

result:

ok good plan

Extra Test:

score: 0
Extra Test Passed