NSITACMC - LED Board

Amit is getting bored. He has an LED box that can be represented as a rectangular grid of sides, N × M. The LEDs work only in two modes, "ON" or "OFF".

He decides to design a pattern with the LEDs. However, the LED box is peculiar.

In one move, Amit can choose a sub-rectangle of exactly R rows and C columns and toggle the LEDs in that sub-rectangle.

Formally, all LEDs in the subrectangle, which are "ON" change to "OFF" while LEDs that are "OFF" change to the "ON".

Your task is to help Amit determine the minimum number of moves required to make the pattern or output -1 if it is not possible.

Initially, all LEDs are off.

T <= 1000

1 <= N, M <= 300

1 <= R <= N

1 <= C <= M

Input

First line consists of the number of test cases, T.

Then follows T test cases each with the first line N, M, R, C.

Then follows, N lines with exactly M characters denoting the state of the LEDs in the desired pattern.

  • 0 - denotes OFF.
  • 1 - denotes ON.

Output

T lines each containing the minimum number of moves to establish the pattern or -1 if it is not possible.

Example

Input:
3
3 3 1 1
010
111
011
4 4 2 1
0111
1101
0110
1101
3 4 2 2
0110
0110
0000

Output:
6
-1
1

Added by:Mukul Gupta
Date:2013-03-14
Time limit:1.360s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2013-03-18 04:16:51 Mukul Gupta
@Anon: There is an apparent bug in your solution. It is not just the corner cases.
2013-03-18 04:16:51 Anon
My code is giving wrong answer. can anybody provide me some special case. My code is working fine on my test cases, may be missing some corner scenario, but i could not find. Can anybody take a look on solution Id 8911153.

Thanks in advance

Last edit: 2013-03-17 06:01:45
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.