Little C has decided to plant patterns in the shape of "CCF" in his garden, and he wants to know how many ways he can plant the letters C and F, respectively. Unfortunately, there are some pits in the garden where flowers cannot be planted, so he hopes you can help him solve this problem.

The garden can be viewed as an $n \times m$ grid, with rows numbered 1 to $n$ from top to bottom and columns 1 to $m$ from left to right. Each position may or may not contain a pit. We use $a_{i,j} = 1$ to indicate that there is a pit at row $i$, column $j$, and $a_{i,j} = 0$ otherwise.

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$, and the positions from column $y_0$ to $y_1$ in row $x_1$, from column $y_0$ to $y_2$ in row $x_2$, and from row $x_1$ to $x_2$ in column $y_0$ are all not pits, and flowers are planted only 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]$ such that $x_1 + 1 < x_2 < x_3$ and $y_0 < y_1, y_2 \le m$, and the positions from column $y_0$ to $y_1$ in row $x_1$, from column $y_0$ to $y_2$ in row $x_2$, and from row $x_1$ to $x_3$ in column $y_0$ are all not pits, and flowers are planted only in these positions.

The explanation for Example 1 provides visual examples of C-shaped and F-shaped planting schemes.

Now, Little C wants to know, given $n, m$ and the values $\{a_{i,j}\}$ representing whether each position is a pit, how many possible C-shaped and F-shaped planting schemes are there? Since the answer can be very large, you only need to output the result modulo 998244353. Please refer to the Output section for details.

Input

Read the data from the file plant.in.

The first line contains two integers $T$ and $id$, representing the number of test cases and the test point ID, respectively. If the data is a sample, it is guaranteed that $id = 0$.

For each of the $T$ test cases: The first line contains four integers $n, m, c, f$, where $n$ and $m$ represent the number of rows and columns of the garden, respectively. For the meanings of $c$ and $f$, see the Output section.

The next $n$ lines each contain a string of length $m$ consisting only of 0 and 1, where the $j$-th character of the $i$-th string represents $a_{i,j}$, i.e., whether the position at row $i$, column $j$ in the garden is a pit.

Output

Output to the file plant.out.

Let $V_C$ and $V_F$ be the number of C-shaped and F-shaped planting schemes in the garden, respectively. For each test case, you need to output a single line containing two non-negative integers separated by a space, representing $(c \times V_C) \pmod{998244353}$ and $(f \times V_F) \pmod{998244353}$, respectively, where $a \pmod P$ denotes the result of $a$ modulo $P$.

Examples

Input 1

1 0
4 3 1 1
001
010
000
000

Output 1

4 2

Note 1

The four C-shaped planting schemes are:

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

Where * indicates a position where a flower is planted. Note that the two horizontal bars of C can have different lengths.

Similarly, the two F-shaped planting schemes are:

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

Examples 2

See plant/plant2.in and plant/plant2.ans in the contestant directory.

Examples 3

See plant/plant3.in and plant/plant3.ans in the contestant directory.

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\}$.

Special Property A: $\forall 1 \le i \le n, 1 \le j \le \lfloor \frac{m}{3} \rfloor, a_{i,3j} = 1$. Special Property B: $\forall 1 \le i \le \lfloor \frac{n}{4} \rfloor, 1 \le j \le m, a_{4i,j} = 1$.