Molly was experimenting with bracket strings, when she made a mistake and accidentally changed some of the characters. Now, she needs your help to fix her bracket sequence.

To begin, here are Molly's definitions:

• A bracket string consists of the following eight symbols: ()[]{}<>. The characters ([{< are considered left brackets, and )]}> are considered right brackets. Initially, Molly's string does not contain either of <>.
• There are four distinct matching pairs: (), [], {}, and <>. Within each pair, the left bracket must be paired with the right bracket.
• A string is considered valid if every left bracket can be paired with a distinct right bracket such that the left bracket appears to the left of the right bracket, and the string inside of the matching pair is either empty or valid. For example, valid strings could be (<>), ({}<[]()>), or ()[]{}{[()]} whereas invalid strings would be ({)}, ((([]) and ><.

Currently, Molly has a bracket string (either valid or invalid) with ~N~ (an even number) characters. You can replace brackets in it according to the following rules:

• You must replace any removed left bracket with a different left bracket, and any right bracket with a different right bracket. Also, you may not replace any index of the string more than once.
• If you replace a bracket with < or >, or choose not to change a bracket, then the cost is ~0~.
• Otherwise, it costs ~X~ to remove ( or ), ~Y~ to remove [ or ], and ~Z~ to remove { or }. The cost is only determined by the bracket which was removed.
• Molly wants the cost of creating a valid string to be exactly ~K~.

Given these constraints, output a valid string with a cost of ~K~. It will always be possible to change the input string into a valid string, although not necessarily with the correct cost. Output impossible if a cost of ~K~ cannot be achieved.

Constraints

For all subtasks:

~K, X, Y, Z \ge 0~

Subtask 1 [15%]

~2 \le N \le 20~

~K, X, Y, Z \le 1000~

Subtask 2 [20%]

~2 \le N \le 200\,000~

~K \le 200\,000~

~X = Y = Z = 1~

Subtask 3 [25%]

~2 \le N \le 200\,000~

~K, X, Y, Z \le 500\,000~

Subtask 4 [40%]

~2 \le N \le 200\,000~

~K \le 10^{10}~

~X, Y, Z \le 10^9~

Input Specification

On the first line, there will be the integers ~N~ and ~K~.

On the second line, there will be the integers ~X~, ~Y~, and ~Z~.

The last line will contain the initial bracket sequence (~N~ characters).

Output Specification

The only line of output should be a valid string of length ~N~ which costs ~K~ to create by replacing characters in the input, or impossible if no such string exists. If there are multiple answers, print any of them.

Sample Input 1

6 4
1 1 1
(()[})

Sample Output 1

([]())

Explanation for Sample 1

Since it costs ~1~ to replace any bracket, and four brackets were changed to different brackets, the total cost is ~4~.

Sample Input 2

6 17
5 3 4
([}[})

Sample Output 2

[()<>]

Explanation for Sample 2

Two of each bracket type were replaced. However, one [ bracket and one } bracket (the fourth and fifth characters) were replaced with <>, meaning that the cost for replacing them is ~0~. Adding up the cost for the rest of the string produces ~5 + 5 + 3 + 4 = 17~. Note that another valid answer would be {<>()}, since the cost of replacing a character with something other than <> is only determined by the original symbol.

Sample Input 3

2 1
0 0 0
()

Sample Output 3

impossible