QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#267202#5108. Prehistoric ProgramsjuampiAC ✓1141ms174704kbJava83.0kb2023-11-27 01:47:062023-11-27 01:47:07

Judging History

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

  • [2023-11-27 01:47:07]
  • 评测
  • 测评结果:AC
  • 用时:1141ms
  • 内存:174704kb
  • [2023-11-27 01:47:06]
  • 提交

answer

// Arup Guha
// 11/12/2022
// Solution to 2021 WF Problem H: Prehistoric Programs

import java.util.*;
import java.io.*;

public class h {

	public static void main(String[] args) throws Exception {
	
		BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(stdin.readLine());
		ArrayList<item> pos = new ArrayList<item>();
		ArrayList<item2> neg = new ArrayList<item2>();
		
		// Read each item.
		for (int i=0; i<n; i++) {
			char[] tmp = stdin.readLine().toCharArray();
			
			int cnt = 0, min = 0;
			for (int j=0; j<tmp.length; j++) {
				if (tmp[j] == '(') cnt++;
				else cnt--;
				min = Math.min(min, cnt);
			}
			
			// Store its id, its overall open count and the lowest it goes.
			if (cnt >= 0)
				pos.add(new item(i+1, cnt, min));
			else
				neg.add(new item2(i+1, cnt, min));
		}
		
		// Sort it.
		boolean flag = true;
		Collections.sort(pos);
		Collections.sort(neg);
	
		ArrayList<Integer> res = new ArrayList<Integer>();
		int myCnt = 0;
		
		// Positives go first.
		for (int i=0; i<pos.size(); i++) {
			
			// See if we fall below 0...
			int thisM = myCnt + pos.get(i).min;
			if (thisM < 0) { flag = false; break; }
			
			// Safe to get here...
			myCnt += pos.get(i).net;
			res.add(pos.get(i).id);
		}
		
		// Then negatives.
		for (int i=0; i<neg.size(); i++) {
			
			// See if we fall below 0...
			int thisM = myCnt + neg.get(i).min;
			if (thisM < 0) { flag = false; break; }
			
			// Safe to get here...
			myCnt += neg.get(i).net;
			res.add(neg.get(i).id);
		}
		
		// Last check.
		if (myCnt != 0) flag=false;
		
		// Can't work...
		if (!flag)
			System.out.println("impossible");
		
		// This is valid, print it.
		else {
			StringBuffer sb = new StringBuffer();
			for (int i=0; i<n; i++) sb.append(res.get(i)+"\n");
			System.out.print(sb);
		}
	}
}

class item implements Comparable<item> {

	public int id;
	public int net;
	public int min;
	
	public item(int myid, int netSum, int minCnt) {
		id = myid;
		net = netSum;
		min = minCnt;
	}
	
	// This one's easy, sort by minimum...these will build up open brackets.
	// If you can't build up open brackets to "handle" mins, then it can't be done.
	public int compareTo(item other) {
		if (this.min != other.min) return other.min - this.min;
		return other.net - this.net;
	}
}

class item2 implements Comparable<item2> {

	public int id;
	public int net;
	public int min;
	public int diff;
	
	public item2(int myid, int netSum, int minCnt) {
		id = myid;
		net = netSum;
		min = minCnt;
		diff = min - net;
	}
	
	// This one's trickier. We want the last items to be all closes in some sense,
	// so if I look for difference between min and the net count, and put the ones
	// last with these two values the same (all closes), we'll be safe.
	public int compareTo(item2 other) {
		if (this.diff != other.diff) return this.diff - other.diff;
		return other.net - this.net;		
	}

}

详细

Test #1:

score: 100
Accepted
time: 230ms
memory: 62880kb

input:

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

output:

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

result:

ok good plan

Test #2:

score: 0
Accepted
time: 72ms
memory: 42196kb

input:

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

output:

36
13
66
386
966
585
286
257
83
127
39
476
595
214
329
598
814
907
62
427
981
131
384
662
707
511
793
807
80
271
379
449
638
767
869
20
239
327
387
422
474
632
746
31
88
168
171
296
334
345
473
502
535
553
715
915
919
975
989
17
33
60
98
134
164
177
208
258
316
324
390
406
414
464
481
563
566
575
60...

result:

ok good plan

Test #3:

score: 0
Accepted
time: 33ms
memory: 37588kb

input:

2
()
()

output:

1
2

result:

ok good plan

Test #4:

score: 0
Accepted
time: 44ms
memory: 37716kb

input:

2
((
))

output:

1
2

result:

ok good plan

Test #5:

score: 0
Accepted
time: 39ms
memory: 38848kb

input:

2
)(
()

output:

impossible

result:

ok impossible

Test #6:

score: 0
Accepted
time: 24ms
memory: 39708kb

input:

3
()
(
)

output:

2
1
3

result:

ok good plan

Test #7:

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

input:

3
)(
(
)

output:

2
1
3

result:

ok good plan

Test #8:

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

input:

5
))(
(()
)(
(
)

output:

2
4
3
1
5

result:

ok good plan

Test #9:

score: 0
Accepted
time: 44ms
memory: 37952kb

input:

3
((
))())
(

output:

1
3
2

result:

ok good plan

Test #10:

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

input:

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

output:

impossible

result:

ok impossible

Test #11:

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

input:

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

output:

311
329
479
199
232
443
483
80
177
211
253
265
297
350
357
414
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
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
13...

result:

ok good plan

Test #12:

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

input:

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

output:

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

result:

ok good plan

Test #13:

score: 0
Accepted
time: 48ms
memory: 37200kb

input:

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

output:

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

result:

ok good plan

Test #14:

score: 0
Accepted
time: 46ms
memory: 39328kb

input:

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

output:

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

result:

ok good plan

Test #15:

score: 0
Accepted
time: 55ms
memory: 38636kb

input:

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

output:

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

result:

ok good plan

Test #16:

score: 0
Accepted
time: 46ms
memory: 37704kb

input:

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

output:

129
50
131
84
115
27
117
45
52
75
92
122
130
140
8
30
36
48
55
58
60
65
67
74
81
93
97
99
106
108
110
111
118
123
136
149
5
68
89
98
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
133
107
37
32
43
12
90
78
44
112
61
7
64
109
125
85
72
144
41
22
20
28
95
16...

result:

ok good plan

Test #17:

score: 0
Accepted
time: 70ms
memory: 40960kb

input:

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

output:

468
163
379
390
204
396
707
585
590
1
4
122
405
601
657
658
34
79
104
180
274
158
473
25
108
149
269
485
504
526
547
571
681
705
730
41
43
55
56
103
131
156
164
166
218
230
246
341
382
395
406
408
418
426
481
494
530
606
7
9
13
16
17
20
21
22
27
37
45
48
57
62
65
66
67
69
74
81
82
95
97
101
112
116
...

result:

ok good plan

Test #18:

score: 0
Accepted
time: 46ms
memory: 38024kb

input:

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

output:

43
37
48
4
6
9
10
11
12
17
18
19
20
22
27
28
29
31
32
38
44
46
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
8
13
14
15
16
21
23
24
26
30
33
34
35
36
39
40
41
45
47
49
52
55
56
58
64
69
71
72
73
75
76
77
78
80
83
85
89
90
92
93
96
97
98
99
54
63
7

result:

ok good plan

Test #19:

score: 0
Accepted
time: 46ms
memory: 38384kb

input:

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

output:

impossible

result:

ok impossible

Test #20:

score: 0
Accepted
time: 44ms
memory: 38080kb

input:

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

output:

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

result:

ok good plan

Test #21:

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

input:

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

output:

60
78
79
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
65
73
75
77
80
82
83
85
95
96
97
98
14
69
88
15
76
93
99
66
92
3
5
10
11
12
13
16
17
20
23
24
25
27
32
34
39
40
43
44
47
50
51
57
61
62
63
67
68
70
71
72
81
84
86
87
89
90
91
94
100
74
30
64

result:

ok good plan

Test #22:

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

input:

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

output:

impossible

result:

ok impossible

Test #23:

score: 0
Accepted
time: 51ms
memory: 39036kb

input:

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

output:

impossible

result:

ok impossible

Test #24:

score: 0
Accepted
time: 72ms
memory: 40624kb

input:

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

output:

impossible

result:

ok impossible

Test #25:

score: 0
Accepted
time: 1066ms
memory: 170204kb

input:

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

output:

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

result:

ok good plan

Test #26:

score: 0
Accepted
time: 164ms
memory: 153560kb

input:

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

output:

impossible

result:

ok impossible

Test #27:

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

input:

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

output:

impossible

result:

ok impossible

Test #28:

score: 0
Accepted
time: 164ms
memory: 153812kb

input:

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

output:

1

result:

ok good plan

Test #29:

score: 0
Accepted
time: 177ms
memory: 151904kb

input:

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

output:

impossible

result:

ok impossible

Test #30:

score: 0
Accepted
time: 186ms
memory: 153676kb

input:

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

output:

impossible

result:

ok impossible

Test #31:

score: 0
Accepted
time: 251ms
memory: 102508kb

input:

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

output:

2
1

result:

ok good plan

Test #32:

score: 0
Accepted
time: 236ms
memory: 101760kb

input:

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

output:

impossible

result:

ok impossible

Test #33:

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

input:

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

output:

3
1
2

result:

ok good plan

Test #34:

score: 0
Accepted
time: 288ms
memory: 126436kb

input:

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

output:

impossible

result:

ok impossible

Test #35:

score: 0
Accepted
time: 248ms
memory: 112304kb

input:

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

output:

impossible

result:

ok impossible

Test #36:

score: 0
Accepted
time: 610ms
memory: 166676kb

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: 666ms
memory: 174704kb

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: 1141ms
memory: 169736kb

input:

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

output:

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

result:

ok good plan

Test #39:

score: 0
Accepted
time: 1097ms
memory: 169188kb

input:

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

output:

250826
568499
494698
629151
675014
425960
536620
795023
985988
106383
300744
463859
561779
926090
137311
575206
597972
689231
129338
207485
333208
353729
388609
427235
746420
930603
963161
116108
123122
470327
487205
623824
696104
770416
834142
905927
997127
12900
60394
77139
104949
122925
123227
18...

result:

ok good plan

Test #40:

score: 0
Accepted
time: 241ms
memory: 76476kb

input:

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

output:

163
236
287
469
358
360
542
537
108
253
305
367
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: 0
Accepted
time: 232ms
memory: 76304kb

input:

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

output:

12
48
75
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
21
95
96
53
51
6
62
64
13
23
97
27
52
65
28
68
2
88
31
1
34
19
25
32
4
77
100
30
11
86
20
14
50
73
35
67
47
58
56
94
26
103
91
17
54
101
107
109
93
63
82
24
92
57
98
60
40
79
41
71
102
106
37
74
18
104
49
42
38
83...

result:

ok good plan

Test #42:

score: 0
Accepted
time: 375ms
memory: 78756kb

input:

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

output:

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

result:

ok good plan

Test #43:

score: 0
Accepted
time: 959ms
memory: 152964kb

input:

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

output:

204843
504790
42954
343862
399438
63131
118929
498212
562227
85220
87230
235660
329734
386793
400919
25279
53936
121461
298959
323865
607247
616123
678888
203448
216616
316054
322499
362444
382031
417795
422036
430469
485491
538238
665377
701764
723227
8477
16430
56019
74820
82698
85379
167630
16826...

result:

ok good plan

Test #44:

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

input:

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

output:

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

result:

ok good plan

Test #45:

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

input:

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

output:

6
3
7
2
1
4
5
8

result:

ok good plan

Test #46:

score: 0
Accepted
time: 44ms
memory: 38476kb

input:

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

output:

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

result:

ok good plan

Test #47:

score: 0
Accepted
time: 44ms
memory: 37536kb

input:

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

output:

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

result:

ok good plan

Test #48:

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

input:

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

output:

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

result:

ok good plan

Test #49:

score: 0
Accepted
time: 47ms
memory: 38492kb

input:

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

output:

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

result:

ok good plan

Test #50:

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

input:

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

output:

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

result:

ok good plan

Test #51:

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

input:

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

output:

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

result:

ok good plan

Test #52:

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

input:

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

output:

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

result:

ok good plan

Test #53:

score: 0
Accepted
time: 66ms
memory: 41932kb

input:

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

output:

2709
883
1378
1426
1641
1969
2952
3074
3641
183
193
540
549
731
1129
1153
1706
2001
2067
2168
2202
2241
2860
3325
3356
3417
3670
41
48
87
136
202
213
256
335
401
413
473
481
485
507
575
587
602
610
622
646
679
700
783
806
877
919
967
1037
1072
1158
1186
1209
1291
1300
1334
1382
1383
1407
1414
1521
1...

result:

ok good plan

Test #54:

score: 0
Accepted
time: 90ms
memory: 41992kb

input:

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

output:

515
2024
4898
4936
7172
7337
7783
15
44
47
53
121
158
160
165
187
258
367
383
464
529
532
564
645
701
707
777
796
811
840
856
958
968
1041
1110
1153
1169
1200
1212
1337
1382
1558
1601
1607
1621
1626
1627
1647
1749
1802
1853
1941
1956
2060
2090
2113
2149
2226
2279
2455
2474
2646
2647
2664
2797
2810
2...

result:

ok good plan

Test #55:

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

input:

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

output:

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

result:

ok good plan

Test #56:

score: 0
Accepted
time: 61ms
memory: 41228kb

input:

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

output:

1004
2854
3163
3255
695
708
857
1147
1316
1463
1718
1720
1789
1929
2091
2498
2653
2920
3052
3432
3673
3759
63
82
107
165
167
384
584
652
739
775
777
778
821
854
856
911
918
928
1047
1179
1278
1369
1370
1393
1451
1509
1520
1580
1584
1599
1618
1757
1836
1862
1884
2027
2113
2180
2183
2211
2307
2485
257...

result:

ok good plan

Test #57:

score: 0
Accepted
time: 61ms
memory: 40932kb

input:

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

output:

3496
3932
180
2783
4856
12
210
294
412
561
1183
1657
1860
2293
2518
2771
2804
2813
3143
3268
3785
3979
4437
4937
39
61
126
144
323
342
361
441
476
491
505
567
698
779
863
1026
1071
1124
1173
1231
1465
1570
1606
1655
1710
1758
1825
1928
2083
2100
2237
2305
2315
2387
2437
2438
2458
2487
2625
2676
2685...

result:

ok good plan

Test #58:

score: 0
Accepted
time: 55ms
memory: 39868kb

input:

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

output:

24
208
206
633
974
1199
2109
2388
3153
66
80
144
167
259
368
377
620
639
640
701
714
717
885
926
980
1031
1175
1187
1273
1353
1401
1413
1437
1652
1654
1668
1782
1799
1827
1848
1887
1890
2076
2283
2445
2463
2464
2632
2642
2751
2823
2950
3066
3267
3344
3358
3361
16
21
40
53
79
108
134
142
171
201
205
...

result:

ok good plan

Test #59:

score: 0
Accepted
time: 59ms
memory: 40252kb

input:

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

output:

253
2233
3246
76
278
708
1932
1962
2547
2585
2781
2926
3461
148
218
246
299
484
793
930
1092
1100
1173
1197
1213
1515
1566
1836
1886
2079
2166
2372
2436
2440
2447
2571
2711
2767
2890
3209
3320
3476
3954
3957
38
59
67
79
115
180
202
248
255
289
331
341
391
415
478
550
621
635
658
679
688
712
759
800
...

result:

ok good plan

Test #60:

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

input:

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

output:

98
106
68
66
73
102
125
105
22
122
110
6
7
69
95
97
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
70
63
28
64
103
93
124
44
61
80
23
75
83
100
67
45
43
120
119
13
42
24
88
41
114
54
19
53
85
104
59
21
17
60
32
8
26
30
81
99
101
57
12
37
49
1
31
79
82
46
52
2...

result:

ok good plan

Test #61:

score: 0
Accepted
time: 77ms
memory: 41216kb

input:

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

output:

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

result:

ok good plan

Test #62:

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

input:

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

output:

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

result:

ok good plan

Test #63:

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

input:

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

output:

3
4
5
6
9
7
10
8
1
2
11

result:

ok good plan

Test #64:

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

input:

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

output:

9
18
5
11
14
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
65
78
1
2
3
4
6
7
8
10
12
13
15
16
17
19
20
21
22
23
24
25
26
28
29
32
33
35
36
40
43
45
46
50
53
55
58
59
63
68
73
75
81
83
86

result:

ok good plan

Test #65:

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

input:

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

output:

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

result:

ok good plan

Test #66:

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

input:

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

output:

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

result:

ok good plan

Test #67:

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

input:

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

output:

1
2
7
8
10
3
5
6
9
4

result:

ok good plan

Test #68:

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

input:

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

output:

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

result:

ok good plan

Test #69:

score: 0
Accepted
time: 48ms
memory: 37888kb

input:

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

output:

2
1
3

result:

ok good plan

Test #70:

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

input:

1
(

output:

impossible

result:

ok impossible

Test #71:

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

input:

1
)

output:

impossible

result:

ok impossible

Test #72:

score: 0
Accepted
time: 44ms
memory: 38576kb

input:

1
)(

output:

impossible

result:

ok impossible

Test #73:

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

input:

1
()

output:

1

result:

ok good plan

Test #74:

score: 0
Accepted
time: 33ms
memory: 39160kb

input:

2
(
)

output:

1
2

result:

ok good plan

Test #75:

score: 0
Accepted
time: 44ms
memory: 38492kb

input:

2
)
(

output:

2
1

result:

ok good plan

Test #76:

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

input:

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

output:

3
5
1
2
6
4

result:

ok good plan

Extra Test:

score: 0
Extra Test Passed