QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#391626#5108. Prehistoric ProgramssurenjamtsAC ✓326ms38832kbC++142.0kb2024-04-16 17:43:542024-04-16 17:43:54

Judging History

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

  • [2024-04-16 17:43:54]
  • 评测
  • 测评结果:AC
  • 用时:326ms
  • 内存:38832kb
  • [2024-04-16 17:43:54]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int main(){
//	ios::sync_with_stdio(0);
//	cin.tie(NULL);
	int n;
	cin>>n;
	string s;
	vector<pair<int,int>> begi;
	vector<pair<pair<int,int>,int>> mid;
	vector<pair<int,int>> en;
	vector< int > vc;
	for(int i=0; i<n; i++){
		cin>>s;
		int cur=0;
		string st="";
		for(int j=0; j<s.size(); j++){
			if(s[j]=='('){
				cur++;
				st+='(';
			}	
			else{
				if(st.size()>0 and st[st.size()-1]=='('){
					st.pop_back();
				}
				else{
					st+=')';
				}
				cur--;
			}
		}
//		cout<<st<<endl;
		cur=st.size();
		if(cur==0){
			vc.push_back( i );
			continue;
		}
		if(cur==1){
			if(st[0]=='(') begi.push_back({cur,i});
			else en.push_back({cur,i});
		}
		else{
			int l=0, r=cur-1;
			if(st[l]==st[r]){
				if(st[l]=='(') begi.push_back({cur,i});
				else{
					en.push_back({cur,i});
				}
			}
			else{
//				cout << "we got mid here\n";
				//mid
				int mx=0;
				for(int j=0; j<cur; j++){
					if(st[j]==')') mx--;
					else break;
				}
//				cout << "i:" << i << "\n";
//				cout << cur << " " << mx << "\n";
				mx = abs(mx);
				//mx cur-mx  cur-mx*2
				mid.push_back({{mx,-cur+mx*2},i});
			}
		}
	}
	sort(mid.begin(),mid.end());
	vector<int> ans;
	int cur=0;
	for(int i=0; i<begi.size(); i++){
//		cout << begi[i].first << "heregg\n";
		cur+=begi[i].first;
		ans.push_back(begi[i].second);
	}
	for(int i=0; i<mid.size(); i++){
//		cout << mid[i].first.first << " " << mid[i].first.second << " " << mid[i].second << "heregg\n";
		int fi=mid[i].first.first, se=-mid[i].first.second;
		if(cur-fi<0){
			cout<<"impossible"<<endl;
			return 0;
		}
		cur+=se;
		ans.push_back(mid[i].second);
	}
	for(int i=0; i<en.size(); i++){
//		cout << en[i].i
		cur-=en[i].first;
		ans.push_back(en[i].second);
	}
	if(cur==0){
		for(int i: ans){
			cout<<i+1<<'\n';
		}
		for(int i = 0; i < vc.size(); i ++ ){
			cout << vc[i]+1 << '\n';
		}
	}
	else{
		cout<<"impossible"<<endl;
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 16ms
memory: 4052kb

input:

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

output:

1
2
5
7
8
9
10
11
12
14
16
19
23
27
28
30
32
34
35
37
38
42
43
44
54
55
58
59
61
70
72
76
77
79
80
87
91
92
93
94
95
96
97
99
112
116
117
118
120
122
125
126
127
128
130
131
135
136
143
146
147
148
149
150
151
154
161
162
165
166
169
175
176
177
179
181
182
183
184
185
186
187
191
192
193
194
195
19...

result:

ok good plan

Test #2:

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

input:

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

output:

1
3
10
12
13
14
17
18
20
22
31
33
36
39
54
58
60
62
64
65
66
75
77
80
83
88
89
90
92
97
98
101
104
106
110
122
125
126
127
131
134
135
136
143
147
162
164
166
168
171
177
178
179
181
182
188
189
190
198
206
208
209
212
213
214
215
216
217
223
228
229
239
242
243
245
247
252
253
257
258
265
267
268
2...

result:

ok good plan

Test #3:

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

input:

2
()
()

output:

1
2

result:

ok good plan

Test #4:

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

input:

2
((
))

output:

1
2

result:

ok good plan

Test #5:

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

input:

2
)(
()

output:

impossible

result:

ok impossible

Test #6:

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

input:

3
()
(
)

output:

2
3
1

result:

ok good plan

Test #7:

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

input:

3
)(
(
)

output:

2
1
3

result:

ok good plan

Test #8:

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

input:

5
))(
(()
)(
(
)

output:

2
4
3
1
5

result:

ok good plan

Test #9:

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

input:

3
((
))())
(

output:

1
3
2

result:

ok good plan

Test #10:

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

input:

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

output:

impossible

result:

ok impossible

Test #11:

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

input:

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

output:

1
4
6
7
10
11
12
13
16
17
19
20
22
23
24
26
27
29
31
33
36
37
38
40
41
45
46
49
51
52
53
55
56
58
59
60
62
65
66
69
70
71
72
73
75
76
77
78
79
80
82
83
85
86
87
90
91
92
94
95
96
99
102
104
105
106
107
109
114
117
120
124
128
129
130
131
132
133
136
139
141
143
149
152
153
156
157
158
159
160
166
17...

result:

ok good plan

Test #12:

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

input:

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

output:

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

result:

ok good plan

Test #13:

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

input:

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

output:

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

result:

ok good plan

Test #14:

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

input:

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

output:

4
6
7
11
12
14
15
17
24
28
32
35
37
38
40
49
52
60
69
73
79
84
87
92
94
98
100
104
105
106
111
120
140
141
142
143
148
149
93
61
89
91
135
62
23
27
51
70
10
16
133
5
96
117
129
137
102
29
77
147
80
101
128
125
25
2
3
9
122
76
78
56
18
47
43
86
41
115
139
82
150
134
58
90
59
114
30
45
85
88
124
36
14...

result:

ok good plan

Test #15:

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

input:

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

output:

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

result:

ok good plan

Test #16:

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

input:

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

output:

8
27
30
36
45
48
50
52
55
58
60
65
67
74
75
81
84
92
93
97
99
106
108
110
111
115
117
118
122
123
129
130
131
136
140
149
63
127
100
42
46
88
70
24
1
11
31
56
9
19
26
57
124
114
15
101
35
120
82
146
119
14
91
128
86
133
107
37
40
49
150
32
43
4
113
13
69
12
90
78
103
139
21
102
143
147
44
137
148
11...

result:

ok good plan

Test #17:

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

input:

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

output:

1
4
7
9
13
16
17
20
21
22
25
27
34
37
41
43
45
48
55
56
57
62
65
66
67
69
74
79
81
82
95
97
101
103
104
108
112
116
121
122
131
136
138
141
148
149
150
152
155
156
157
158
159
160
162
163
164
166
169
172
175
176
180
181
182
184
185
186
191
195
204
208
212
213
214
218
220
224
225
227
228
229
230
231
...

result:

ok good plan

Test #18:

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

input:

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

output:

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

result:

ok good plan

Test #19:

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

input:

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

output:

impossible

result:

ok impossible

Test #20:

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

input:

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

output:

5
6
7
9
11
12
15
16
19
21
22
26
29
30
33
38
39
41
42
43
46
47
49
51
53
57
60
61
62
65
66
68
69
70
72
73
76
80
84
86
87
92
94
95
98
75
81
100
3
56
1
2
4
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
14
85

result:

ok good plan

Test #21:

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

input:

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

output:

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

result:

ok good plan

Test #22:

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

input:

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

output:

impossible

result:

ok impossible

Test #23:

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

input:

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

output:

impossible

result:

ok impossible

Test #24:

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

input:

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

output:

impossible

result:

ok impossible

Test #25:

score: 0
Accepted
time: 229ms
memory: 17668kb

input:

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

output:

2
4
5
6
8
9
12
13
20
23
28
29
30
31
36
37
38
42
44
49
52
54
55
60
63
65
66
69
74
77
82
86
87
88
89
90
91
94
95
98
99
100
102
104
106
110
111
112
117
119
120
122
133
135
139
140
142
143
144
147
149
150
151
153
156
157
159
164
165
167
168
170
172
177
179
180
181
183
190
192
193
197
200
203
204
207
208...

result:

ok good plan

Test #26:

score: 0
Accepted
time: 116ms
memory: 38832kb

input:

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

output:

impossible

result:

ok impossible

Test #27:

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

input:

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

output:

impossible

result:

ok impossible

Test #28:

score: 0
Accepted
time: 133ms
memory: 28428kb

input:

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

output:

1

result:

ok good plan

Test #29:

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

input:

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

output:

impossible

result:

ok impossible

Test #30:

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

input:

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

output:

impossible

result:

ok impossible

Test #31:

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

input:

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

output:

2
1

result:

ok good plan

Test #32:

score: 0
Accepted
time: 123ms
memory: 12652kb

input:

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

output:

impossible

result:

ok impossible

Test #33:

score: 0
Accepted
time: 125ms
memory: 18620kb

input:

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

output:

3
1
2

result:

ok good plan

Test #34:

score: 0
Accepted
time: 190ms
memory: 19084kb

input:

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

output:

impossible

result:

ok impossible

Test #35:

score: 0
Accepted
time: 192ms
memory: 19160kb

input:

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

output:

impossible

result:

ok impossible

Test #36:

score: 0
Accepted
time: 242ms
memory: 17332kb

input:

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

output:

2
4
6
8
10
12
14
16
18
20
22
24
26
28
30
32
34
36
38
40
42
44
46
48
50
52
54
56
58
60
62
64
66
68
70
72
74
76
78
80
82
84
86
88
90
92
94
96
98
100
102
104
106
108
110
112
114
116
118
120
122
124
126
128
130
132
134
136
138
140
142
144
146
148
150
152
154
156
158
160
162
164
166
168
170
172
174
176
1...

result:

ok good plan

Test #37:

score: 0
Accepted
time: 223ms
memory: 28680kb

input:

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

output:

500001
500002
500003
500004
500005
500006
500007
500008
500009
500010
500011
500012
500013
500014
500015
500016
500017
500018
500019
500020
500021
500022
500023
500024
500025
500026
500027
500028
500029
500030
500031
500032
500033
500034
500035
500036
500037
500038
500039
500040
500041
500042
500043...

result:

ok good plan

Test #38:

score: 0
Accepted
time: 323ms
memory: 20556kb

input:

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

output:

5
11
13
14
17
21
27
29
33
36
37
40
43
49
57
59
61
62
63
65
75
83
84
87
90
99
102
104
115
119
128
133
139
154
155
157
158
159
164
173
174
181
183
185
187
190
191
194
196
197
207
212
214
215
218
219
222
223
224
226
229
230
233
237
240
243
244
249
250
253
257
260
263
267
269
270
271
273
275
276
279
282...

result:

ok good plan

Test #39:

score: 0
Accepted
time: 326ms
memory: 20416kb

input:

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

output:

2
5
12
13
15
29
36
38
39
44
47
59
61
66
70
72
75
86
87
92
94
99
101
104
110
113
115
118
119
126
128
132
134
136
138
141
143
149
150
158
163
168
171
180
187
189
190
193
195
211
219
225
228
232
233
235
237
239
243
247
253
257
258
259
260
269
270
274
278
279
297
300
302
307
313
315
319
320
322
326
332
...

result:

ok good plan

Test #40:

score: 0
Accepted
time: 153ms
memory: 3796kb

input:

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

output:

108
163
236
253
287
305
358
360
367
469
537
542
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
208
139
153
340
133
286
451
301
421
52
11
350
182
477
255
32
463
483
408
299
24
79
235
330
553
533
529
81
223
443
137
552
327
510
43...

result:

ok good plan

Test #41:

score: 0
Accepted
time: 151ms
memory: 3724kb

input:

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

output:

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

result:

ok good plan

Test #42:

score: 0
Accepted
time: 168ms
memory: 4528kb

input:

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

output:

51
58
59
60
69
112
120
144
146
159
163
186
193
195
198
202
204
209
210
228
231
232
242
258
263
264
269
271
282
285
288
297
301
302
309
314
352
377
378
391
394
397
398
404
409
410
414
415
442
446
455
481
501
508
510
518
530
549
563
566
575
584
586
595
602
612
614
622
625
631
654
657
670
673
685
689
7...

result:

ok good plan

Test #43:

score: 0
Accepted
time: 285ms
memory: 18276kb

input:

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

output:

8
9
13
14
29
41
42
46
53
57
61
66
69
84
89
107
108
109
110
115
117
118
121
125
131
133
135
145
156
157
164
170
171
177
180
181
184
189
192
193
204
206
207
212
219
220
225
232
233
235
237
240
244
250
252
253
257
261
264
265
266
267
272
273
274
277
282
295
298
301
305
307
314
317
325
334
340
345
352
3...

result:

ok good plan

Test #44:

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

input:

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

output:

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

result:

ok good plan

Test #45:

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

input:

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

output:

6
3
1
7
2
4
5
8

result:

ok good plan

Test #46:

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

input:

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

output:

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

result:

ok good plan

Test #47:

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

input:

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

output:

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

result:

ok good plan

Test #48:

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

input:

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

output:

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

result:

ok good plan

Test #49:

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

input:

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

output:

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

result:

ok good plan

Test #50:

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

input:

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

output:

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

result:

ok good plan

Test #51:

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

input:

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

output:

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

result:

ok good plan

Test #52:

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

input:

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

output:

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

result:

ok good plan

Test #53:

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

input:

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

output:

1
4
6
7
8
10
12
19
21
22
25
26
28
31
35
40
41
46
47
48
50
54
57
59
60
61
63
66
70
74
79
81
85
86
87
88
94
95
105
106
107
109
111
115
117
118
123
125
129
134
135
136
138
139
140
144
145
149
152
153
156
162
164
167
169
173
175
177
181
183
189
193
196
198
200
201
202
206
207
210
212
213
217
224
226
227...

result:

ok good plan

Test #54:

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

input:

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

output:

1
7
8
9
12
13
15
16
19
20
22
23
24
26
31
33
37
38
43
44
45
47
48
51
53
54
56
58
59
60
61
62
65
67
71
72
75
78
79
83
86
91
92
93
94
95
96
98
99
102
104
105
107
108
111
115
116
120
121
122
129
134
136
137
139
140
144
146
147
148
149
151
152
153
155
158
160
161
162
163
165
167
168
169
171
172
173
174
1...

result:

ok good plan

Test #55:

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

input:

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

output:

3
6
7
10
13
22
24
28
32
33
36
37
38
39
40
42
47
48
49
50
51
54
56
61
66
72
73
75
79
83
84
87
89
91
92
97
98
105
109
111
112
114
121
122
123
124
127
130
131
133
135
136
138
139
140
143
146
147
148
149
155
158
159
162
170
174
178
179
183
187
188
196
198
200
201
202
203
209
213
221
222
226
227
228
229
...

result:

ok good plan

Test #56:

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

input:

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

output:

4
7
10
14
15
17
18
19
22
23
24
25
32
33
35
38
39
41
42
44
46
47
49
50
51
52
59
63
64
67
71
72
73
75
76
77
79
80
82
91
94
95
96
97
98
101
105
106
107
110
117
123
125
133
138
142
146
150
151
153
163
164
165
167
168
170
173
174
175
178
180
188
190
191
193
200
205
209
212
217
221
222
223
226
230
231
232...

result:

ok good plan

Test #57:

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

input:

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

output:

3
4
5
9
12
14
17
18
24
25
26
27
28
33
36
37
38
39
40
41
42
44
45
46
51
54
55
58
60
61
63
66
69
70
71
74
78
81
82
83
85
87
89
90
91
92
101
102
104
108
111
113
114
116
117
118
121
122
124
125
126
127
129
130
131
133
135
136
137
143
144
146
154
155
158
161
163
164
167
169
170
173
180
181
182
188
192
19...

result:

ok good plan

Test #58:

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

input:

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

output:

1
4
5
7
8
13
16
20
21
24
25
27
29
30
34
35
36
39
40
41
42
45
48
51
52
53
57
60
63
66
72
73
79
80
85
88
94
95
96
99
104
108
111
115
118
120
121
124
125
127
131
133
134
135
136
138
141
142
144
145
148
154
164
166
167
169
171
176
177
183
184
187
188
189
190
191
192
195
201
205
206
208
210
211
212
213
2...

result:

ok good plan

Test #59:

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

input:

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

output:

2
4
8
9
11
12
13
15
19
22
25
26
28
29
31
37
38
39
43
46
47
49
56
58
59
62
63
67
69
73
75
76
77
79
81
84
87
88
92
94
95
100
102
105
106
108
109
113
115
116
120
125
127
129
131
140
141
143
144
148
150
151
154
156
162
164
167
174
176
178
180
181
186
190
191
194
196
197
202
203
206
214
216
218
219
221
2...

result:

ok good plan

Test #60:

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

input:

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

output:

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

result:

ok good plan

Test #61:

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

input:

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

output:

1
2
4
5
6
7
11
14
17
18
19
20
22
26
27
31
32
35
36
37
38
39
40
41
46
48
50
53
55
59
61
63
64
65
69
71
72
76
78
79
82
83
84
85
89
91
97
98
99
101
103
107
108
109
110
111
114
115
116
117
120
121
122
123
124
126
128
131
133
134
135
136
137
138
141
150
154
158
160
164
165
166
170
174
175
176
180
182
186...

result:

ok good plan

Test #62:

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

input:

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

output:

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

result:

ok good plan

Test #63:

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

input:

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

output:

3
4
5
6
7
10
1
8
2
11
9

result:

ok good plan

Test #64:

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

input:

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

output:

5
9
11
14
18
27
30
31
34
37
38
39
41
42
44
47
48
49
51
52
54
56
57
60
61
62
64
66
67
69
70
71
72
74
76
77
79
80
82
84
85
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
65
78

result:

ok good plan

Test #65:

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

input:

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

output:

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

result:

ok good plan

Test #66:

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

input:

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

output:

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

result:

ok good plan

Test #67:

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

input:

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

output:

1
2
7
8
10
3
4
5
6
9

result:

ok good plan

Test #68:

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

input:

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

output:

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

result:

ok good plan

Test #69:

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

input:

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

output:

2
1
3

result:

ok good plan

Test #70:

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

input:

1
(

output:

impossible

result:

ok impossible

Test #71:

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

input:

1
)

output:

impossible

result:

ok impossible

Test #72:

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

input:

1
)(

output:

impossible

result:

ok impossible

Test #73:

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

input:

1
()

output:

1

result:

ok good plan

Test #74:

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

input:

2
(
)

output:

1
2

result:

ok good plan

Test #75:

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

input:

2
)
(

output:

2
1

result:

ok good plan

Test #76:

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

input:

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

output:

3
5
2
4
6
1

result:

ok good plan

Extra Test:

score: 0
Extra Test Passed