有一个 $n$ 行 $m$ 列的网格。每个单元格中都有一个箭头，指向向上（U）、向下（D）、向左（L）或向右（R）。

在每次操作中，你可以移除恰好一个箭头。然而，要移除一个箭头，在其指向的方向上不能有其他箭头。更具体地说，设 $s_{i,j}$ 为位于第 $i$ 行第 $j$ 列的箭头。要移除 $s_{i,j}$：

• 如果 $s_{i,j} = \text{U}$，则所有满足 $1 \le k < i$ 的 $s_{k,j}$ 必须在此之前被移除。
• 如果 $s_{i,j} = \text{D}$，则所有满足 $i < k \le n$ 的 $s_{k,j}$ 必须在此之前被移除。
• 如果 $s_{i,j} = \text{L}$，则所有满足 $1 \le k < j$ 的 $s_{i,k}$ 必须在此之前被移除。
• 如果 $s_{i,j} = \text{R}$，则所有满足 $j < k \le m$ 的 $s_{i,k}$ 必须在此之前被移除。

对于每个箭头，分别回答以下问题：移除它所需的最少操作次数是多少？

输入格式

每个输入包含多个测试用例。输入的第一行包含一个整数 $T$（$1 \le T \le 10^3$），表示测试用例的数量。对于每个测试用例：

第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 5 \times 10^4$，$n \times m \le 5 \times 10^4$），表示网格的行数和列数。

接下来的 $n$ 行中，第 $i$ 行包含一个长度为 $m$ 的字符串 $s_{i,1}s_{i,2} \dots s_{i,m}$（$s_{i,j} \in \{\text{U}, \text{D}, \text{L}, \text{R}\}$），其中 $s_{i,j}$ 表示第 $i$ 行第 $j$ 列的箭头。

保证所有测试用例的 $n \times m$ 之和不超过 $5 \times 10^4$。

输出格式

对于每个测试用例，输出 $n$ 行。第 $i$ 行包含 $m$ 个由空格隔开的整数 $a_{i,1}, a_{i,2}, \dots, a_{i,m}$，其中 $a_{i,j}$ 是移除箭头 $s_{i,j}$ 所需的最少操作次数。如果无法移除箭头 $s_{i,j}$，则 $a_{i,j}$ 应为 $-1$。

样例

输入样例 1

2
4 3
RRD
DUL
RDD
RRR
1 2
LR

输出样例 1

-1 -1 -1
7 -1 -1
5 3 2
3 2 1
1 1