Is It Square?

Time Limit: 1 sec

 

The Problem

Given a string grid with N x M cell, where each cell contains an uppercase alphabetic letter. And some alphabetic letters in separate line which you have to removes from grid. After removing the letter from grid take remaining letter and try to make a square. If it is possible to make a square then print its length otherwise “Impossible!!”.

 

Example: N=2, M=4

GHTG

DTHA

 

Remove H and G

T

DTA

 

Rearrange

TA

DT

It is square with length 2

 

So the output is 2 for the above case.

If we only remove H then the grid will be a rectangle of (2 X 3) or (3 X 2), which is not square.

 

The Input

The first line of the input is start with an integer T(T<=20), the number of test case. Each test case is start with two non negative integers N(N<=500)) and M(M<=500). The next N line will contain an uppercase string with M length. The next line is a non negative integer L (L<=100) the number of character to remove. The last line of the each test case is L space separated alphabetic letter that you have to remove from grid.

 

The Output

For each input set if it is possible to make a square then print the length of the square otherwise print “Impossible!!”. See the sample input and output section for more clarification.

 

Sample Input

2

2 4

GHTG

DTHA

2

H G

5 5

ADAHA

SGRCD

FAWRH

STWQL

TRYEB

4

F T Y H

 

Sample Output

2

Impossible!!

 

 

 

Inter University Programming Contest(II) - 2018 [BGC Trust University Bangladesh]

Problem Setter: Milton Dev