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 $998244353$. 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)mod998244353$, and $(f\times V_F)mod998244353$, where $amodP$ 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	$\le 1000$	$\le 1000$	0	0	none	1
2	$=3$	$=2$	1	1		2
3	$=4$					3
4	$\le 1000$					4
5		$\le 1000$			$\mathrm{\forall }1\le i\le n,1\le j\le \lfloor \frac{m}{3}\rfloor ,a_{i,3j}=1$	4
6					$\mathrm{\forall }1\le i\le \lfloor \frac{n}{4}\rfloor ,1\le j\le m,a_{4i,j}=1$	6
7	$\le 10$	$\le 10$			none	10
8	$\le 20$	$\le 20$				6
9	$\le 30$	$\le 30$				6
10	$\le 50$	$\le 50$				8
11	$\le 100$	$\le 100$				10
12	$\le 200$	$\le 200$				6
13	$\le 300$	$\le 300$				6
14	$\le 500$	$\le 500$				8
15	$\le 1000$	$\le 1000$		0		6
16				1		14