QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#68479#5108. Prehistoric Programsnocriz#AC ✓1314ms103772kbC++179.3kb2022-12-16 19:39:092022-12-16 19:39:11

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-16 19:39:11]
  • 评测
  • 测评结果:AC
  • 用时:1314ms
  • 内存:103772kb
  • [2022-12-16 19:39:09]
  • 提交

answer

//    苔花如米小,也学牡丹开。 
//    Zhikun Wang (nocriz)
//    敢问路在何方 路在脚下

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long; using db = long double; using str = string;
using pi = pair<int,int>; using pl = pair<ll,ll>; using pd = pair<db,db>;
using vi = vector<int>; using vb = vector<bool>; using vl = vector<ll>;
using vd = vector<db>; using vs = vector<str>;
using vpi = vector<pi>; using vpl = vector<pl>; using vpd = vector<pd>;

#define tcT template<class T
#define tcTU tcT, class U
tcT> using V = vector<T>;  tcT, size_t SZ> using AR = array<T,SZ>; tcT> using PR = pair<T,T>;

#define mp make_pair 
#define f first
#define s second
#define sz(x) int((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) x.rbegin(), x.rend() 
#define sor(x) sort(all(x)) 
#define rsz resize
#define ins insert 
#define ft front()
#define bk back()
#define pb push_back
#define eb emplace_back 
#define pf push_front
#define lb lower_bound
#define ub upper_bound

tcT> int lwb(V<T>& a, const T& b) { return int(lb(all(a),b)-bg(a)); }

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define each(a,x) for (auto& a: x)

const int MOD = 998244353;
const ll INF = 1e18; // not too close to LLONG_MAX
const db PI = acos((db)-1);
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1}; // for every grid problem!!
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 
template<class T> using pqg = priority_queue<T,vector<T>,greater<T>>;

constexpr int pct(int x) { return __builtin_popcount(x); } // # of bits set
constexpr int bits(int x) { return x == 0 ? 0 : 31-__builtin_clz(x); } // floor(log2(x)) 
constexpr int p2(int x) { return 1<<x; }
constexpr int msk2(int x) { return p2(x)-1; }
ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down
tcT> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
tcT> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
tcTU> T fstTrue(T lo, T hi, U f) { hi ++; assert(lo <= hi); while (lo < hi) { T mid = lo+(hi-lo)/2; f(mid) ? hi = mid : lo = mid+1; } return lo; }
tcTU> T lstTrue(T lo, T hi, U f) { lo --; assert(lo <= hi); while (lo < hi) { T mid = lo+(hi-lo+1)/2; f(mid) ? lo = mid : hi = mid-1; } return lo; }
tcT> void remDup(vector<T>& v) { sort(all(v)); v.erase(unique(all(v)),end(v)); }
tcTU> void erase(T& t, const U& u) { auto it = t.find(u); assert(it != end(t)); t.erase(it); } 
#define tcTUU tcT, class ...U
inline namespace Helpers { tcT, class = void> struct is_iterable : false_type {}; tcT> struct is_iterable<T, void_t<decltype(begin(declval<T>())), decltype(end(declval<T>())) > > : true_type {}; tcT> constexpr bool is_iterable_v = is_iterable<T>::value; tcT, class = void> struct is_readable : false_type {}; tcT> struct is_readable<T, typename std::enable_if_t< is_same_v<decltype(cin >> declval<T&>()), istream&> > > : true_type {}; tcT> constexpr bool is_readable_v = is_readable<T>::value; tcT, class = void> struct is_printable : false_type {}; tcT> struct is_printable<T, typename std::enable_if_t< is_same_v<decltype(cout << declval<T>()), ostream&> > > : true_type {}; tcT> constexpr bool is_printable_v = is_printable<T>::value;}
inline namespace Input { tcT> constexpr bool needs_input_v = !is_readable_v<T> && is_iterable_v<T>; tcTUU> void re(T& t, U&... u); tcTU> void re(pair<T,U>& p); tcT> typename enable_if<is_readable_v<T>,void>::type re(T& x) { cin >> x; } tcT> void re(complex<T>& c) { T a,b; re(a,b); c = {a,b}; } tcT> typename enable_if<needs_input_v<T>,void>::type re(T& i); tcTU> void re(pair<T,U>& p) { re(p.f,p.s); } tcT> typename enable_if<needs_input_v<T>,void>::type re(T& i) { each(x,i) re(x); } tcTUU> void re(T& t, U&... u) { re(t); re(u...); }}
inline namespace ToString {  tcT> constexpr bool needs_output_v = !is_printable_v<T> && is_iterable_v<T>;  tcT> typename enable_if<is_printable_v<T>,str>::type ts(T v) {   stringstream ss; ss << fixed << setprecision(15) << v;   return ss.str(); }  tcT> str bit_vec(T t) {   str res = "{"; F0R(i,sz(t)) res += ts(t[i]);   res += "}"; return res; }  str ts(V<bool> v) { return bit_vec(v); }  template<size_t SZ> str ts(bitset<SZ> b) { return bit_vec(b); }   tcTU> str ts(pair<T,U> p);  tcT> typename enable_if<needs_output_v<T>,str>::type ts(T v);   tcTU> str ts(pair<T,U> p) { return "("+ts(p.f)+", "+ts(p.s)+")"; }  tcT> typename enable_if<is_iterable_v<T>,str>::type ts_sep(T v, str sep) {   bool fst = 1; str res = "";   for (const auto& x: v) {    if (!fst) res += sep;    fst = 0; res += ts(x);   }   return res;  }  tcT> typename enable_if<needs_output_v<T>,str>::type ts(T v) {   return "{"+ts_sep(v,", ")+"}"; }  template<int, class T> typename enable_if<!needs_output_v<T>,vs>::type     ts_lev(const T& v) { return {ts(v)}; }  template<int lev, class T> typename enable_if<needs_output_v<T>,vs>::type     ts_lev(const T& v) {   if (lev == 0 || !sz(v)) return {ts(v)};   vs res;   for (const auto& t: v) {    if (sz(res)) res.bk += ",";    vs tmp = ts_lev<lev-1>(t);    res.ins(end(res),all(tmp));   }   F0R(i,sz(res)) {    str bef = " "; if (i == 0) bef = "{";    res[i] = bef+res[i];   }   res.bk += "}";   return res;  } }
inline namespace Output { template<class T> void pr_sep(ostream& os, str, const T& t) { os << ts(t); } template<class T, class... U> void pr_sep(ostream& os, str sep, const T& t, const U&... u) {pr_sep(os,sep,t); os << sep; pr_sep(os,sep,u...); } template<class ...T> void pr(const T&... t) { pr_sep(cout,"",t...); } void ps() { cout << "\n"; } template<class ...T> void ps(const T&... t) { pr_sep(cout," ",t...); ps(); } template<class ...T> void dbg_out(const T&... t) { pr_sep(cerr," | ",t...); cerr << endl; }void loc_info(int line, str names) { cerr << "Line(" << line << ") -> [" << names << "]: "; } template<int lev, class T> void dbgl_out(const T& t) { cerr << "\n\n" << ts_sep(ts_lev<lev>(t),"\n") << "\n" << endl; } }
#ifdef LOCAL
	#define dbg(...) loc_info(__LINE__,#__VA_ARGS__), dbg_out(__VA_ARGS__)
	#define dbgl(lev,x) loc_info(__LINE__,#x), dbgl_out<lev>(x)
#else 
	#define dbg(...) 0
	#define dbgl(lev,x) 0
#endif
void decrement() {} // subtract one from each
tcTUU> void decrement(T& t, U&... u) { --t; decrement(u...); }
#define ints(...) int __VA_ARGS__; re(__VA_ARGS__);
#define int1(...) ints(__VA_ARGS__); decrement(__VA_ARGS__);

template<int MOD, int RT> struct mint {
	static const int mod = MOD;
	static constexpr mint rt() { return RT; } // primitive root for FFT
	int v; explicit operator int() const { return v; } // explicit -> don't silently convert to int
	mint() { v = 0; }
	mint(ll _v) { v = int((-MOD < _v && _v < MOD) ? _v : _v % MOD);
		if (v < 0) v += MOD; }
	friend bool operator==(const mint& a, const mint& b) { 
		return a.v == b.v; }
	friend bool operator!=(const mint& a, const mint& b) { 
		return !(a == b); }
	friend bool operator<(const mint& a, const mint& b) { 
		return a.v < b.v; }
	friend void re(mint& a) { ll x; re(x); a = mint(x); }
	friend str ts(mint a) { return ts(a.v); }
   
	mint& operator+=(const mint& m) { 
		if ((v += m.v) >= MOD) v -= MOD; 
		return *this; }
	mint& operator-=(const mint& m) { 
		if ((v -= m.v) < 0) v += MOD; 
		return *this; }
	mint& operator*=(const mint& m) { 
		v = int((ll)v*m.v%MOD); return *this; }
	mint& operator/=(const mint& m) { return (*this) *= inv(m); }
	friend mint pow(mint a, ll p) {
		mint ans = 1; assert(p >= 0);
		for (; p; p /= 2, a *= a) if (p&1) ans *= a;
		return ans; }
	friend mint inv(const mint& a) { assert(a.v != 0); 
		return pow(a,MOD-2); }
		
	mint operator-() const { return mint(-v); }
	mint& operator++() { return *this += 1; }
	mint& operator--() { return *this -= 1; }
	friend mint operator+(mint a, const mint& b) { return a += b; }
	friend mint operator-(mint a, const mint& b) { return a -= b; }
	friend mint operator*(mint a, const mint& b) { return a *= b; }
	friend mint operator/(mint a, const mint& b) { return a /= b; }
};

typedef mint<MOD,5> mi; // 5 is primitive root for both common mods
typedef vector<mi> vmi;
typedef pair<mi,mi> pmi;
typedef vector<pmi> vpmi;

vmi facs_1926 = {1};
mi fac(int n){
	if(n<0)return 0;
	while(facs_1926.size()<n+10)
		facs_1926.pb(facs_1926.back()*facs_1926.size());
	return facs_1926[n];
}

mi C(int n,int m){
	if(n<0 || m<0 || n-m<0)return 0;
	return fac(n)/fac(m)/fac(n-m);
}


vi solve(set<pair<int,pair<int,int>>> S){
	int c = 0;
	vi ret;
	while(S.size()){
		pair<int, pi> C = *S.begin();
		S.erase(C);
		dbg(C);
		if(C.f > c){
			ps("impossible");
			exit(0);
		}
		ret.pb(C.s.s);
		c+=C.s.f;
	}
	return ret;
}

int n;
int main() {
	re(n);
	set<pair<int,pair<int,int>>> S1,S2;
	int cc = 0;
	for(int i=1;i<=n;i++){
		str s;
		re(s);
		int cnt = 0, mi = 0;
		for(auto ct:s){
		//	dbg(ct,cnt,mi);
			if(ct == '('){
				cnt+=1;
			}else{
				cnt-=1;
			}
			mi = min(mi, cnt);
		}
		cc+=cnt;
		if(cnt>0){
			S1.insert(mp(-mi,mp(cnt,i)));
		}else{
			S2.insert(mp(cnt-mi,mp(-cnt,i)));
		}
	}
	if(cc!=0){
		ps("impossible");
		exit(0);
	}
	vi ans = solve(S1);
	vi ans2 = solve(S2);
	for(auto ct:ans)ps(ct);
	reverse(all(ans2));
	for(auto ct:ans2)ps(ct);
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 54ms
memory: 8348kb

input:

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

output:

1
2
5
8
9
10
11
12
14
16
19
23
27
28
30
32
34
35
37
38
42
43
44
55
58
59
61
70
72
79
80
87
91
92
93
94
95
96
97
99
112
116
118
120
122
125
126
127
128
131
135
136
146
147
148
149
150
151
165
166
175
177
179
181
182
183
185
186
187
191
192
193
194
195
196
199
205
207
209
210
211
218
220
225
229
230
2...

result:

ok good plan

Test #2:

score: 0
Accepted
time: 6ms
memory: 3452kb

input:

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

output:

1
3
10
12
14
18
22
54
58
64
65
75
77
89
90
92
97
101
104
106
110
122
125
126
135
136
143
147
162
166
178
179
181
182
188
189
190
198
206
209
212
213
215
216
217
223
228
229
242
243
245
247
252
253
265
267
268
280
282
287
290
291
301
309
313
335
347
356
371
372
377
381
382
396
398
399
408
410
420
426...

result:

ok good plan

Test #3:

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

input:

2
()
()

output:

2
1

result:

ok good plan

Test #4:

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

input:

2
((
))

output:

1
2

result:

ok good plan

Test #5:

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

input:

2
)(
()

output:

impossible

result:

ok impossible

Test #6:

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

input:

3
()
(
)

output:

2
3
1

result:

ok good plan

Test #7:

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

input:

3
)(
(
)

output:

2
1
3

result:

ok good plan

Test #8:

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

input:

5
))(
(()
)(
(
)

output:

2
4
1
3
5

result:

ok good plan

Test #9:

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

input:

3
((
))())
(

output:

3
1
2

result:

ok good plan

Test #10:

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

input:

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

output:

impossible

result:

ok impossible

Test #11:

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

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
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
171
1...

result:

ok good plan

Test #12:

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

input:

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

output:

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

result:

ok good plan

Test #13:

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

input:

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

output:

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

result:

ok good plan

Test #14:

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

input:

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

output:

4
6
15
32
35
37
40
49
52
73
79
92
94
100
104
111
140
141
143
149
11
14
38
60
69
84
87
106
7
28
148
120
12
24
98
142
105
17
10
16
133
27
51
70
23
62
91
135
61
89
93
77
147
29
102
122
9
3
2
25
125
86
43
47
18
56
134
150
59
45
30
19
21
33
55
8
121
126
71
72
95
57
85
50
124
88
146
132
115
41
110
127
67
...

result:

ok good plan

Test #15:

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

input:

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

output:

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

result:

ok good plan

Test #16:

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

input:

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

output:

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

result:

ok good plan

Test #17:

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

input:

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

output:

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
121
136
138
141
148
150
152
155
157
159
160
162
169
172
175
176
181
182
184
185
186
191
195
208
212
213
214
220
224
225
227
228
229
231
238
243
250
255
258
259
263
264
265
281
287
294
304
324
326
330
331
333
335
338
343
3...

result:

ok good plan

Test #18:

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

input:

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

output:

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
37
48
43
25
42
95
7
63
54
99
98
97
96
93
92
90
89
85
83
80
78
77
76
75
73
72
71
69
64
58
56
55
52
49
47
45
41
40
39
36
35
34
33
30
26
24
23
21
16
15
14
13
8
5
3
2
1

result:

ok good plan

Test #19:

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

input:

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

output:

impossible

result:

ok impossible

Test #20:

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

input:

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

output:

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
41
86
51
3
56
100
81
75
4
99
97
96
93
91
90
89
88
83
82
79
78
77
74
71
67
64
63
59
58
55
54
52
50
48
45
44
40
37
36
35
34
32
31
28
27
25
24
23
20
18
17
13
10
8
2
1
85
14

result:

ok good plan

Test #21:

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

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

result:

ok good plan

Test #22:

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

input:

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

output:

impossible

result:

ok impossible

Test #23:

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

input:

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

output:

impossible

result:

ok impossible

Test #24:

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

input:

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

output:

impossible

result:

ok impossible

Test #25:

score: 0
Accepted
time: 1127ms
memory: 100888kb

input:

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

output:

2
4
5
6
8
9
13
23
28
29
30
31
36
37
38
42
44
49
52
54
55
63
65
66
69
74
77
82
86
87
88
89
90
91
94
95
98
99
100
104
106
110
111
112
117
119
120
122
135
139
140
142
143
147
149
150
151
153
156
159
164
168
170
172
177
179
180
181
183
190
193
197
200
203
207
208
212
219
220
221
223
224
225
226
227
228
...

result:

ok good plan

Test #26:

score: 0
Accepted
time: 154ms
memory: 18700kb

input:

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

output:

impossible

result:

ok impossible

Test #27:

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

input:

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

output:

impossible

result:

ok impossible

Test #28:

score: 0
Accepted
time: 146ms
memory: 18600kb

input:

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

output:

1

result:

ok good plan

Test #29:

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

input:

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

output:

impossible

result:

ok impossible

Test #30:

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

input:

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

output:

impossible

result:

ok impossible

Test #31:

score: 0
Accepted
time: 146ms
memory: 15812kb

input:

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

output:

2
1

result:

ok good plan

Test #32:

score: 0
Accepted
time: 127ms
memory: 15912kb

input:

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

output:

impossible

result:

ok impossible

Test #33:

score: 0
Accepted
time: 139ms
memory: 18644kb

input:

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

output:

3
1
2

result:

ok good plan

Test #34:

score: 0
Accepted
time: 556ms
memory: 66032kb

input:

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

output:

impossible

result:

ok impossible

Test #35:

score: 0
Accepted
time: 531ms
memory: 66040kb

input:

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

output:

impossible

result:

ok impossible

Test #36:

score: 0
Accepted
time: 1194ms
memory: 99332kb

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: 1079ms
memory: 99280kb

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: 1314ms
memory: 103772kb

input:

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

output:

11
13
21
29
37
40
49
84
87
90
102
133
154
155
159
174
181
183
191
194
215
222
223
237
240
249
250
260
269
292
294
331
335
344
351
370
373
387
394
412
442
446
452
454
491
502
506
519
540
553
573
591
603
613
617
623
626
629
633
641
657
664
668
682
688
697
701
703
723
728
732
738
769
779
805
824
830
83...

result:

ok good plan

Test #39:

score: 0
Accepted
time: 1289ms
memory: 103640kb

input:

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

output:

5
12
15
38
44
47
59
87
99
101
104
115
126
134
138
143
163
168
171
180
187
190
225
228
232
233
239
243
247
259
260
274
315
319
322
335
343
352
353
365
367
368
392
399
424
434
435
439
456
470
475
490
494
508
509
517
531
560
565
605
614
632
636
643
653
660
673
677
680
692
694
719
724
726
746
752
755
75...

result:

ok good plan

Test #40:

score: 0
Accepted
time: 147ms
memory: 3696kb

input:

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

output:

367
305
253
108
537
542
360
358
469
287
236
163
93
307
267
541
329
563
17
95
65
359
243
528
100
445
465
134
513
75
356
113
514
26
302
44
342
54
547
265
281
555
405
531
286
133
340
153
139
350
11
52
421
301
451
24
299
408
483
463
32
255
81
529
533
553
330
235
373
43
510
327
552
137
443
223
280
240
49...

result:

ok good plan

Test #41:

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

input:

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

output:

48
12
75
7
81
33
36
76
16
99
10
105
59
108
22
15
5
69
87
9
55
84
3
66
80
39
78
8
46
21
96
95
53
51
6
62
64
13
23
97
27
52
65
28
68
2
31
1
34
19
25
32
4
77
100
30
11
86
20
14
50
35
73
67
47
88
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
74
37
18
104
49
70
42
38
83...

result:

ok good plan

Test #42:

score: 0
Accepted
time: 231ms
memory: 9632kb

input:

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

output:

60
146
195
198
210
410
446
566
673
711
887
904
972
1004
1022
1241
1324
1464
1622
1702
1772
1813
1816
1862
1954
2011
2082
2305
2390
2595
2713
2830
2953
3010
3025
3088
3216
3326
3438
3750
3764
3804
3874
3978
4297
4427
4573
4647
4760
4806
4886
5059
5209
5234
5282
5360
5467
5543
5758
6086
6325
6460
6498...

result:

ok good plan

Test #43:

score: 0
Accepted
time: 990ms
memory: 78168kb

input:

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

output:

29
41
69
84
89
109
145
156
171
180
189
206
225
235
252
257
265
282
301
305
314
353
365
384
385
388
395
404
409
415
429
441
442
455
476
485
500
505
517
534
574
581
613
617
632
636
658
668
677
688
699
714
731
744
753
755
760
764
767
773
775
782
806
810
831
836
881
899
901
905
909
915
921
930
935
945
9...

result:

ok good plan

Test #44:

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

input:

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

output:

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

result:

ok good plan

Test #45:

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

input:

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

output:

6
3
7
2
1
8
5
4

result:

ok good plan

Test #46:

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

input:

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

output:

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

result:

ok good plan

Test #47:

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

input:

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

output:

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

result:

ok good plan

Test #48:

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

input:

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

output:

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

result:

ok good plan

Test #49:

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

input:

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

output:

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

result:

ok good plan

Test #50:

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

input:

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

output:

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

result:

ok good plan

Test #51:

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

input:

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

output:

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

result:

ok good plan

Test #52:

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

input:

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

output:

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

result:

ok good plan

Test #53:

score: 0
Accepted
time: 5ms
memory: 3788kb

input:

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

output:

1
4
7
8
10
12
19
22
25
26
28
31
35
46
50
57
59
60
61
63
66
70
74
79
81
85
86
88
95
105
106
107
115
118
123
125
129
135
138
139
140
145
149
153
156
164
167
169
175
181
189
196
198
200
201
206
210
212
217
226
227
231
234
236
238
240
242
244
246
252
262
267
271
272
280
281
285
288
290
292
295
299
301
3...

result:

ok good plan

Test #54:

score: 0
Accepted
time: 9ms
memory: 4216kb

input:

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

output:

1
7
8
9
12
13
16
19
20
22
23
24
26
31
33
37
38
43
45
48
51
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
122
129
134
136
137
139
140
144
146
147
148
149
151
152
153
155
161
162
163
167
168
169
171
172
173
174
175
176
177
179
181
183
184
1...

result:

ok good plan

Test #55:

score: 0
Accepted
time: 4ms
memory: 3584kb

input:

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

output:

3
6
7
10
13
24
32
33
36
37
38
42
49
51
54
56
66
75
79
83
84
87
89
92
97
105
112
121
122
123
127
136
138
140
143
146
147
148
149
155
158
159
178
179
183
196
198
201
203
209
222
226
227
228
229
230
236
253
261
266
268
273
276
284
285
291
294
296
298
305
308
316
320
322
324
331
337
346
349
353
360
362
...

result:

ok good plan

Test #56:

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

input:

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

output:

4
7
10
17
18
19
22
23
24
25
32
33
35
38
39
44
46
47
49
50
51
52
59
64
67
71
72
73
75
77
79
80
94
95
96
97
98
101
105
106
117
123
125
133
138
142
146
150
151
153
163
168
173
174
180
188
190
191
193
212
217
221
222
223
226
230
231
232
235
237
239
242
244
245
247
249
251
254
255
256
258
259
263
268
269...

result:

ok good plan

Test #57:

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

input:

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

output:

4
5
9
14
17
18
24
25
26
27
28
33
36
37
38
40
42
44
46
51
54
55
58
60
66
69
70
71
74
78
81
82
83
85
87
89
90
91
92
101
102
108
111
116
117
118
121
122
124
125
129
131
133
135
136
137
143
146
154
161
163
164
167
169
170
173
181
182
188
192
194
195
197
206
217
218
219
222
225
226
228
233
235
237
239
24...

result:

ok good plan

Test #58:

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

input:

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

output:

1
4
5
7
8
13
20
25
27
29
30
34
35
36
39
41
42
45
48
51
52
57
60
63
72
73
85
88
94
95
96
99
104
111
115
118
120
121
124
125
127
131
133
135
136
138
141
145
148
154
164
166
169
176
177
183
184
187
188
189
190
191
192
195
210
211
212
213
223
224
225
230
244
245
250
254
255
258
262
263
265
267
268
269
2...

result:

ok good plan

Test #59:

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

input:

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

output:

4
8
9
11
13
15
19
22
26
28
37
39
43
46
49
56
58
62
63
69
73
75
77
81
84
87
88
92
95
100
105
106
109
116
120
125
129
131
140
141
143
144
150
151
154
156
164
167
174
181
186
190
191
194
196
203
206
214
216
219
221
224
225
228
231
239
244
251
256
257
260
264
265
266
268
270
271
275
277
280
284
286
290
...

result:

ok good plan

Test #60:

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

input:

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

output:

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

result:

ok good plan

Test #61:

score: 0
Accepted
time: 8ms
memory: 4064kb

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
91
97
98
99
101
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
187
19...

result:

ok good plan

Test #62:

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

input:

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

output:

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
6
30
32
61
23
14
41
38
36
19
15
58
56
55
54
49
48
47
42
39
37
27
22
21
10
9
8
7
5
4
2
1
52
26
20

result:

ok good plan

Test #63:

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

input:

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

output:

3
4
5
6
7
10
8
1
11
2
9

result:

ok good plan

Test #64:

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

input:

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

output:

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

result:

ok good plan

Test #65:

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

input:

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

output:

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

result:

ok good plan

Test #66:

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

input:

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

output:

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

result:

ok good plan

Test #67:

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

input:

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

output:

2
7
8
10
1
4
9
6
5
3

result:

ok good plan

Test #68:

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

input:

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

output:

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

result:

ok good plan

Test #69:

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

input:

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

output:

2
1
3

result:

ok good plan

Test #70:

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

input:

1
(

output:

impossible

result:

ok impossible

Test #71:

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

input:

1
)

output:

impossible

result:

ok impossible

Test #72:

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

input:

1
)(

output:

impossible

result:

ok impossible

Test #73:

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

input:

1
()

output:

1

result:

ok good plan

Test #74:

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

input:

2
(
)

output:

1
2

result:

ok good plan

Test #75:

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

input:

2
)
(

output:

2
1

result:

ok good plan

Test #76:

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

input:

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

output:

5
3
2
4
6
1

result:

ok good plan

Extra Test:

score: 0
Extra Test Passed