Baby Ming and Matrix games

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Description

These few days, Baby Ming is addicted to playing a matrix game.

Given a $n*m$ matrix, the character in the matrix$(i*2, j*2) \ (i, j = 0, 1, 2 ...)$ are the numbers between $0-9$. There are an arithmetic sign (‘+’, ‘-‘, ‘$*$’, ‘/’) between every two adjacent numbers, other places in the matrix fill with ‘#’.

The question is whether you can find an expressions from the matrix, in order to make the result of the expressions equal to the given integer $sum$. (Expressions are calculated according to the order from left to right)

Get expressions by the following way: select a number as a starting point, and then selecting an adjacent digital X to make the expressions, and then, selecting the location of X for the next starting point. (The number in same place can’t be used twice.)

Input

In the first line contains a single positive integer $T$, indicating number of test case.

In the second line there are two odd numbers $n, m$, and an integer sum($-10^{18} < sum < 10^{18}$, divisor 0 is not legitimate, division rules see example)

In the next $n$ lines, each line input $m$ characters, indicating the matrix. (The number of numbers in the matrix is less than $15$)

$1 \leq T \leq 1000$

Output

Print Possible if it is possible to find such an expressions.

Print Impossible if it is impossible to find such an expressions.

Sample Input

3 3 3 24 1*1 +#* 2*8 1 1 1 1 3 3 3 1*0 /#* 2*6

Sample Output

Possible Possible Possible
Hint
The first sample:1+2*8=24 The third sample:1/2*6=3

Hint

hujie

Source

BestCoder Round #69 (div.2)

提交代码