QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#238247#7683. Hard Brackets Problemucup-team988#AC ✓54ms4736kbC++171.8kb2023-11-04 16:12:212023-11-04 16:12:22

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3648kb

input:

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

output:

((()))
impossible
)))()

result:

ok 3 cases (3 test cases)

Test #2:

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

input:

100000
())(()()()
()())()))
)()()()()
())()(())(
((())()))
)(())()))(
)()))())))
)))))(((()
()))((()((
()((()()))
(()())())
())(()))()
(())(())))
))))(()(()
()))(())((
()((())())
()))()))()
()((())())
()()))((()
()))(()))
(()(())))
())((()))
())()((())
(()(())))
()(((()())
))))())))(
((((()()()
(()(...

output:

impossible
()())()))
)()()()()
impossible
((())()))
impossible
)()))())))
impossible
impossible
()((()()))
(()())())
())(()))()
(())(())))
impossible
impossible
()((())())
()))()))()
()((())())
impossible
()))(()))
(()(())))
())((()))
impossible
(()(())))
impossible
impossible
impossible
impossible
...

result:

ok 100000 cases (100000 test cases)

Test #3:

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

input:

200000
(()))
()))(
)()))
(())
)((((
)(())
)(())
()))(
((()(
()(()
))())
)((((
()())
(())
()(()
(()()
)(())
()))
(()()
()())
(())
()()(
(()((
)())
(()()
(())
))(((
(())
())()
())()
(()))
(((((
)())
(()))
()(()
)()()
(()))
()())
(()))
)(())
(())(
))))(
())((
))(((
))))(
()()
()())
(())
(())
(())
)(())...

output:

(()))
impossible
)()))
(())
impossible
)(())
)(())
impossible
impossible
impossible
))())
impossible
()())
(())
impossible
impossible
)(())
()))
impossible
()())
(())
impossible
impossible
)())
impossible
(())
impossible
(())
())()
())()
(()))
impossible
)())
(()))
impossible
)()()
(()))
()())
(()))...

result:

ok 200000 cases (200000 test cases)

Test #4:

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

input:

250000
()()
(())
())
)(((
(()(
(())
)()
(())
(())
))()
)(()
)())
)())
(())
)())
()))
())
(()(
))))
()((
()()
)())
())
())
())
(())
))()
(())
(()(
)))(
()))
())
)))(
)(()
()))
()()
(())
((()
(())
))((
))((
(())
()))
(()(
(())
((()
)(()
(())
((((
())
))()
())
()()
)()(
)()
(())
))()
()))
())
)()
)())
...

output:

()()
(())
())
impossible
impossible
(())
)()
(())
(())
))()
impossible
)())
)())
(())
)())
()))
())
impossible
))))
impossible
()()
)())
())
())
())
(())
))()
(())
impossible
impossible
()))
())
impossible
impossible
()))
()()
(())
impossible
(())
impossible
impossible
(())
()))
impossible
(())
impo...

result:

ok 250000 cases (250000 test cases)

Test #5:

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

input:

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

output:

impossible
impossible
impossible
impossible
()(())()()()((())))
impossible
((())(()()))()(()())
impossible
))(((())(())()))())
impossible
((())()))))(((()))))
()()(())((()(()))))
()())())))()()(()))
()))(())()())()(())
impossible
)))))(())()())((()))
impossible
)(((()())()(())()))
impossible
impossi...

result:

ok 50000 cases (50000 test cases)

Test #6:

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

input:

83333
((()((())(()
(())(()()))
()(()(())))
((((())))))
)())(((())))
()()())()())
()()((())))
(()(()(((())
()((()()()()
(()()()())))
(()()()(((()
)))))()()())
)((()()())))
))(((()))))
()())(()))()
)()))))()())
)(()((())))(
(()())(()))
())()((())))
(()()()(()))
)())()()(())
((())()))(()
(()(()(((())
)...

output:

impossible
(())(()()))
()(()(())))
((((())))))
)())(((())))
()()())()())
()()((())))
impossible
impossible
(()()()())))
impossible
)))))()()())
)((()()())))
))(((()))))
()())(()))()
)()))))()())
impossible
(()())(()))
())()((())))
(()()()(()))
)())()()(())
impossible
impossible
impossible
impossible...

result:

ok 83333 cases (83333 test cases)

Test #7:

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

input:

250000
)))
)(((
()()
((()
((()
())
())(
))((
)())
()()
()()
())
((()
())
()()
(())
(())
()()
()))
())
)())
()()
)()
())
)()(
(())
)()
)(((
))()
(())
)()
)())
)()
)()
))((
()()
(())
()((
))((
)(((
()))
)())
)())
)())
)())
)(((
())
)))
(())
(())
())(
())
(())
(())
()()
())(
()()
())
))()
(())
(())
)()...

output:

)))
impossible
()()
impossible
impossible
())
impossible
impossible
)())
()()
()()
())
impossible
())
()()
(())
(())
()()
()))
())
)())
()()
)()
())
impossible
(())
)()
impossible
))()
(())
)()
)())
)()
)()
impossible
()()
(())
impossible
impossible
impossible
()))
)())
)())
)())
)())
impossible
())...

result:

ok 250000 cases (250000 test cases)

Test #8:

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

input:

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

output:

impossible
()()()((((()())())))
(())(()()()((())))()
(())(()))(()(()()))
()((((()((())))))))
impossible
impossible
()()())())(((()())))
(())(())))(()((())))
impossible
()()()((()(()()))))
)(())))()(())()())()
impossible
)()())(()((()(()))))
(())(()()())()())())
)())()()()()((())())
(())()((())((()))...

result:

ok 50000 cases (50000 test cases)

Test #9:

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

input:

83333
((()(())))()
()))()()))()
()))()))())(
())(())))())
)()))))(((((
)(()(()())((
(()))(())())
)()()()(()()
((()())((())
)())()()(()(
()(())()())
)(()(())())
()(())(()))
))()(()(())(
()((()())))
)()(((())))
)())()())))
(((()()())))
()())()())()
()())(())()
)()((()())((
(()()((((())
(())))()()))
((...

output:

((()(())))()
()))()()))()
impossible
())(())))())
impossible
impossible
(()))(())())
impossible
impossible
impossible
()(())()())
)(()(())())
()(())(()))
impossible
()((()())))
)()(((())))
)())()())))
(((()()())))
()())()())()
()())(())()
impossible
impossible
(())))()()))
((((())))))
impossible
())...

result:

ok 83333 cases (83333 test cases)

Test #10:

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

input:

250000
)())
()))
())(
(())
()()
())
))((
())
)()
())
()((
()))
(())
)(((
())
(())
))()
)())
(()(
)()
((((
()))
)))(
(()(
()()
))))
)())
()()
((()
)(((
()()
(())
)(()
()()
)()
)))(
())
())(
())
)))(
))()
())
)())
))((
())
()))
((()
)()(
)()
()))
())
)())
(())
(()(
()()
()))
()))
)))(
()))
)()
())
())...

output:

)())
()))
impossible
(())
()()
())
impossible
())
)()
())
impossible
()))
(())
impossible
())
(())
))()
)())
impossible
)()
impossible
()))
impossible
impossible
()()
))))
)())
()()
impossible
impossible
()()
(())
impossible
()()
)()
impossible
())
impossible
())
impossible
))()
())
)())
impossible
...

result:

ok 250000 cases (250000 test cases)

Test #11:

score: 0
Accepted
time: 7ms
memory: 3644kb

input:

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

output:

(())(()(()(())))())
())()()))(())()()())
())()())((()(()))))
()(()()))(()((())))
impossible
()(())())())(()))())
((()((()((())))())))
())()))()()()())))))
(((()()))))))()(())
impossible
impossible
(()())(()(()))())))
()()))))(()(()()()))
())()())(((()(()))))
()((()(()))()(())))
impossible
()))())(()...

result:

ok 50000 cases (50000 test cases)

Test #12:

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

input:

83333
())()))))(()
(()((()(()))
((((((()())(
())(((((()))
((())((())))
)())())))))(
()(((())((()
()(((()))))
(()))((()))
)(())())((((
)()()()(())
)(()))(())))
)(((()())))
)(())(()()))
(())))(()))(
(((((()))))(
))((()()())(
(((()))())()
(((()()((())
())))))(((((
()((((()))))
)()(()))(())
(()))(()()))...

output:

impossible
impossible
impossible
impossible
((())((())))
impossible
impossible
()(((()))))
(()))((()))
impossible
)()()()(())
)(()))(())))
)(((()())))
)(())(()()))
impossible
impossible
impossible
(((()))())()
impossible
impossible
()((((()))))
)()(()))(())
(()))(()()))
)())))()()))
impossible
(())(...

result:

ok 83333 cases (83333 test cases)

Test #13:

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

input:

250000
(())
((((
(())
())
()()
(())
(())
())
))()
(())
))()
(())
()))
))))
(())
()))
()))
())
)()(
)))
)())
(())
(())
))()
(())
())
()))
))()
))((
)()
()()
)(((
(())
()()
)()
)(()
())
)())
((()
))()
)(((
()))
())
())
)())
()))
)())
(())
))()
))))
)())
())
))()
)()(
))))
((((
())
(())
)()
)())
())
()...

output:

(())
impossible
(())
())
()()
(())
(())
())
))()
(())
))()
(())
()))
))))
(())
()))
()))
())
impossible
)))
)())
(())
(())
))()
(())
())
()))
))()
impossible
)()
()()
impossible
(())
()()
)()
impossible
())
)())
impossible
))()
impossible
()))
())
())
)())
()))
)())
(())
))()
))))
)())
())
))()
impo...

result:

ok 250000 cases (250000 test cases)

Test #14:

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

input:

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

output:

impossible
)((())((()()))(())))
()(()(()))()(()()))
((()())()())(()(()))
)()()(())())()(())()
(()(()(((())))()()))
impossible
()()()()(())(((())))
impossible
((())((()()(())))))
(((((()()()(()))))))
())())))())())()(())
((())((((((())))))))
((())()())())()()())
()((((()(((())))))))
()())(((()))((())...

result:

ok 50000 cases (50000 test cases)

Test #15:

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

input:

83333
)))((())(()(
()((()))())
(()))()(()((
))((()()(()(
(()))()()))
)))()()(()((
)(()))()()((
())((()))))
(())))()())
)(()()))(()(
()(()()))()
()))())())((
((()(()())))
(((())()()()
()(())(()())
))())((()))
())((()()(()
))(()((())))
((((()()))))
(()((())())(
)()())(())()
))(()())()))
(()(())(()()
(...

output:

impossible
()((()))())
impossible
impossible
(()))()()))
impossible
impossible
())((()))))
(())))()())
impossible
()(()()))()
impossible
((()(()())))
impossible
()(())(()())
))())((()))
impossible
))(()((())))
((((()()))))
impossible
)()())(())()
))(()())()))
impossible
())(())()()
impossible
imposs...

result:

ok 83333 cases (83333 test cases)

Test #16:

score: 0
Accepted
time: 7ms
memory: 4724kb

input:

1
(()()((((())))(((((((())(()())())()(()((()(((()(()))))())((())((())((()))()())(()))()))((())()())))()())()(()((())(((()()(((())(((()))(((()())((()(((()())()())(()(()(())()()())())(((((((()((((()))()())())((((()(()())()())))((()((((()(((((()((((())()(()(()((((()()(((())())())))(())))))))))((((()(()...

output:

impossible

result:

ok 1 cases (1 test case)

Test #17:

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

input:

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

output:

())())()()(((()))()(((()())(())))))((()((()()()()()())(()((((()))()()((())()()((()))()())(())))(()(())(()()())(())))()())((((()()(()))((())()(())))))(((()(((((()(())()()((())))))(()(()())))))((())))))())())()()(()(()()))(((()))(()())))(())()))()())()()())()((()((()())())))())())((()((()())())(((()))...

result:

ok 2 cases (2 test cases)

Test #18:

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

input:

1
()(()(()))()()()((()())(())())())()(())(()()(()))(())()()()((()(()(())(()()(()((((()()))))))())((()))))((())((((()))(((((()(()))(((())((()))()()((()(()((()((()()()))(())))(())())()()))))((((()(())))))((()(()((()()())())())(()())(()()))()((((()))())()(((()(())))()()((((()))))()))()()))))((())((()((...

output:

()(()(()))()()()((()())(())())())()(())(()()(()))(())()()()((()(()(())(()()(()((((()()))))))())((()))))((())((((()))(((((()(()))(((())((()))()()((()(()((()((()()()))(())))(())())()()))))((((()(())))))((()(()((()()())())())(()())(()()))()((((()))())()(((()(())))()()((((()))))()))()()))))((())((()(()(...

result:

ok 1 cases (1 test case)

Test #19:

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

input:

1
()((()(((()))(())()())((()((()))((()()((()())(())())())(()()()()())(())(()((()(((())()((()((((((((())(()))))(((()()(()))(((()()())(()()(())))((((())()(()((()(())))()((())((((())())(()()()(()())((())(((()(((()))((()((()(()))))))())((())))((()))(((())))))))())(((((()(((())))(()())()()(())()(())(()()...

output:

()((()(((()))(())()())((()((()))((()()((()())(())())())(()()()()())(())(()((()(((())()((()((((((((())(()))))(((()()(()))(((()()())(()()(())))((((())()(()((()(())))()((())((((())())(()()()(()())((())(((()(((()))((()((()(()))))))())((())))((()))(((())))))))())(((((()(((())))(()())()()(())()(())(()())(...

result:

ok 1 cases (1 test case)

Test #20:

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

input:

1
)()((((())()))(())()))()(()))()())()(((()()(()(())))(()(((()))(((()()()))())))(())())()))(()((()))())()()()((((()))())))())((()())(()())))(((()(())()((()())(()((((())))(())))(()(())())(())(()()))(()((((()(())((())()()(((())()))(((()))(()(())(()()()()()()(())(((()()()(()(()(()))(()()))(((()((()()((...

output:

)()((((())()))(())()))()(()))()())()(((()()(()(())))(()(((()))(((()()()))())))(())())()))(()((()))())()()()((((()))())))())((()())(()())))(((()(())()((()())(()((((())))(())))(()(())())(())(()()))(()((((()(())((())()()(((())()))(((()))(()(())(()()()()()()(())(((()()()(()(()(()))(()()))(((()((()()(())...

result:

ok 1 cases (1 test case)

Test #21:

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

input:

1
())((()())()(((((()(((())()))((((()()))))))()())())(()())(())))())()((((()((()))))(()))))(((()(())((()()(()()(()))))()())))()))()(((())(()))))()()()(((((((())))(((()()))(())(()()))()))())))(((()((()())()()(((()()(((((((((())(()(())))(())()((()))))()((((())()(((()))))(()(())())(((()()(((((()(((()((...

output:

())((()())()(((((()(((())()))((((()()))))))()())())(()())(())))())()((((()((()))))(()))))(((()(())((()()(()()(()))))()())))()))()(((())(()))))()()()(((((((())))(((()()))(())(()()))()))())))(((()((()())()()(((()()(((((((((())(()(())))(())()((()))))()((((())()(((()))))(()(())())(((()()(((((()(((()(())...

result:

ok 1 cases (1 test case)

Test #22:

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

input:

1
(()))())(())((()(()())())))())(()((((())))())())(()((()(()(()((((()))()())()))(((()())()))((())))))))()())()))((()))()()()))())))()(())())(()(()()()(()((()))))((())))((((())()((())))())())()))()()))))()())(()))()(())(((()))))()))(()(()((()(()(((((()(())))(())(()))()()())))))()()))(((()())(())))(()...

output:

(()))())(())((()(()())())))())(()((((())))())())(()((()(()(()((((()))()())()))(((()())()))((())))))))()())()))((()))()()()))())))()(())())(()(()()()(()((()))))((())))((((())()((())))())())()))()()))))()())(()))()(())(((()))))()))(()(()((()(()(((((()(())))(())(()))()()())))))()()))(((()())(())))(()))...

result:

ok 1 cases (1 test case)

Test #23:

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

input:

1
()((()(()(()))())(())(()())((()))()()))(())(()))()((((()(()))))((())))())())()((()(()(()())(())())))(((((()(()(((()))()()))(()()((()))))((())()))))(()())(((())))))(((())((()))((((())()))))()()()))()()()()(())()((()))(()()(()()((())(((()(()()()))))())((((())(((()(((((()()()()))))()))))()((()))))))(...

output:

()((()(()(()))())(())(()())((()))()()))(())(()))()((((()(()))))((())))())())()((()(()(()())(())())))(((((()(()(((()))()()))(()()((()))))((())()))))(()())(((())))))(((())((()))((((())()))))()()()))()()()()(())()((()))(()()(()()((())(((()(()()()))))())((((())(((()(((((()()()()))))()))))()((()))))))(()...

result:

ok 1 cases (1 test case)

Test #24:

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

input:

1
(((()((())((((()(((((()())())))())(((())()(()(()())()((())())))()(()(()())())()()())((()))()())))()(((())()))(())(()((()))))()()(())((()((()(()))))())))))(()(((((((()())))((((())))))(((())())(()))(()(()))((((((()((()()()(()())())())(()(()())))())(((()()()((())))(()()()()()((())())))(())))()()(())(...

output:

(((()((())((((()(((((()())())))())(((())()(()(()())()((())())))()(()(()())())()()())((()))()())))()(((())()))(())(()((()))))()()(())((()((()(()))))())))))(()(((((((()())))((((())))))(((())())(()))(()(()))((((((()((()()()(()())())())(()(()())))())(((()()()((())))(()()()()()((())())))(())))()()(())())...

result:

ok 1 cases (1 test case)

Test #25:

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

input:

1
)))()())(()()()))(((((((((())(()(())()()()))(((()))()))()((())(()(())))())))(((()(())(()))(()(()(()))(())))((()))(()()())()((((())((())))()())))))(()())())))()()(((())()))())(()))((((())((((((())(()((((((()(()(()((()(((())()(()))()(()(((()))()(()(()()((((((()()))())())()))()(()(())))(()()))()(((((...

output:

)))()())(()()()))(((((((((())(()(())()()()))(((()))()))()((())(()(())))())))(((()(())(()))(()(()(()))(())))((()))(()()())()((((())((())))()())))))(()())())))()()(((())()))())(()))((((())((((((())(()((((((()(()(()((()(((())()(()))()(()(((()))()(()(()()((((((()()))())())()))()(()(())))(()()))()((((()(...

result:

ok 1 cases (1 test case)

Test #26:

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

input:

1
)((((())()(()))(())))))())())()(()))(((()))(()())))(((()((((()(()))))(((()))((((()((()(())))))())()(((((()()))(()((()(()((()()()(())))()))(((()()))()()((((()()(((()(()))())(((()())(()(())((()(()((())()))())())(((((((()))()))())(((()(())))()())(())()())(()))((((())(())))((())((())(((())))()()(()())...

output:

impossible

result:

ok 1 cases (1 test case)

Test #27:

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

input:

1
((())(())(())))((())))()()()((())))((((()()(((()()))))()()()()(((())((()((()))(((((())(())(()())))))))((((()))))())()))((()(((((())))))(()())())))(()(()))(((()((())((()()())(()()((()()()))((((((((()))))(()(()))()((()()())(((())(((())())()))()(((()((((()((())()(()((()(()((((())))(((()))())((((())()...

output:

impossible

result:

ok 1 cases (1 test case)

Test #28:

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

input:

1
)()()((())))))()()())))(()))()(()(())()))))())()(()(()()(((())()))))(())((())()))))))((()()()))()(()(()))))()()()(()()))))())())))))))(((()(())()()))))((()()(((((()(((())())(()(())(())))(()))()()))())((((((((((())(()(()))(()()()()(())(())(()(((()(()))()((()(()))((((())(()()()((()(())))((())((())((...

output:

impossible

result:

ok 1 cases (1 test case)

Test #29:

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

input:

1
(()))(()(()())())(((())()())((())))(())))))))((())()))))())()()))()()))))))())())((()))))))()()()))()())(())))()()(((())())(((())))(()()()(((()((()())))(()))())))))()))(())(())(()))(()()())))()))(((()))(()())))()(((()(((()()))(())()()))()(()()())()()(((((()()()))())))()((())()))(()((()()()()((((((...

output:

impossible

result:

ok 1 cases (1 test case)

Test #30:

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

input:

1
(((()))(()((())()(())()()())()(())()()()()))()(()()))(())(())(())((())(((())(()()))())()))(()((((((())()))(((()))))))()(((()()(())))()()(())))()))()(()())()((()((((()()())()((((((())((((((((())(()()()(()))(((()(()(((((())((()))(((((()(()(((()()(()(())()()((((())))(()))(())())))(())))((((()))()))()...

output:

(((()))(()((())()(())()()())()(())()()()()))()(()()))(())(())(())((())(((())(()()))())()))(()((((((())()))(((()))))))()(((()()(())))()()(())))()))()(()())()((()((((()()())()((((((())((((((((())(()()()(()))(((()(()(((((())((()))(((((()(()(((()()(()(())()()((((())))(()))(())())))(())))((((()))()))()((...

result:

ok 1 cases (1 test case)

Test #31:

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

input:

1
))()))((())()((()))(()))(())())(()()(())()((((())())()()()()()))))(((()(()(((()(((()(((()())((())(()(())))(()()))((()()((()))()))(()))()))((())())))())(())))()((()())()()((((()()())())))((())()((((()()()())((((((((())))))()()()(()())(())()(()((()()(()())(()(()(())((())((())()(()))())(((()(())(((((...

output:

impossible

result:

ok 1 cases (1 test case)

Test #32:

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

input:

1
)))()()()()((())())))))))))))()(()))()()())((((((()))((())))((())(((())(()())()))))()()))()))((()((()(())(())(())())(((((()())))))(((()(()())()((())))))()(((()((()(((()()((())))))((()(()((())()))()))()(((())))))())(())((((((((()()())()))))(()(()((()()())(())))))())((((()()(())(((())))((()())())(()...

output:

impossible

result:

ok 1 cases (1 test case)

Test #33:

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

input:

1
((((())))))(()()((((()(())()))))(((()()())()())))(())(())())()(()))(()()()(((()((()))))))(()())))(()((((((((()(((())(()))())))(()())))()(((()))))()()(((()()()((()(()()()((()()((()))()())))()((())()()))()(((((()))((()((())(((()((()()(()))(()))())()()(())((((())())()))()()()())))()(()())))(()()))(((...

output:

impossible

result:

ok 1 cases (1 test case)

Test #34:

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

input:

1
)(()))))))))()(())(((((())))()))())))())))()()(((()((())(()))(())(()())()())(()((())((((())())))())(((()()()()))())())()()((()(((()(()(((())(()((()()()()((()()()())))((()()()(((())))))))))))())()())))((()()())))))(((()()())()))(()))()))())))))))))()(()(()((())))()(()())(()))()()))())((()(()()()(((...

output:

impossible

result:

ok 1 cases (1 test case)

Test #35:

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

input:

1
))(((()(()((()(((()((())()((((()()))((()(((()(())(((())))((()))))()(())))(((((()())))(())())(()())()(((((()(())()))(((((()(())())))())))(((((()())())()(()())))))())(()))(((((((()((((((((((())))((())(())((()))))()((((())()(())((((()((((()))))))(())(())(()))))()()(())))()((()))(())())())(())())))))(...

output:

impossible

result:

ok 1 cases (1 test case)

Test #36:

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

input:

1
(()()))()(())())()(()))(())()())(()((())))())(()))())()(((()))()()()())()(((()(()(((()))()))((())(()()(((())(())()))()()))((()()))((()((((((((()()(())()(((()))(()()(((()))(((((()()))((((()((()((())((()))))))(((((()(()()())()))))))(()())(((((()()((()))(())(((()((()()(())()()())))())()((()()((((()()...

output:

(()()))()(())())()(()))(())()())(()((())))())(()))())()(((()))()()()())()(((()(()(((()))()))((())(()()(((())(())()))()()))((()()))((()((((((((()()(())()(((()))(()()(((()))(((((()()))((((()((()((())((()))))))(((((()(()()())()))))))(()())(((((()()((()))(())(((()((()()(())()()())))())()((()()((((()()))...

result:

ok 1 cases (1 test case)

Test #37:

score: 0
Accepted
time: 7ms
memory: 4688kb

input:

1
()))))((((()()()()((())((())((()()((()(((((()()()(((())())))())())()(()))((())((((((())((())()())())()())()()((((()(((())()()))(((()))((((()(()))))(()()()()((())))))(())()(((()))))())())())((()()))())())()((()()()(()()()()(((()()))())(()())(()()(())))(()))))())())(((()))(((())))()()(())))()(((()))...

output:

impossible

result:

ok 1 cases (1 test case)

Test #38:

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

input:

1
)()())())((()((()(())(())(())())(((((()())))))(((()(()())()((())))))()(((()((()(((()()((())))))((()(()((())()))()))()(((())))))())(())((((((((()()())()))))(()(()((()()())(())))))())((((()()(())(((())))((()())())(()(()(()((())()((((())()()()))((()))())()((()())())())(()))(()(()())))(()(()((())))))(...

output:

)()())())((()((()(())(())(())())(((((()())))))(((()(()())()((())))))()(((()((()(((()()((())))))((()(()((())()))()))()(((())))))())(())((((((((()()())()))))(()(()((()()())(())))))())((((()()(())(((())))((()())())(()(()(()((())()((((())()()()))((()))())()((()())())())(()))(()(()())))(()(()((())))))(()...

result:

ok 1 cases (1 test case)

Test #39:

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

input:

1
(())(((()))))((()()()(()(((((((()()(()((())())(())))))())()((())(())()))(()(()()()(()))(()(())()()(()())))))()())))((()((())()()())())())()))())())()()(())((()))()()(()))))()(())(()()()()()()())()(((()((())())(())))())()(()(())())()()(()()(((())(()(((((())()))(()()())()()())(()(())(()())))()())))(...

output:

(())(((()))))((()()()(()(((((((()()(()((())())(())))))())()((())(())()))(()(()()()(()))(()(())()()(()())))))()())))((()((())()()())())())()))())())()()(())((()))()()(()))))()(())(()()()()()()())()(((()((())())(())))())()(()(())())()()(()()(((())(()(((((())()))(()()())()()())(()(())(()())))()())))(()...

result:

ok 1 cases (1 test case)

Test #40:

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

input:

1
)))))(()((((()))())))()()((())(()()())(()())()))))()(((())))((()()))(((()()(((((()()(()())()(())(((()))))()(()))(())))(()())((()(())())))(()(()(((()((()))(((((())(())(()(()(()())))())(()))()((((()))()())))()())(()()((()()(()()))))))(())(()()(())(())())()()(()))()))))()()()((()(())()))()((())))())(...

output:

)))))(()((((()))())))()()((())(()()())(()())()))))()(((())))((()()))(((()()(((((()()(()())()(())(((()))))()(()))(())))(()())((()(())())))(()(()(((()((()))(((((())(())(()(()(()())))())(()))()((((()))()())))()())(()()((()()(()()))))))(())(()()(())(())())()()(()))()))))()()()((()(())()))()((())))())()(...

result:

ok 1 cases (1 test case)

Test #41:

score: 0
Accepted
time: 7ms
memory: 4536kb

input:

1
)))(()()(())))())()((((((((()()()(())())()())))((())())()((()))))))(((())()(((()))(((())()(()()())()()))))((()(()(())()()()((())())(()()((())))))))((()(((()((())())())(()()))))))((())()))()(((()))()))(())))(()(((()((((((((()))((())))())())())))()((())))()(((()))()((()())())((()())()))()(()())()())...

output:

)))(()()(())))())()((((((((()()()(())())()())))((())())()((()))))))(((())()(((()))(((())()(()()())()()))))((()(()(())()()()((())())(()()((())))))))((()(((()((())())())(()()))))))((())()))()(((()))()))(())))(()(((()((((((((()))((())))())())())))()((())))()(((()))()((()())())((()())()))()(()())()()))(...

result:

ok 1 cases (1 test case)

Test #42:

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

input:

1
)))())(())()())))()()()((()))(()))()(((()()()(()))(()()())())(((()(())))()))()((((((((()()()(())())()())))((())())()((()))))))(((())()(((()))(((())()(()()())()()))))((()(()(())()()()((())())(()()((())))))))((()(((()((())())())(()())))))))((())()))()(((()))())(())))(()(((()((((((((()))((())))())())...

output:

)))())(())()())))()()()((()))(()))()(((()()()(()))(()()())())(((()(())))()))()((((((((()()()(())())()())))((())())()((()))))))(((())()(((()))(((())()(()()())()()))))((()(()(())()()()((())())(()()((())))))))((()(((()((())())())(()())))))))((())()))()(((()))())(())))(()(((()((((((((()))((())))())())()...

result:

ok 1 cases (1 test case)

Test #43:

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

input:

1
)((()()))()()(()))())())()((())(()(())(())(()))))()((()()(()())))()(()((()))())()))()()(())(())((((()((()()()))))))()())()()()()()())(()())()((((()((()(())))()())())())))()())()()())(()((())))()(()())(((((((())))(((())((()())()((()))(()())(()((()()())(())(()((())))((()()()())(()))()))()))))(((((((...

output:

)((()()))()()(()))())())()((())(()(())(())(()))))()((()()(()())))()(()((()))())()))()()(())(())((((()((()()()))))))()())()()()()()())(()())()((((()((()(())))()())())())))()())()()())(()((())))()(()())(((((((())))(((())((()())()((()))(()())(()((()()())(())(()((())))((()()()())(()))()))()))))((((((()(...

result:

ok 1 cases (1 test case)

Test #44:

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

input:

1
)))()(((()()(()))(((())())()()(()()(())))))))(()))((()()))(()))()()))((()))())()((()())())())(()))(()(()())))(()(()((())))))(()))()))))()()())(()()))(()((((()))))))())()(()(((()())(()(((()))(()))())))(((((())((((()())((()(((())(()(()))()()())()())))()()(((())())))))))))(((()()()()()()()()(()()))((...

output:

)))()(((()()(()))(((())())()()(()()(())))))))(()))((()()))(()))()()))((()))())()((()())())())(()))(()(()())))(()(()((())))))(()))()))))()()())(()()))(()((((()))))))())()(()(((()())(()(((()))(()))())))(((((())((((()())((()(((())(()(()))()()())()())))()()(((())())))))))))(((()()()()()()()()(()()))(())...

result:

ok 1 cases (1 test case)

Test #45:

score: 0
Accepted
time: 7ms
memory: 4596kb

input:

1
)))())()))))()))(()))()))()((())(())))(()((((()())(((()()(()))()))()))((()((())))(((()()))()))(()))))(()(((((((()))())(()((((())()))(()((())(((()(((()(((()))))(())((()(()()))(()))(((())(()()))((()())((((((()(()())())))))((()))())((((((()(())(()()(()()(()()((((((((())())())(()(()())((((())))())))()...

output:

impossible

result:

ok 1 cases (1 test case)

Test #46:

score: 0
Accepted
time: 10ms
memory: 4736kb

input:

1
(((())))(((()()()()(()))()())()))(()((()()()()())()())))((()())(((()()())(()))(()))()()((()()(())()(())))())(())(()(()()(((()()(())((((()((()))()())()((())(())(()((((())((((())(((((())()((()(())))(()()(()()()))()((((()((())((())())))((()((()(((()())))))((()())((((())()()())((((()())))())()((()))((...

output:

(((())))(((()()()()(()))()())()))(()((()()()()())()())))((()())(((()()())(()))(()))()()((()()(())()(())))())(())(()(()()(((()()(())((((()((()))()())()((())(())(()((((())((((())(((((())()((()(())))(()()(()()()))()((((()((())((())())))((()((()(((()())))))((()())((((())()()())((((()())))())()((()))(()(...

result:

ok 1 cases (1 test case)

Test #47:

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

input:

1
))((((()))())))(((())()()((()))(((()((())())()((())((((((((()))()()(((())(()((((())()))(()(((())()((())(())(()))(()))()(()()())(())))((())(()()))())))))(()))()(((()())))(()))()())))()()((()(((()))))((()((((())(())(())()())))(()())(((()()(()(())()()()))))()())())))(()((()(()(()())))()))(())))))))((...

output:

))((((()))())))(((())()()((()))(((()((())())()((())((((((((()))()()(((())(()((((())()))(()(((())()((())(())(()))(()))()(()()())(())))((())(()()))())))))(()))()(((()())))(()))()())))()()((()(((()))))((()((((())(())(())()())))(()())(((()()(()(())()()()))))()())())))(()((()(()(()())))()))(())))))))((()...

result:

ok 1 cases (1 test case)

Test #48:

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

input:

1
)))()()(()))()))(()(())())(()())((((())()))(())()(()))))((((((())))((()(())()((((()())(()())())()()(()(())(()(((()))))(()()((())((((((()))(((((()()))()())()))))((())()())((((()))))())())())()))()()()))())))(((()))((()()((((())))((()()()(())((()()()())()())()()()()(((())(()))())(()))()(()(()())())(...

output:

)))()()(()))()))(()(())())(()())((((())()))(())()(()))))((((((())))((()(())()((((()())(()())())()()(()(())(()(((()))))(()()((())((((((()))(((((()()))()())()))))((())()())((((()))))())())())()))()()()))())))(((()))((()()((((())))((()()()(())((()()()())()())()()()()(((())(()))())(()))()(()(()())())(((...

result:

ok 1 cases (1 test case)

Test #49:

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

input:

1
()(((((((((((((((((((((((((((()((((((((((((((((((((((((((((((((((((((((((()())(()((((((((((()((((((((((((((((((()(()()()((((((((((((()(()((()((((((((((()(((((((((((((((())((((((((((((((((((((((((((((((((((((((((((((((())((((((((((()((((((()(((((((((((((((((((((((((()(()(()(((((((((((()((((((((((((...

output:

()(((((((((((((((((((((((((((()((((((((((((((((((((((((((((((((((((((((((()())(()((((((((((()((((((((((((((((((()(()()()((((((((((((()(()((()((((((((((()(((((((((((((((())((((((((((((((((((((((((((((((((((((((((((((((())((((((((((()((((((()(((((((((((((((((((((((((()(()(()(((((((((((()((((((((((((((...

result:

ok 1 cases (1 test case)

Test #50:

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

input:

1
()()()(()))(()()(())(((((((()(())(((()))))(((()(((())))()((((((()(((((()(((((()((())((((((((((()(((()))()(((()((()(((()))(()((((((((()((((((()((((()((()(((((())((((()())((())(((()(()()((((()()))(())((())(()())()()((((((((((((((((((((((()(()))(()((((()((())((()((((((((((((()()(((((((((((()(()((()((...

output:

()()()(()))(()()(())(((((((()(())(((()))))(((()(((())))()((((((()(((((()(((((()((())((((((((((()(((()))()(((()((()(((()))(()((((((((()((((((()((((()((()(((((())((((()())((())(((()(()()((((()()))(())((())(()())()()((((((((((((((((((((((()(()))(()((((()((())((()((((((((((((()()(((((((((((()(()((()(())...

result:

ok 1 cases (1 test case)

Test #51:

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

input:

1
)())())()(()))()))())()(()((())())))()))(())))))((())))()()))()((((()(()))))))))()))()))())(()))()())))()()())(()())()))))))))()(())(()))()()))())))))()()))()(()))))())()))()))()(()())(()))(()))()))()))(())()())))))()))()()())())))()((())()))))())()))))))())))()()())(()))())))()))))))))()()((())()...

output:

)())())()(()))()))())()(()((())())))()))(())))))((())))()()))()((((()(()))))))))()))()))())(()))()())))()()())(()())()))))))))()(())(()))()()))())))))()()))()(()))))())()))()))()(()())(()))(()))()))()))(())()())))))()))()()())())))()((())()))))())()))))))())))()()())(()))())))()))))))))()()((())()()...

result:

ok 1 cases (1 test case)

Test #52:

score: 0
Accepted
time: 7ms
memory: 4620kb

input:

1
))))))())())())()()))))))))))))))))))))))()))))))))))))))))))()))))))))))))))))()))))))))())))))))))()))))))))))((())))())()(()))()))))()))))))())))()))))())))))))()())()()()))))()))()))))())()))))))))))))(())))))(()))))())))())()()))))()))))))))))))()))))))())))))))))))()))))(())))))))))())))))))...

output:

))))))())())())()()))))))))))))))))))))))()))))))))))))))))))()))))))))))))))))()))))))))())))))))))()))))))))))((())))())()(()))()))))()))))))())))()))))())))))))()())()()()))))()))()))))())()))))))))))))(())))))(()))))())))())()()))))()))))))))))))()))))))())))))))))))()))))(())))))))))())))))))))...

result:

ok 1 cases (1 test case)

Test #53:

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

input:

1
((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((()((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((()((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

result:

ok 1 cases (1 test case)

Test #54:

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

input:

1
)))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))()))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))()))))))))))))))))))))())))))))))))))))))))))))))))))))))...

output:

)))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))()))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))()))))))))))))))))))))())))))))))))))))))))))))))))))))))))...

result:

ok 1 cases (1 test case)

Test #55:

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

input:

100000
((((())()(
)(((())()(
()((())()(
))((())()(
(()(())()(
)()(())()(
())(())()(
)))(())()(
((()())()(
)(()())()(
()()())()(
))()())()(
(())())()(
)())())()(
()))())()(
))))())()(
(((()))()(
)((()))()(
()(()))()(
))(()))()(
(()()))()(
)()()))()(
())()))()(
)))()))()(
((())))()(
)(())))()(
()())))...

output:

impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
imp...

result:

ok 100000 cases (100000 test cases)

Test #56:

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

input:

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

output:

(((())()(())))(())))
)((())()(())))(())))
()(())()(())))(())))
))(())()(())))(())))
(()())()(())))(())))
)()())()(())))(())))
())())()(())))(())))
)))())()(())))(())))
((()))()(())))(())))
)(()))()(())))(())))
()()))()(())))(())))
))()))()(())))(())))
(())))()(())))(())))
)())))()(())))(())))
()))))...

result:

ok 50000 cases (50000 test cases)

Test #57:

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

input:

66666
())()(()))())))
)))()(()))())))
((())(()))())))
)(())(()))())))
()())(()))())))
))())(()))())))
(()))(()))())))
)()))(()))())))
())))(()))())))
)))))(()))())))
((((()()))())))
)(((()()))())))
()((()()))())))
))((()()))())))
(()(()()))())))
)()(()()))())))
())(()()))())))
)))(()()))())))
((()()...

output:

())()(()))())))
)))()(()))())))
((())(()))())))
)(())(()))())))
()())(()))())))
))())(()))())))
(()))(()))())))
)()))(()))())))
())))(()))())))
)))))(()))())))
((((()()))())))
)(((()()))())))
()((()()))())))
))((()()))())))
(()(()()))())))
)()(()()))())))
())(()()))())))
)))(()()))())))
((()()()))()...

result:

ok 66666 cases (66666 test cases)

Test #58:

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

input:

200000
(((((
)((((
()(((
))(((
(()((
)()((
())((
)))((
((()(
)(()(
()()(
))()(
(())(
)())(
()))(
))))(
(((()
)((()
()(()
))(()
(()()
)()()
())()
)))()
((())
)(())
()())
))())
(()))
)()))
())))
)))))
(((((
)((((
()(((
))(((
(()((
)()((
())((
)))((
((()(
)(()(
()()(
))()(
(())(
)())(
()))(
))))(
(((()...

output:

impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
)()()
())()
)))()
impossible
)(())
()())
))())
(()))
)()))
())))
))))...

result:

ok 200000 cases (200000 test cases)

Test #59:

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

input:

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

output:

)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
...

result:

ok 1000000 cases (1000000 test cases)

Extra Test:

score: 0
Extra Test Passed