C. Count Cubes
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Xue Ba Ti! Shu Zheng Fang Ti!

There are some cubes in the $$$3$$$-dimensional space. Each cube has a side length of $$$1$$$. The sides of the cubes are parallel to the $$$x$$$, $$$y$$$, and $$$z$$$ axes. A cube is said to be located at coordinates $$$(x,y,z)$$$ if and only if its $$$8$$$ corners are at:

  • $$$(x,y,z)$$$,
  • $$$(x,y,z+1)$$$,
  • $$$(x,y+1,z)$$$,
  • $$$(x,y+1,z+1)$$$,
  • $$$(x+1,y,z)$$$,
  • $$$(x+1,y,z+1)$$$,
  • $$$(x+1,y+1,z)$$$,
  • $$$(x+1,y+1,z+1)$$$.

respectively.

All cubes are located at non-negative integer coordinates in space and obey the laws of gravity. Formally, if there is a cube located at $$$(x,y,z)$$$, then either $$$z=0$$$ or there is a cube located at $$$(x,y,z-1)$$$.

An $$$x$$$-view of a $$$3$$$-dimensional structure is the $$$2$$$-dimensional shape observed if you align your sight in the positive $$$x$$$ direction. The $$$y$$$-view is defined similarly.

You don't know the exact locations of the cubes, but fortunately, you have the $$$x$$$-view and $$$y$$$ view of the structure. You also know that the locations of all cubes satisfy: $$$x \le a, y \le b, z \le c$$$. You want to find: whats the minimum and maximum number of cubes possibly present in the structure for these views to be valid? It is also possible that you have poor eyesight and there doesn't exist any valid structure, or somehow the laws of gravity are disobeyed. In any of these cases, output $$$-1$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 2\cdot 10^4$$$). The description of the test cases follows.

The first line of each test case contains three integers $$$a$$$, $$$b$$$, and $$$c$$$ ($$$1 \le a,b,c \le 10^3$$$). The size of the $$$x$$$-view will be $$$c \times b$$$, and the size of the $$$y$$$-view will be $$$c \times a$$$.

The $$$i$$$-th of the next $$$c$$$ lines contains a binary string $$$s_i$$$ of length $$$b$$$. If $$$s_j=1$$$, then the $$$x$$$-view contains a cell at $$$y=j-1$$$ and $$$z=c-i$$$.

The $$$i$$$-th of the next $$$c$$$ lines contains a binary string $$$s_i$$$ of length $$$a$$$. If $$$s_j=1$$$, then the $$$y$$$-view contains a cell at $$$x=j-1$$$ and $$$z=c-i$$$.

It is guaranteed that the sum of $$$(a+b)\cdot c$$$ over all test cases does not exceed $$$2 \cdot 10^6$$$.

Output

For each test case, if there doesn't exist any valid structure, output $$$-1$$$. Otherwise, output two integers $$$l$$$ and $$$r$$$, corresponding to the minimum and maximum number of cubes, respectively.

Example
Input
4
3 3 3
010
010
111
100
110
111
2 2 2
11
00
00
11
5 4 3
1111
1111
1111
11111
11111
11111
2 2 2
00
00
00
00
Output
7 12
-1
15 60
0 0
Note

The structures of the first sample test case are given below (Source: HDZ's MineCraft):