QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#225923#5108. Prehistoric Programsb05704085AC ✓403ms33288kbC++233.0kb2023-10-25 11:54:292023-10-25 11:54:29

Judging History

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

  • [2023-10-25 11:54:29]
  • 评测
  • 测评结果:AC
  • 用时:403ms
  • 内存:33288kb
  • [2023-10-25 11:54:29]
  • 提交

answer

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

int main() {
    int n;
    std::string in;
    std::vector<std::pair<std::pair<int, int>, int>> opening, closing; // {{lowest, openness}, index}
    std::cin >> n;
    for (int i = 0; i < n; i++) {
        std::cin >> in;
        int lowest = 0, openness = 0;
        for (auto c: in) {
            if (c == '(') openness++;
            if (c == ')') openness--;
            lowest = std::min(lowest, openness);
            // lowest is the... lowest openness of the tablet sequence.
            // This directly determines whether this tablet can fit in the sequence.
            // For example, if the sequence is (, the ))(( won't work, because its lowest is -3, which is less
            // than the current openness, so the parenthesis closes more than it opened. That is illegal.
        }
        // for tablets that increases the "openness", we take the ones with the tallest lowest point first,
        // for the best chance of being in the solution
        // the actual order of these tablets don't really matter, as it will always increase the openness
        // secondarily, we want the tablets that opens the sequence more first, so big total values first
        if (openness > 0)
            opening.emplace_back(std::make_pair(lowest, openness), i + 1);
            // for tablets that decreases, we start from the end and work our way back, exactly like the open ones
            // but in reverse
        else {
            lowest = 0, openness = 0;
            std::reverse(in.begin(), in.end());
            for (auto c: in) {
                if (c == '(') openness--;
                if (c == ')') openness++;
                lowest = std::min(lowest, openness);
            }
            closing.emplace_back(std::make_pair(lowest, openness), i + 1);
        }
    }
    std::sort(opening.begin(), opening.end(), std::greater<>());
    std::sort(closing.begin(), closing.end(), std::greater<>());
    std::vector<int> solutionOpen;
    std::vector<int> solutionClose;
    int openness = 0;
    for (auto& i: opening) {
        if (openness + i.first.first < 0) { // the sequence closes too much
            std::cout << "impossible\n";
            return 0;
        }
        solutionOpen.emplace_back(i.second);
        openness += i.first.second;
    }
    int openingOpenness = openness;
    openness = 0;
    for (auto& i: closing) {
        if (openness + i.first.first < 0) { // the sequence closes too much
            std::cout << "impossible\n";
            return 0;
        }
        solutionClose.emplace_back(i.second);
        openness += i.first.second;
    }
    if (openness == openingOpenness) { // perfecto!
        std::reverse(solutionClose.begin(), solutionClose.end());
        for (auto& t: solutionOpen)
            std::cout << t << "\n";
        for (auto& t: solutionClose)
            std::cout << t << "\n";
    } else // the sequence is broken
        std::cout << "impossible\n";
    return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 15ms
memory: 4160kb

input:

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

output:

41248
4238
13809
27609
5338
48374
2458
389
48749
6754
42979
18533
14096
6986
32583
31692
23456
5803
3405
169
43508
38930
34539
26695
26677
10427
9225
46429
46194
41740
39743
35132
30771
25061
24373
21764
11398
2253
45491
35039
34110
33777
31402
23312
5699
41641
41639
39389
35743
28794
23551
9790
736...

result:

ok good plan

Test #2:

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

input:

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

output:

36
13
66
386
966
585
286
257
127
83
39
595
476
907
814
598
329
214
981
427
62
707
662
384
131
807
793
511
869
767
638
449
379
271
80
746
632
474
422
387
327
239
20
989
975
919
915
715
553
535
502
473
345
334
296
171
168
88
31
947
945
929
881
872
863
859
852
827
820
819
799
778
774
738
731
725
686
66...

result:

ok good plan

Test #3:

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

input:

2
()
()

output:

1
2

result:

ok good plan

Test #4:

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

input:

2
((
))

output:

1
2

result:

ok good plan

Test #5:

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

input:

2
)(
()

output:

impossible

result:

ok impossible

Test #6:

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

input:

3
()
(
)

output:

2
1
3

result:

ok good plan

Test #7:

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

input:

3
)(
(
)

output:

2
1
3

result:

ok good plan

Test #8:

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

input:

5
))(
(()
)(
(
)

output:

4
2
3
1
5

result:

ok good plan

Test #9:

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

input:

3
((
))())
(

output:

1
3
2

result:

ok good plan

Test #10:

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

input:

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

output:

impossible

result:

ok impossible

Test #11:

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

input:

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

output:

479
329
311
483
443
232
199
414
357
350
297
265
253
211
177
80
496
495
494
492
491
489
487
486
480
476
474
472
467
464
459
456
452
449
445
442
440
439
437
436
435
434
431
429
428
427
426
424
420
416
415
413
412
411
410
409
406
405
404
399
398
395
393
392
388
381
378
373
370
368
367
366
362
360
356
3...

result:

ok good plan

Test #12:

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

input:

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

output:

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

result:

ok good plan

Test #13:

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

input:

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

output:

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

result:

ok good plan

Test #14:

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

input:

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

output:

17
105
142
98
24
12
120
148
28
7
106
87
84
69
60
38
14
11
149
143
141
140
111
104
100
94
92
79
73
52
49
40
37
35
32
15
6
4
93
89
61
135
91
62
23
70
51
27
133
16
10
102
29
147
77
125
25
2
3
9
122
56
18
47
43
86
150
134
59
30
45
19
21
55
33
8
121
126
71
85
57
95
72
88
124
50
146
41
115
132
110
76
139
...

result:

ok good plan

Test #15:

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

input:

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

output:

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

result:

ok good plan

Test #16:

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

input:

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

output:

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

result:

ok good plan

Test #17:

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

input:

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

output:

468
163
390
379
204
396
707
590
585
122
4
1
658
657
601
405
274
180
104
79
34
473
158
730
705
681
571
547
526
504
485
269
149
108
25
606
530
494
481
426
418
408
406
395
382
341
246
230
218
166
164
156
131
103
56
55
43
41
749
745
743
738
736
726
725
723
722
721
719
717
712
709
699
698
697
690
684
680...

result:

ok good plan

Test #18:

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

input:

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

output:

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

result:

ok good plan

Test #19:

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

input:

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

output:

impossible

result:

ok impossible

Test #20:

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

input:

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

output:

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

result:

ok good plan

Test #21:

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

input:

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

output:

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

result:

ok good plan

Test #22:

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

input:

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

output:

impossible

result:

ok impossible

Test #23:

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

input:

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

output:

impossible

result:

ok impossible

Test #24:

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

input:

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

output:

impossible

result:

ok impossible

Test #25:

score: 0
Accepted
time: 321ms
memory: 25672kb

input:

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

output:

149392
264227
387984
770337
898404
995820
83071
269214
349084
897909
857929
731069
604894
385160
174818
196234
765299
352796
904916
760108
134097
708004
526593
308325
992894
911588
748267
675083
592970
540367
501576
489285
309146
900795
474263
342091
197429
160328
619800
610823
507757
475916
267140
...

result:

ok good plan

Test #26:

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

input:

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

output:

impossible

result:

ok impossible

Test #27:

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

input:

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

output:

impossible

result:

ok impossible

Test #28:

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

input:

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

output:

1

result:

ok good plan

Test #29:

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

input:

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

output:

impossible

result:

ok impossible

Test #30:

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

input:

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

output:

impossible

result:

ok impossible

Test #31:

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

input:

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

output:

2
1

result:

ok good plan

Test #32:

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

input:

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

output:

impossible

result:

ok impossible

Test #33:

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

input:

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

output:

3
1
2

result:

ok good plan

Test #34:

score: 0
Accepted
time: 214ms
memory: 22908kb

input:

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

output:

impossible

result:

ok impossible

Test #35:

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

input:

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

output:

impossible

result:

ok impossible

Test #36:

score: 0
Accepted
time: 257ms
memory: 21112kb

input:

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

output:

1000000
999998
999996
999994
999992
999990
999988
999986
999984
999982
999980
999978
999976
999974
999972
999970
999968
999966
999964
999962
999960
999958
999956
999954
999952
999950
999948
999946
999944
999942
999940
999938
999936
999934
999932
999930
999928
999926
999924
999922
999920
999918
99991...

result:

ok good plan

Test #37:

score: 0
Accepted
time: 293ms
memory: 33288kb

input:

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

output:

999999
999998
999997
999996
999995
999994
999993
999992
999991
999990
999989
999988
999987
999986
999985
999984
999983
999982
999981
999980
999979
999978
999977
999976
999975
999974
999973
999972
999971
999970
999969
999968
999967
999966
999965
999964
999963
999962
999961
999960
999959
999958
999957...

result:

ok good plan

Test #38:

score: 0
Accepted
time: 403ms
memory: 25228kb

input:

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

output:

510441
164663
944202
483356
500584
889056
879218
763948
732016
679768
637097
496501
183559
163748
90286
924596
911154
629235
590693
428626
321244
970762
651410
598737
480176
475331
378339
323909
295142
261112
67591
947844
897141
880821
850025
766848
740159
553153
491924
480934
451519
354542
235797
1...

result:

ok good plan

Test #39:

score: 0
Accepted
time: 403ms
memory: 24316kb

input:

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

output:

568499
250826
675014
629151
494698
985988
795023
536620
425960
926090
561779
463859
300744
106383
689231
597972
575206
137311
963161
930603
746420
427235
388609
353729
333208
207485
129338
997127
905927
834142
770416
696104
623824
487205
470327
123122
116108
902316
858526
836351
713994
665997
580640...

result:

ok good plan

Test #40:

score: 0
Accepted
time: 149ms
memory: 3644kb

input:

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

output:

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

result:

ok good plan

Test #41:

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

input:

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

output:

12
48
75
7
81
36
33
76
99
16
10
105
59
108
22
5
15
69
87
9
55
84
3
66
80
78
39
8
46
21
95
96
53
51
6
62
64
13
23
97
27
52
65
28
68
2
31
1
34
19
25
32
4
77
100
30
11
86
20
14
50
73
35
67
47
88
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
37
74
18
104
49
70
42
38
83...

result:

ok good plan

Test #42:

score: 0
Accepted
time: 163ms
memory: 4580kb

input:

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

output:

51373
43701
17030
24272
1485
42660
5483
27238
63066
16598
56433
63470
16623
40015
36141
17061
14019
45353
14405
34448
25754
9742
9313
13709
13231
56930
27954
25751
64001
63327
53450
30549
29121
10165
9388
1889
48613
17456
12907
9834
5582
50885
23130
12456
11895
44572
39672
25948
17043
38775
26319
13...

result:

ok good plan

Test #43:

score: 0
Accepted
time: 344ms
memory: 18040kb

input:

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

output:

504790
204843
343862
42954
399438
562227
498212
118929
63131
85220
400919
386793
329734
235660
87230
678888
616123
607247
323865
298959
121461
53936
25279
723227
701764
665377
538238
485491
430469
422036
417795
382031
362444
322499
316054
216616
203448
719644
654766
629123
620885
570582
536883
41979...

result:

ok good plan

Test #44:

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

input:

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

output:

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

result:

ok good plan

Test #45:

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

input:

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

output:

6
3
7
2
1
4
5
8

result:

ok good plan

Test #46:

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

input:

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

output:

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

result:

ok good plan

Test #47:

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

input:

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

output:

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

result:

ok good plan

Test #48:

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

input:

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

output:

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

result:

ok good plan

Test #49:

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

input:

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

output:

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

result:

ok good plan

Test #50:

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

input:

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

output:

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

result:

ok good plan

Test #51:

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

input:

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

output:

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

result:

ok good plan

Test #52:

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

input:

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

output:

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

result:

ok good plan

Test #53:

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

input:

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

output:

2709
3641
3074
2952
1969
1641
1426
1378
883
3670
3417
3356
3325
2860
2241
2202
2168
2067
2001
1706
1153
1129
731
549
540
193
183
3697
3692
3675
3625
3622
3608
3538
3473
3469
3447
3443
3436
3371
3334
3138
3136
3133
3080
2964
2962
2950
2889
2849
2699
2685
2678
2664
2629
2589
2585
2574
2506
2493
2462
2...

result:

ok good plan

Test #54:

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

input:

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

output:

7783
7337
7172
4936
4898
2024
515
7687
7675
7669
7601
7590
7576
7535
7481
7412
7388
7386
7368
7288
7238
7117
7014
7007
7000
6989
6926
6915
6900
6825
6817
6735
6714
6702
6685
6671
6659
6633
6549
6543
6430
6417
6403
6399
6388
6355
6310
6274
6259
6245
6228
6180
6082
6081
6058
5997
5879
5828
5768
5747
5...

result:

ok good plan

Test #55:

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

input:

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

output:

1037
1937
271
2179
1730
1700
1431
1146
2198
2065
1857
1742
1442
1440
1438
1377
1357
1306
974
935
584
39
2227
2117
2070
2021
1910
1881
1764
821
768
200
139
2190
2058
2028
2024
2004
1977
1906
1812
1769
1718
1666
1640
1539
1420
1339
1318
1297
1288
1198
1035
896
783
665
640
581
543
532
430
413
367
339
3...

result:

ok good plan

Test #56:

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

input:

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

output:

1004
3255
3163
2854
3759
3673
3432
3052
2920
2653
2498
2091
1929
1789
1720
1718
1463
1316
1147
857
708
695
4026
3866
3655
3383
3068
3012
2964
2937
2791
2748
2746
2735
2652
2608
2588
2575
2485
2307
2211
2183
2180
2113
2027
1884
1862
1836
1757
1618
1599
1584
1580
1520
1509
1451
1393
1370
1369
1278
117...

result:

ok good plan

Test #57:

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

input:

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

output:

3932
3496
4856
2783
180
4937
4437
3979
3785
3268
3143
2813
2804
2771
2518
2293
1860
1657
1183
561
412
294
210
12
5209
5177
5143
5103
5026
4778
4743
4722
4602
4568
4529
4511
4450
4397
4390
4363
4357
4305
4273
4240
4228
4069
3918
3881
3824
3771
3746
3692
3683
3645
3615
3576
3421
3370
3344
3297
3014
29...

result:

ok good plan

Test #58:

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

input:

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

output:

208
24
3153
2388
2109
1199
974
633
206
3361
3358
3344
3267
3066
2950
2823
2751
2642
2632
2464
2463
2445
2283
2076
1890
1887
1848
1827
1799
1782
1668
1654
1652
1437
1413
1401
1353
1273
1187
1175
1031
980
926
885
717
714
701
640
639
620
377
368
259
167
144
80
66
3450
3405
3395
3367
3362
3352
3328
3326...

result:

ok good plan

Test #59:

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

input:

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

output:

3246
2233
253
3461
2926
2781
2585
2547
1962
1932
708
278
76
3957
3954
3476
3320
3209
2890
2767
2711
2571
2447
2440
2436
2372
2166
2079
1886
1836
1566
1515
1213
1197
1173
1100
1092
930
793
484
299
246
218
148
3857
3826
3819
3760
3715
3654
3543
3250
3241
3174
3167
3104
3072
3028
2839
2731
2724
2722
26...

result:

ok good plan

Test #60:

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

input:

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

output:

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

result:

ok good plan

Test #61:

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

input:

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

output:

6845
6842
6789
6536
6482
6352
5975
5819
5790
5784
5782
5716
5544
5459
5245
5145
5142
5036
4865
4849
4751
4683
4662
4547
4428
4226
4198
4080
4061
3926
3887
3877
3823
3549
3539
3315
3228
3037
3020
2973
2796
2689
2670
2537
2471
2181
2135
1803
1782
1665
1547
1525
1497
1201
1103
985
976
905
844
784
469
3...

result:

ok good plan

Test #62:

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

input:

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

output:

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

result:

ok good plan

Test #63:

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

input:

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

output:

6
5
4
3
10
7
8
1
9
2
11

result:

ok good plan

Test #64:

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

input:

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

output:

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

result:

ok good plan

Test #65:

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

input:

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

output:

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

result:

ok good plan

Test #66:

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

input:

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

output:

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

result:

ok good plan

Test #67:

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

input:

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

output:

1
10
8
7
2
3
5
6
9
4

result:

ok good plan

Test #68:

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

input:

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

output:

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

result:

ok good plan

Test #69:

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

input:

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

output:

2
1
3

result:

ok good plan

Test #70:

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

input:

1
(

output:

impossible

result:

ok impossible

Test #71:

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

input:

1
)

output:

impossible

result:

ok impossible

Test #72:

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

input:

1
)(

output:

impossible

result:

ok impossible

Test #73:

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

input:

1
()

output:

1

result:

ok good plan

Test #74:

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

input:

2
(
)

output:

1
2

result:

ok good plan

Test #75:

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

input:

2
)
(

output:

2
1

result:

ok good plan

Test #76:

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

input:

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

output:

3
5
2
1
6
4

result:

ok good plan

Extra Test:

score: 0
Extra Test Passed