8021번 - Minuses 다국어

The operation of subtraction is not associative, e.g. (5-2)-1=2, but 5-(2-1)=4, therefore (5-2)-1≠5-(2-1). It implies that the value of the expression of the form 5-2-1 depends on the order of performing subtractions. In lack of brackets we assume that the operations are performed from left to right, i.e. the expression 5-2-1 denotes (5-2)-1. We are given an expression of the form

x₁±x₂±…±x_n,

where each ± denotes either + (plus) or - (minus), and x₁,x₂,…,x_n denote (pairwise) distinct variables. In an expression of the form

x₁-x₂-…-x_n

we want to insert brackets in such a way as to obtain an expression equivalent to the given one. For example, if we want to obtain an expression equivalent to the expression

x₁-x₂-x₃+x₄+x₅-x₆+x₇

we may insert brackets into

x₁-x₂-x₃-x₄-x₅-x₆-x₇

as follows:

((x₁-x₂)-(x₃-x₄-x₅))-(x₆-x₇).

Note: Brackets that surround none or only one variable are not allowed.

Write a program which:

• reads from the standard input the description of the given expression of the form x₁±x₂±…±x_n,
• determines the way brackets may be inserted into the expression so as to obtain an expression x₁-x₂-…-x_n equivalent to the given one; at most n-1 pairs of brackets may be inserted,
• describes in the text file min.out this arrangement brackets.

In the first line of the standard input there is one integer n, 2 ≤ n ≤ 1,000,000. This is the number of variables in the given expression. In each of the following n-1 lines there is one character + or -. In the i-th line there is the sign appearing between x_i-1 and x_i in the given expression.

In the first line of the standard output your program should write the requested way of bracket insertion into the expression x₁-x₂-…-x_n. Only brackets and minuses (without spaces between them) should be written, and the variables x₁,x₂,…,x_n ought to be skipped. You may assume that for the test data there is always a solution. If there exist many possible solutions your program should write one of them.