QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#66040#5108. Prehistoric Programsbili2002#WA 204ms38312kbC++173.9kb2022-12-06 00:59:322022-12-06 00:59:35

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-06 00:59:35]
  • 评测
  • 测评结果:WA
  • 用时:204ms
  • 内存:38312kb
  • [2022-12-06 00:59:32]
  • 提交

answer


#include <bits/stdc++.h>
#define f first
#define s second
#define sz(a) ((int)a.size())
#define all(a) a.begin(), a.end()
#define pb push_back
#define eb emplace_back

using namespace std;
using ll = long long;

template<class T, class T2> inline bool chkmax(T &x, const T2 & y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 & y) { return x > y ? x = y, 1 : 0; }
template<class T, class T2> inline istream &operator>>(istream &is,       pair<T, T2> &p)             { is>>p.f>>p.s;        return is; }
template<class T, class T2> inline ostream &operator<<(ostream &os, const pair<T, T2> &p)             { os<<p.f<<' '<<p.s;   return os; }
template<class T>           inline istream &operator>>(istream &is,       vector<T> &v)               { for (auto &id : v)   is>>id;       return is; }
template<class T>           inline ostream &operator<<(ostream &os, const vector<T> &v)               { for (auto id : v)    os<<id<<'\n';  return os; }
template<class T, class T2> inline ostream &operator<<(ostream &os, const map<T, T2> &m)              { for (auto id : m)    os<<id<<'\n'; return os; }
template<class T, class T2> inline ostream &operator<<(ostream &os, const unordered_map<T, T2> &um)   { for (auto id : um)   os<<id<<'\n'; return os; }
template<class T>           inline ostream &operator<<(ostream &os, const list<T> &l)                 { for (auto id : l)    os<<id<<' ';  return os; }
template<class T>           inline ostream &operator<<(ostream &os, const set<T> &s)                  { for (auto id : s)    os<<id<<' ';  return os; }
template<class T>           inline ostream &operator<<(ostream &os, const unordered_set<T> &us)       { for (auto id : us)   os<<id<<' ';  return os; }
const long long INF = 1e18;
const bool hasTests = 0;

struct par {
    int op, cl;
    int id;
    bool neg;
    int highestMin;

    bool operator<(const par& oth) {
        if (!neg && oth.neg) {
            return true;
        }
        if (neg && !oth.neg) {
            return false;
        }

        if (op - cl > 0 && oth.op - oth.cl <= 0) {
            return true;
        }
        if (op - cl <= 0 && oth.op - oth.cl > 0) {
            return false;
        }

        if (op - cl <= 0) {
            return highestMin < oth.highestMin;
        } else {
            return highestMin > oth.highestMin;
        }
    }
};

vector<par> p;

bool pos;
vector<int> ans;
int n;

void input() {
    cin>>n;
    p.resize(n);

    string s;
    for (int i=0; i<n; i++) {
        cin>>s;
        p[i].id = i;
        p[i].neg = false;
        for (auto curr : s) {
            if (curr == '(') {
                p[i].op++;
            } else {
                p[i].cl++;
            }
            if (p[i].op < p[i].cl) {
                p[i].neg = true;
            }
            p[i].highestMin = min(p[i].highestMin, p[i].op - p[i].cl);
        }
        //cerr<<i<<' '<<p[i].highestMin<<' '<<p[i].neg<<endl;
    }
}

void output() {
    if (!pos) {
        cout<<"impossible"<<endl;
        return;
    }

    cout<<ans<<endl;
}

void solve() {
    sort(all(p));

    pos = true;
    int cntOp = 0, cntCl = 0;
    for (auto& curr : p) {
        //cout<<curr.id<<' '<<cntOp + curr.highestMin<<' '<<cntCl<<endl;
        if (cntOp + curr.highestMin < cntCl) {
            pos = false;
            break;
        }

        cntOp += curr.op;
        cntCl += curr.cl;
        ans.pb(curr.id + 1);
    }

    if (cntOp != cntCl) {
        pos = false;
    }

}

void start() {
    int t = 1;
    if (hasTests) {
        cin>>t;
    }

    for (int i=1; i<=t; i++) {
        input();
        solve();
        //cout<<"Case #"<<i<<": ";
        output();
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    start();
    return 0;
}

/*
7
((((()
()))))
(
)
((
))((
))

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

2
()
*/


Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

26315
26345
26341
26339
26336
26334
26333
26329
26328
26327
26321
26320
26318
26317
26316
26347
26313
26311
26308
26307
26305
26302
26297
26295
26294
26292
26290
26289
26286
26384
26414
26413
26412
26409
26406
26402
26401
26399
26398
26396
26395
26394
26393
26285
26383
26382
26380
26376
26370
26366
...

result:

ok good plan

Test #2:

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

input:

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

output:

188
387
667
390
666
731
396
190
189
386
398
732
814
399
182
181
663
179
907
213
212
673
371
209
208
372
206
178
668
377
379
381
382
384
198
746
422
894
652
426
427
430
650
439
963
646
147
443
445
447
143
449
640
738
177
662
406
659
408
410
171
414
214
168
655
166
420
164
162
811
257
265
826
929
309
...

result:

ok good plan

Test #3:

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

input:

2
()
()

output:

1
2


result:

ok good plan

Test #4:

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

input:

2
((
))

output:

1
2


result:

ok good plan

Test #5:

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

input:

2
)(
()

output:

impossible

result:

ok impossible

Test #6:

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

input:

3
()
(
)

output:

2
1
3


result:

ok good plan

Test #7:

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

input:

3
)(
(
)

output:

2
1
3


result:

ok good plan

Test #8:

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

input:

5
))(
(()
)(
(
)

output:

2
4
1
3
5


result:

ok good plan

Test #9:

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

input:

3
((
))())
(

output:

1
3
2


result:

ok good plan

Test #10:

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

input:

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

output:

impossible

result:

ok impossible

Test #11:

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

input:

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

output:

166
152
153
381
440
156
157
158
159
160
439
275
437
436
435
442
434
274
271
431
171
172
269
268
429
176
177
178
428
180
136
456
296
124
373
290
288
128
129
130
131
132
133
287
452
427
286
285
139
449
141
284
143
283
282
378
445
277
149
443
226
414
413
214
412
411
410
409
219
249
248
406
405
404
247
...

result:

ok good plan

Test #12:

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

input:

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

output:

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


result:

ok good plan

Test #13:

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

input:

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

output:

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


result:

ok good plan

Test #14:

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

input:

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

output:

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

result:

ok good plan

Test #15:

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

input:

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

output:

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

result:

ok good plan

Test #16:

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

input:

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

output:

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

result:

ok good plan

Test #17:

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

input:

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

output:

571
563
238
569
570
231
230
229
228
227
556
225
224
573
220
574
218
578
214
213
259
522
274
526
530
269
265
264
263
541
212
258
255
250
547
549
246
555
243
612
181
180
605
606
176
175
609
172
169
182
166
164
163
162
160
159
158
157
156
590
208
581
584
204
585
587
588
589
195
518
592
191
593
594
601
...

result:

ok good plan

Test #18:

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

input:

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

output:

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


result:

ok good plan

Test #19:

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

input:

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

output:

impossible

result:

ok impossible

Test #20:

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

input:

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

output:

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


result:

ok good plan

Test #21:

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

input:

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

output:

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


result:

ok good plan

Test #22:

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

input:

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

output:

impossible

result:

ok impossible

Test #23:

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

input:

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

output:

impossible

result:

ok impossible

Test #24:

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

input:

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

output:

impossible

result:

ok impossible

Test #25:

score: 0
Accepted
time: 200ms
memory: 26800kb

input:

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

output:

534143
534126
534127
534129
534130
534133
534135
534139
534140
534142
534125
534144
534145
534146
534150
534153
534154
534155
534158
534104
534082
534090
534091
534097
534098
534100
534102
534103
534159
534110
534111
534112
534113
534114
534117
534118
534119
534215
534201
534203
534204
534206
534209...

result:

ok good plan

Test #26:

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

input:

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

output:

impossible

result:

ok impossible

Test #27:

score: 0
Accepted
time: 38ms
memory: 19908kb

input:

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

output:

impossible

result:

ok impossible

Test #28:

score: 0
Accepted
time: 62ms
memory: 19752kb

input:

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

output:

1


result:

ok good plan

Test #29:

score: 0
Accepted
time: 40ms
memory: 20820kb

input:

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

output:

impossible

result:

ok impossible

Test #30:

score: 0
Accepted
time: 50ms
memory: 20792kb

input:

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

output:

impossible

result:

ok impossible

Test #31:

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

input:

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

output:

2
1


result:

ok good plan

Test #32:

score: 0
Accepted
time: 49ms
memory: 11240kb

input:

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

output:

impossible

result:

ok impossible

Test #33:

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

input:

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

output:

3
1
2


result:

ok good plan

Test #34:

score: 0
Accepted
time: 131ms
memory: 26796kb

input:

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

output:

impossible

result:

ok impossible

Test #35:

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

input:

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

output:

impossible

result:

ok impossible

Test #36:

score: 0
Accepted
time: 189ms
memory: 26700kb

input:

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

output:

555562
555542
555544
555546
555548
555550
555552
555554
555556
555558
555560
555540
555564
555566
555568
555570
555572
555574
555576
555578
555580
555520
555502
555504
555506
555508
555510
555512
555514
555516
555518
555582
555522
555524
555526
555528
555530
555532
555534
555536
555538
555644
555624...

result:

ok good plan

Test #37:

score: 0
Accepted
time: 204ms
memory: 38312kb

input:

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

output:

666672
666657
666658
666659
666660
666661
666662
666663
666664
666665
666666
666667
666668
666669
666670
666671
666656
666673
666674
666675
666676
666677
666678
666679
666680
666681
666682
666683
666684
666685
666686
666641
666626
666627
666628
666629
666630
666631
666632
666633
666634
666635
666636...

result:

ok good plan

Test #38:

score: -100
Wrong Answer
time: 177ms
memory: 26708kb

input:

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

output:

impossible

result:

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