Holes -- Problem I (15 points)


An mxn rectangular grid (m rows and n columns) has its cells numbered sequentially so that the top left square is 1, the square to the right of this is 2, the top right is n and the bottom right is mn. A number of its cells are occupied and the numbers for these cells are specified. You must find how many ways a pxq block (p rows and q columns) can be placed on the empty squares in the grid without changing its orientation. For example, using the data shown below (m = 5, n = 4, p = 1, q = 2), the grid, with the occupied cells marked by X, looks like:

The 1x2 block could be placed with its leftmost square on squares 1,6,7 or 15. It cannot be rotated and placed on squares 2,4,8,9,12,13 or 16.

The input file for this problem is called PROBLEMI.DAT. The first line on this file contains four numbers, giving the values for m, n, p and q respectively, separated by one or more blanks. None of these numbers will be greater than 20 or less than 1. After this there will be zero or more lines giving the numbers of the squares which are occupied. None of these numbers will exceed mn. This list of numbers will be terminated by a line containing a single zero. The file will be terminated by a line giving four zero values to m, n, p and q.

Output, which must be written to standard output (the screen), must be the number of ways of placing the pxq block, leftjustified on its line. There will be one output line for each problem description in the input.

Example Input

5 4 1 2
3
5
10
11
14
18
19
0
0 0 0 0

Example Output

4