시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 2048 MB142214.286%

문제

Marijn wrote an expression to calculate the answer to the ultimate question. Unfortunately, his friend Jeroen decided to pull a prank and shuffled all the characters in his expression!

The syntax of the expression is similar to that of most programming languages (in fact, the expression is valid Python):

  • Expressions consist of numbers, variables, and parenthesized expressions (enclosed between '(' and ')'), which are joined together by the operators '+' and '*'.
  • Numbers consist of digits (0-9) and do not start with a leading '0', except for the number '0' itself.
  • Variables start with a letter, followed by zero or more letters and/or digits.
  • The '*' operator takes precedence over '+'.

An example of a valid expression is "(abc+var0)*(12+0)", where the addition of two variables "abc" and "var0" is multiplied by the addition of "12" and "0".

Luckily, Marijn remembers that he did not use any unnecessary parentheses in his code. This means that for example "a+(b+c)" does not appear because the '+' operator is associative, nor does "(a*b)+c" since the '*' operator takes precedence over '+'. Note: it is not required that removing any of the parentheses actually changes the outcome of the expression.

Given a shuffled expression, help Marijn find any expression that could have been his original expression, if such an expression exists.

입력

The input consists of:

  • One line with an integer $n$ ($1\leq n\leq 3\cdot 10^5$), the length of the shuffled expression.
  • One line with a string of length $n$, the shuffled expression, consisting of the characters in "()+*", digits (0-9), and English lowercase letters (a-z).

출력

If an expression exists that satisfies all the requirements, output "possible" followed by such a permutation of the input string. Otherwise, output "impossible".

If there are multiple valid solutions, you may output any one of them.

예제 입력 1

7
123test

예제 출력 1

possible
test321

예제 입력 2

10
012var+*()

예제 출력 2

possible
(var2+0)*1

예제 입력 3

7
(1+2)+3

예제 출력 3

impossible

예제 입력 4

7
(000+*)

예제 출력 4

possible
(0+0)*0

예제 입력 5

2
00

예제 출력 5

impossible

예제 입력 6

9
((1+2))*3

예제 출력 6

impossible

예제 입력 7

10
bilmseiops

예제 출력 7

possible
impossible

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2025 Preliminaries C번

  • 문제를 만든 사람: Marijn Adriaanse