The students of university M. like to play the game ``HardNumbers''.
The rules are the following: you are given a sequence of digits. Your goal is to obtain a given number from them by using some operations. The operations you may perform are given in the input.
The first line of the input contains the number of the
test cases, which is at most 40. The descriptions of the test cases
follow.
The first line a test case description contains the original
sequence of at most five digits without spaces. The second
line contains the integer number you have to obtain. (The
number is from
to
.) The third line contains a
sequence of characters without spaces describing the rules.
Each character allows one to use some operation. The
operations and their characters are listed below:
Character | Operation |
+ | addition |
- | subtraction |
* | multiplication |
/ | real division |
x | throwing away some (not all) of the digits |
j | concatenation of some subsequent digits in a single integer |
p | permutation of the digits |
For each test case in the input, output `Impossible
' (without quotes), if it is impossible to obtain
the given number using the given set of operations, or any
expression yielding the number otherwise. The expression
syntax is given below:
expression ::= number
| `(
' expression `+
' expression `)
'
| `(
' expression `-
' expression `)
'
| `(
' expression `*
' expression `)
'
| `(
' expression `/
' expression `)
';
number ::= digit | digit number;
digit ::= `0
' | `1
' | `2
'
| `3
' | `4
' | `5
'
| `6
' | `7
' | `8
'
| `9
';
The expression must contain no spaces. It may contain an
operation sign (+-/*
) only if this operation is
permitted by the rules. If throwing away digits is
permitted, each digit must enter in the expression no more
times than it entered in the original sequence of digits,
otherwise each digit must enter in the expression as many
times as it entered in the original sequence of digits. If
concatenation of subsequent digits is not permitted, each
number in the expression must contain exactly one digit. If
permutation of the digits is not permitted, the sequence of
digits in the expression must be a subsequence of the
original sequence of digits. The value of the expression
must be equal to the given number. Print a blank line between
test cases.
Input | Output |
1 1346 24 +-*/p | (6/(1-(3/4))) |