For any matrix, we can define two ways to enumerate its elements in non-decreasing order of their indices: either the row number takes priority over the column number, or vice versa. Let us call these orders Z and N, respectively (taking inspiration from the shape of the polyline connecting the elements in the order).
You are given an $$$n \times m$$$ matrix that can be split into blocks of size $$$r \times c$$$ (in other words, it is a $$$\frac{n}{r} \times \frac{m}{c}$$$ matrix of blocks). We can define $$$4$$$ encoding formats ZZ, ZN, NZ, and NN for it as follows: the first character defines the order of blocks in the enumeration, the second character defines the order of cells in a single block, and all cells of a block are enumerated sequentially. Refer to the image to obtain a clearer understanding using a $$$9 \times 9$$$ matrix example with $$$3 \times 3$$$ blocks.

Another, "$$$n$$$-dimensional" (ND) encoding format corresponds to Z-ordering and lists elements in the "usual" order: cells with a lower row number, or with an equal row number but a lower column number, go first.
You are given a block matrix stored as a $$$1$$$-dimensional array in the order of format $$$s$$$. Reorder it to adhere to format $$$f$$$.
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$): the number of test cases. Then, $$$t$$$ test cases follow.
The first line of a test case contains four integers $$$n$$$, $$$m$$$, $$$r$$$, $$$c$$$ ($$$1 \leq r \leq n \leq 3 \cdot 10^5$$$, $$$1 \leq c \leq m \leq 3 \cdot 10^5$$$, $$$r$$$ divides $$$n$$$, $$$c$$$ divides $$$m$$$): the dimensions of the matrix and the dimensions of the blocks.
The second line contains two formats $$$s$$$ and $$$f$$$. Each of them is one of ND, ZZ, ZN, NZ, and NN.
The third line contains $$$n \cdot m$$$ integers $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_{nm}$$$ ($$$-10^9 \leq a_i \leq 10^9$$$): the encoded matrix in format $$$s$$$.
It is guaranteed that the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.
For each test case, print $$$n \cdot m$$$ integers on a separate line: the elements of the same matrix in format $$$f$$$.
34 3 2 1ND ZZ1 2 3 4 5 6 7 8 9 10 11 124 4 2 2ZN ND1 5 2 6 3 7 4 8 9 13 10 14 11 15 12 164 4 2 2NZ NN1 2 -7 -6 5 6 -3 -2 3 4 -5 -4 7 8 -1 0
1 4 2 5 3 6 7 10 8 11 9 121 2 3 4 5 6 7 8 9 10 11 12 13 14 15 161 -7 2 -6 5 -3 6 -2 3 -5 4 -4 7 -1 8 0
| Name |
|---|


