Ak sakallı dede (tr: white-bearded elder) (asd) has a rectangular-shaped beard with length \(\mathbf{N}\) and width \(\mathbf{M}\). The beard of asd used to be black and glorious many years ago, but now it is completely white. asd is not satisfied with the look of his beard and wants to draw some of the patterns he saw on the internet for a change. Luckily, he has learned a new spell that will help him in this task. With this spell, he can invert the color of each hair (black to white / white to black) in his beard in a \(\mathbf{X}\) by \(\mathbf{Y}\) area. In other words, after casting this spell, the black patches in the affected area will turn white, meanwhile, the white ones will turn black.

In asd's beard, the black patches are denoted by 0 and the white patches are denoted by 1. Before the initial spell, asd's beard is completely white, therefore, his beard is denoted by only 1's.

Finally, note that asd's beard can't be rotated. Can you help asd draw the pattern that he saw on the internet with this spell?

Input

The number of test cases \(\mathbf{T}\) is given in the first line.

At the first line of each test case, integers \(\mathbf{N}\), \(\mathbf{M}\), \(\mathbf{X}\) and \(\mathbf{Y}\) (that are the length and the width of asd's beard, and the length and the width of the area affected by the spell, respectively) are given.

In the following \(\mathbf{N} \times \mathbf{M}\) area a pattern is given. This is the pattern asd desires to draw on his beard.

• \(1 \leq \mathbf{T} \leq 10\)
• \(1 \leq \mathbf{X} \leq \mathbf{N} \leq 300\)
• \(1 \leq \mathbf{Y} \leq \mathbf{M} \leq 300\)

Output

For each test case firstly, print the minimum number of times (\(L\)) the spell must be cast to attain the desired pattern will be printed. Then in following \(L\) lines print the sorted list of the top-left coordinates of the areas that asd should cast a spell on.

If the pattern is unattainable, the string "sad" should be printed, instead.

Examples

Input 1:

1
3 3 1 1
111
000
111

Output 1:

3
2 1
2 2
2 3

Input 2:

1
4 3 2 2
101
000
101
101

Output 2:

sad