QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#66035#5108. Prehistoric Programsbili2002#TL 1087ms38288kbC++174.1kb2022-12-06 00:54:502022-12-06 00:54:51

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:54:51]
  • 评测
  • 测评结果:TL
  • 用时:1087ms
  • 内存:38288kb
  • [2022-12-06 00:54:50]
  • 提交

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 true;
        if (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
()
*/


詳細信息

Test #1:

score: 100
Accepted
time: 11ms
memory: 4244kb

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: 1ms
memory: 3368kb

input:

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

output:

223
242
239
496
498
725
502
229
228
511
243
963
793
514
217
216
215
214
213
212
778
907
268
267
466
265
731
471
258
257
894
473
253
252
474
779
476
481
247
245
801
181
799
179
178
177
544
854
707
171
182
168
553
166
554
164
803
162
804
557
198
209
208
516
206
517
719
522
966
524
271
852
715
190
189
...

result:

ok good plan

Test #3:

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

input:

2
()
()

output:

2
1


result:

ok good plan

Test #4:

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

input:

2
((
))

output:

1
2


result:

ok good plan

Test #5:

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

input:

2
)(
()

output:

impossible

result:

ok impossible

Test #6:

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

input:

3
()
(
)

output:

2
1
3


result:

ok good plan

Test #7:

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

input:

3
)(
(
)

output:

2
1
3


result:

ok good plan

Test #8:

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

input:

5
))(
(()
)(
(
)

output:

2
4
3
1
5


result:

ok good plan

Test #9:

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

input:

3
((
))())
(

output:

1
3
2


result:

ok good plan

Test #10:

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

input:

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

output:

impossible

result:

ok impossible

Test #11:

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

input:

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

output:

203
416
214
211
210
209
208
207
205
415
420
199
198
196
424
194
192
191
226
399
234
232
404
405
406
228
227
426
409
410
411
412
219
413
414
156
439
440
442
443
160
159
158
157
166
445
153
152
149
449
143
452
141
178
427
428
186
429
184
182
431
180
239
177
434
172
171
435
436
437
367
325
362
321
320
...

result:

ok good plan

Test #12:

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

input:

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

output:

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


result:

ok good plan

Test #13:

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

input:

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

output:

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


result:

ok good plan

Test #14:

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

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
48
20
136
130
53
103
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
45
30
19
115
129
96
117
137
85
55
5
41
72
21
71
127
50
81
...

result:

ok good plan

Test #15:

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

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
10
19
14
5
26
66
42
15
4
102
23
55
80
107
16
84
112
75
113
29
145
117
63
74
82
53
34
39
88
144
85
21
140
7
41
62
45
18
76
114
136
90
50
13
122
40
81
96
111
79
97
125
12
116
123
22
20
108
139
115...

result:

ok good plan

Test #16:

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

input:

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

output:

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

result:

ok good plan

Test #17:

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

input:

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

output:

588
578
250
246
581
584
243
585
587
238
255
589
590
231
230
229
228
227
225
224
269
287
547
549
281
555
556
274
563
569
592
570
571
265
264
263
573
574
259
258
635
185
184
182
181
180
625
632
176
175
186
172
636
169
166
645
164
163
162
160
606
220
593
594
214
213
212
601
208
605
541
204
609
195
612
...

result:

ok good plan

Test #18:

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

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: 1ms
memory: 3216kb

input:

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

output:

impossible

result:

ok impossible

Test #20:

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

input:

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

output:

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


result:

ok good plan

Test #21:

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

input:

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

output:

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


result:

ok good plan

Test #22:

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

input:

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

output:

impossible

result:

ok impossible

Test #23:

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

input:

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

output:

impossible

result:

ok impossible

Test #24:

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

input:

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

output:

impossible

result:

ok impossible

Test #25:

score: 0
Accepted
time: 1087ms
memory: 28268kb

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: 39ms
memory: 20260kb

input:

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

output:

impossible

result:

ok impossible

Test #27:

score: 0
Accepted
time: 45ms
memory: 20884kb

input:

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

output:

impossible

result:

ok impossible

Test #28:

score: 0
Accepted
time: 53ms
memory: 20968kb

input:

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

output:

1


result:

ok good plan

Test #29:

score: 0
Accepted
time: 54ms
memory: 19600kb

input:

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

output:

impossible

result:

ok impossible

Test #30:

score: 0
Accepted
time: 65ms
memory: 20596kb

input:

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

output:

impossible

result:

ok impossible

Test #31:

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

input:

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

output:

2
1


result:

ok good plan

Test #32:

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

input:

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

output:

impossible

result:

ok impossible

Test #33:

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

input:

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

output:

3
1
2


result:

ok good plan

Test #34:

score: 0
Accepted
time: 115ms
memory: 26680kb

input:

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

output:

impossible

result:

ok impossible

Test #35:

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

input:

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

output:

impossible

result:

ok impossible

Test #36:

score: 0
Accepted
time: 176ms
memory: 26628kb

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: 209ms
memory: 38288kb

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
Time Limit Exceeded

input:

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

output:


result: