QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#101661#5108. Prehistoric ProgramsmiaomiaoziWA 349ms64916kbC++171.5kb2023-04-30 17:20:032023-04-30 17:20:04

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-30 17:20:04]
  • 评测
  • 测评结果:WA
  • 用时:349ms
  • 内存:64916kb
  • [2023-04-30 17:20:03]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
// https://space.bilibili.com/672346917

using LL = long long;

int main () {
    cin.tie(nullptr)->sync_with_stdio(false);
    cout << fixed << setprecision(12);

    int n;
    cin >> n;

    vector<array<int, 3>> pos, neg;
    vector<string> ss(n);
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        ss[i] = s;

        int mn = 0x3f3f3f3f;
        int tot = 0;
        for (char c : s) {
            tot += (c == '(' ? 1 : -1);
            mn = min(mn, tot);
        }

        if (tot >= 0) {
            pos.push_back({tot, mn, i});
        } else {
            neg.push_back({tot, mn, i});
        }
    }

    sort(pos.begin(), pos.end(), [&](auto u, auto v) {
        return u[1] == v[1] ? u[0] > v[0] : u[1] > v[1];
    });
    sort(neg.begin(), neg.end(), [&](auto u, auto v) {
        return u[1] == v[1] ? u[0] < v[0] : u[1] < v[1];
    });
    vector<int> p;
    for (auto [a, b, c] : pos) {
        p.push_back(c);
    }
    for (auto [a, b, c] : neg) {
        p.push_back(c);
    }

    int tot = 0, ok = 1;
    for (int x : p) {
        for (auto c : ss[x]) {
            tot += c == ')' ? -1 : 1;
            if (tot < 0) {
                ok = 0;
            }
        }
    }

    if (tot != 0) {
        ok = 0;
    }

    if (!ok) {
        cout << "impossible\n";
        return 0;
    }

    for (auto x : p) {
        cout << x + 1 << "\n";
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 7ms
memory: 6164kb

input:

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

output:

4238
48374
389
2458
6754
18533
6986
32583
23456
5803
31692
169
10427
26677
34539
41740
46194
24373
30771
35132
39743
25061
23312
33777
5699
34110
45491
31402
28794
7365
23551
35743
6381
41639
41641
6701
40415
20865
35499
34723
42121
3880
11768
22710
16030
17649
30949
15279
34479
18953
40332
25697
19...

result:

ok good plan

Test #2:

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

input:

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

output:

36
66
386
585
257
127
39
907
329
598
814
62
981
707
384
131
662
807
511
793
449
271
632
327
422
474
387
746
20
915
919
88
553
168
535
715
473
334
502
31
171
989
667
872
863
859
390
852
258
134
725
738
820
819
208
316
324
774
640
164
604
177
799
566
945
947
60
33
929
464
414
563
98
17
406
881
655
301...

result:

ok good plan

Test #3:

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

input:

2
()
()

output:

1
2

result:

ok good plan

Test #4:

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

input:

2
((
))

output:

1
2

result:

ok good plan

Test #5:

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

input:

2
)(
()

output:

impossible

result:

ok impossible

Test #6:

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

input:

3
()
(
)

output:

2
1
3

result:

ok good plan

Test #7:

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

input:

3
)(
(
)

output:

2
1
3

result:

ok good plan

Test #8:

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

input:

5
))(
(()
)(
(
)

output:

2
4
3
1
5

result:

ok good plan

Test #9:

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

input:

3
((
))())
(

output:

1
3
2

result:

ok good plan

Test #10:

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

input:

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

output:

impossible

result:

ok impossible

Test #11:

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

input:

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

output:

311
479
329
232
199
483
297
253
80
177
414
211
357
265
309
321
320
318
315
288
308
296
290
283
325
327
330
334
338
339
340
343
344
345
349
351
353
258
228
234
239
1
241
242
243
247
248
249
251
254
256
287
262
264
268
269
271
274
275
277
282
360
284
285
286
459
428
429
431
434
435
436
437
439
440
442...

result:

ok good plan

Test #12:

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

input:

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

output:

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

result:

ok good plan

Test #13:

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

input:

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

output:

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

result:

ok good plan

Test #14:

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

input:

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

output:

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

result:

ok good plan

Test #15:

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

input:

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

output:

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

result:

ok good plan

Test #16:

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

input:

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

output:

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

result:

ok good plan

Test #17:

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

input:

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

output:

468
390
396
4
122
1
601
657
79
180
274
158
526
730
547
25
485
571
418
246
406
230
395
408
103
606
131
481
530
494
164
166
341
41
43
56
55
345
490
477
475
470
469
348
461
455
450
446
442
343
440
491
338
492
335
333
331
330
495
500
326
13
409
384
378
385
387
392
374
7
371
397
401
369
407
324
441
417
3...

result:

ok good plan

Test #18:

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

input:

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

output:

43
48
70
53
57
59
60
61
62
65
66
67
68
50
74
79
81
82
84
86
87
88
91
94
100
4
6
9
10
11
12
17
18
19
20
22
27
28
29
31
32
38
44
46
51
37
95
42
25
7
63
54
78
55
56
58
64
69
71
72
73
75
76
77
52
80
83
85
89
90
92
93
96
97
98
99
26
2
3
5
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: 2ms
memory: 3384kb

input:

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

output:

impossible

result:

ok impossible

Test #20:

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

input:

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

output:

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

result:

ok good plan

Test #21:

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

input:

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

output:

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

result:

ok good plan

Test #22:

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

input:

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

output:

impossible

result:

ok impossible

Test #23:

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

input:

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

output:

impossible

result:

ok impossible

Test #24:

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

input:

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

output:

impossible

result:

ok impossible

Test #25:

score: 0
Accepted
time: 237ms
memory: 60116kb

input:

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

output:

264227
770337
898404
83071
269214
897909
857929
731069
196234
352796
904916
134097
308325
992894
501576
309146
675083
748267
592970
900795
619800
507757
610823
267140
714320
769249
833824
902203
932913
799635
25080
703503
175996
470977
799479
385146
999836
705720
356849
164427
860200
637563
466467
6...

result:

ok good plan

Test #26:

score: 0
Accepted
time: 31ms
memory: 22508kb

input:

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

output:

impossible

result:

ok impossible

Test #27:

score: 0
Accepted
time: 29ms
memory: 22520kb

input:

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

output:

impossible

result:

ok impossible

Test #28:

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

input:

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

output:

1

result:

ok good plan

Test #29:

score: 0
Accepted
time: 34ms
memory: 22516kb

input:

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

output:

impossible

result:

ok impossible

Test #30:

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

input:

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

output:

impossible

result:

ok impossible

Test #31:

score: 0
Accepted
time: 34ms
memory: 19168kb

input:

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

output:

2
1

result:

ok good plan

Test #32:

score: 0
Accepted
time: 37ms
memory: 19212kb

input:

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

output:

impossible

result:

ok impossible

Test #33:

score: 0
Accepted
time: 29ms
memory: 22480kb

input:

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

output:

3
1
2

result:

ok good plan

Test #34:

score: 0
Accepted
time: 126ms
memory: 53856kb

input:

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

output:

impossible

result:

ok impossible

Test #35:

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

input:

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

output:

impossible

result:

ok impossible

Test #36:

score: 0
Accepted
time: 193ms
memory: 53836kb

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: 207ms
memory: 64916kb

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: 336ms
memory: 64032kb

input:

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

output:

164663
944202
483356
500584
889056
90286
879218
637097
496501
763948
679768
163748
732016
911154
629235
590693
924596
428626
321244
67591
323909
475331
378339
261112
970762
130656
880821
897141
553153
740159
480934
491924
766848
235797
354542
318856
782080
578545
47535
786672
465501
507855
663182
80...

result:

ok good plan

Test #39:

score: 0
Accepted
time: 349ms
memory: 63992kb

input:

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

output:

568499
675014
629151
425960
795023
985988
463859
106383
137311
597972
689231
353729
427235
129338
388609
207485
623824
770416
116108
123122
696104
470327
905927
289835
333468
123227
77139
437875
391833
104949
328008
209291
122925
902316
858526
460894
186938
287685
713994
542007
192291
420073
840131
...

result:

ok good plan

Test #40:

score: 0
Accepted
time: 57ms
memory: 13044kb

input:

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

output:

163
542
108
367
236
287
469
358
360
537
253
305
105
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
48...

result:

ok good plan

Test #41:

score: -100
Wrong Answer
time: 65ms
memory: 12720kb

input:

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

output:

impossible

result:

wrong answer you didn't find a solution but jury did