Problem Statement

In a classic card guessing game, you first lay out some cards in a width times height rectangular configuration. A friend looks at the cards, and memorizes one of them. You have to guess which card he chose. He tells you the column in which his card is located (the left-most column number is 0). Now you rearrange the cards by picking them up column after column (beginning with the first column, and picking up cards within each column from top to bottom), and laying the cards back down row by row (beginning with the top row, row number 0, and laying down cards within each row from left to right) creating a rectangular configuration with the same width and height as the original one; you lay the cards down in the order you picked them up. After this rearrangement, your friend tells you the column in which his card is now located. You repeat this rearrangement procedure several times and with all the information you get you may be able to deduce the card your friend had in mind.

For example, in the classic game, there are a total of 21 cards placed in 7 rows and 3 columns, like this:

01 02 03
04 05 06
07 08 09
10 11 12
13 14 15
16 17 18
19 20 21

Let's say the card to guess is "09". Your friend tells you that it is in the last column (column 2). Now you pick up the first column from top to bottom, then the second column, and finally the third column, and lay all the cards down row by row. This gives the following configuration:

01 04 07
10 13 16
19 02 05
08 11 14
17 20 03
06 09 12
15 18 21

Now you are informed that the card you are looking for ("09") is in the middle column (column 1). You rearrange the cards again, giving:

01 10 19
08 17 06
15 04 13
02 11 20
09 18 07
16 05 14
03 12 21

And now the card "09" is in the first column (column 0). Since this is the only card that was in the given columns in the three configurations, you can now be sure that the card you are looking for is "09".

In this problem, you will be given width and height, the width and height of the configuration, and a int[] columns giving the column position of the card to guess in each configuration. If there is enough information to deduce the correct card, return the row where the card lies in the last configuration (the configuration for which you get the last element of columns as an answer). In the example, width would be 3, height would be 7, columns would be {2, 1, 0}, and you should return 4 (the card "09" is in the fifth row in the last configuration). If there is not enough information in columns, return -1.

Definition

Constraints

Examples