Little C decided to plant the pattern of CCF in his garden, so he wanted to know how many flowering schemes there are for the two letters C and F; He wants you to help him with this problem.

A garden can be viewed as a grid map with ~n \times m~ locations, which are the ~1~st to ~n~th rows from top to bottom, and the ~1~st to ~m~th columns from left to right, where each location may be mud or not. Specifically, ~a_{i,j} = 1~ indicates that there is mud at the position of row ~i~ and column ~j~, and ~a_{i,j} = 0~ indicates that there is no mud at this position.

A planting scheme is called C-shaped, if there exist ~x_1, x_2 \in [1,n]~, and ~y_0, y_1, y_2 \in [1,m]~, such that ~x_1+1 < x_2~, and ~y_0 < y_1, y_2 \le m~, so that the ~y_0~th to ~y_1~th column of the ~x_1~th row, the ~y_0~th to ~y_2~th column of the ~x_2~th row, and the ~x_1~th to ~x_2~th row of the ~y_0~th column are not mud, and flowers are only planted in these positions.

A planting scheme is called F-shaped, if there exist ~x_1, x_2, x_3 \in [1,n]~, and ~y_0, y_1, y_2 \in [1,m]~, satisfying ~x_1+1 < x_2 < x_3~, and ~y_0 < y_1, y_2 \le m~, so that the ~y_0~ to ~y_1~ column of the ~x_1~ row, the ~y_0~ to ~y_2~ column of the ~x_2~ row, and the ~x_1~ to ~x_3~ row of the ~y_0~ column are not mud, and flowers are only planted in these positions.

Sample 1 gives examples of C-shape and F-shape planting schemes.

Now little C wants to know, given ~n~, ~m~ and the value ~\{a_{i, j}\}~ indicating whether each position is mud, how many possibilities are there for C-shaped and F-shaped flowering schemes? Since the answer may be very large, you only need to output the result modulo ~998\,244\,353~. Please refer to the output format section for specific output results.

Input Specification

The first line contains two integers ~T~, ~\mathit{id}~, which respectively represent the number of data sets and the number of test points. All sample data have ~\mathit{id} = 0~.

Next, there are ~T~ sets of data, in each set of data:

The first line contains four integers ~n~, ~m~, ~c~, ~f~, where ~n~, ~m~ represent the number of rows and columns of the garden respectively, and see the output format section for the meaning of ~c~, ~f~.

The next ~n~ lines, each line contains a string of length ~m~ and only contains ~0~ and ~1~, where the ~j~th character of the ~i~th string represents ~a_{i, j}~, that is, is the ~j~th column of the ~i~th row in the garden mud.

Output Specification

For each set of data, if there are ~V_C~ and ~V_F~ C-shaped and F-shaped flower planting schemes in the garden respectively, you need to output two non-negative integers separated by a space, ~(c \times V_C) \bmod 998\,244\,353~, and ~(f \times V_F) \bmod 998\,244\,353~, where ~a \bmod P~ represents the result of taking the remainder of ~a~ divided by ~P~.

Sample Input 1

1 0
4 3 1 1
001
010
000
000

Sample Output 1

4 2

Explanation of Sample 1

The four C-typed plans are:

**1 **1 **1 **1
*10 *10 *10 *10
**0 *** *00 *00
000 000 **0 ***

Where * means to plant flowers at this position. Note that the two bars of C can be of different lengths.

Similarly, the two F-shape planting schemes are:

**1 **1
*10 *10
**0 ***
*00 *00

Additional Samples

Additional sample cases can be found here.

Constraints

For all data, it is guaranteed that ~1 \le T \le 5~, ~1 \le n, m \le 10^3~, ~0 \le c, f \le 1~, ~a_{i, j} \in \{0, 1\}~.

Case	~n~	~m~	~c~	~f~	Special Property	Points
1	~\leq 1000~	~\leq 1000~	0	0	none	1
2	~=3~	~=2~	1	1		2
3	~=4~					3
4	~\leq 1000~					4
5		~\leq 1000~			~\forall 1 \leq i \leq n, 1 \leq j \leq \lfloor \frac{m}{3} \rfloor, a_{i, 3j} = 1~	4
6					~\forall 1 \leq i \leq \lfloor \frac{n}{4} \rfloor, 1 \leq j \leq m, a_{4i, j} = 1~	6
7	~\leq 10~	~\leq 10~			none	10
8	~\leq 20~	~\leq 20~				6
9	~\leq 30~	~\leq 30~				6
10	~\leq 50~	~\leq 50~				8
11	~\leq 100~	~\leq 100~				10
12	~\leq 200~	~\leq 200~				6
13	~\leq 300~	~\leq 300~				6
14	~\leq 500~	~\leq 500~				8
15	~\leq 1\,000~	~\leq 1\,000~		0		6
16				1		14