Migrated from Lutece 1316 Joyful Painting

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

You are using a painting software to draw a picture $H$ pixels in height and $W$ pixels in width.

There are $n$ kinds of black brushes in rectangle shape, and $i^{th}$ brush is $A_i$ high and $B_i$ wide.

All brushes can't be rotated, and all pixels are white initially.

You want to draw a specific picture, and now you should determine whether it is possible to draw it.

Input

The first line contains two integers $H$ and $W$: the height and the width of picture.

Then $H$ lines follow, each with a string consisting of $W$ characters with only W(White) and B(Black), showing the target picture.

The following line contains a number $n$.

Then $n$ lines follow, each line with two integers $A_i$ and $B_i$.

$1\leq W, H, A_i, B_i\leq 2000$

$1\leq n\leq 10$

Output

If it is possible to draw the target picture, print POSSIBLE, otherwise print IMPOSSIBLE.

Samples

5 5
WWWWW
WBBBW
WBBWW
WBWWW
WWWWW
3
1 3
2 2
3 1

POSSIBLE

3 3
BBW
WBB
WWB
1
1 2

POSSIBLE

4 3
WWW
WBW
WBW
WWW
1
1 2

IMPOSSIBLE

Note

Please note that brushes can redraw the area that have been drawn, and can be out of bound partly.

Resources

The 14th UESTC Programming Contest Final