CF1991G.Grid Reset

给定一个 $n$ 行 $m$ 列的格子矩阵，初始所有格子都是白色。另外给定一个整数 $k$。

你将执行如下两类操作共 $q$ 次：

• $\texttt H$（水平操作）：在格子矩阵中选择一个 $1$ 行 $k$ 列，且所有格子均为白色的格子矩阵，并将其中的所有格子涂黑。
• $\texttt V$（纵向操作）：在格子矩阵中选择一个 $k$ 行 $1$ 列，且所有格子均为白色的格子矩阵，并将其中的所有格子涂黑。

每次操作之后，如果任意一行或一列所有格子都被涂成了黑色，则这一行或一列的所有格子自动被重置成白色。特别的，如果某一个格子所在的行和列都被涂成了黑色，则该格子所处的行和列的所有格子也将自动被重置成白色。

现在，对于 $q$ 次操作中的每次操作，请指定一个矩阵，使得所有 $q$ 次操作都能够进行，或者报告无论如何指定矩阵都不能使得所有 $q$ 次操作都能够进行。

本题包含多组数据。

第一行输入一个整数 $t$，表示数据组数。

对于每组数据，第一行输入四个整数 $n,m,k,q$，分别代表格子矩阵的行数、列数、每次操作选定的矩阵的大小和操作次数。
第二行输入一个长度为 $q$ 的字符串 $s$，表示操作序列。

对于每组数据，如果无论如何指定矩阵都不能使得所有 $q$ 次操作都能够进行，输出一行 $-1$。否则，输出 $q$ 行，第 $x$ 行两个整数 $i,j$，表示第 $x$ 次操作所指定的矩阵的左上角的格子所在的行和列。

对于所有数据：

• $1\leqslant t\leqslant 1000$。
• $1\leqslant n,m\leqslant 100,\color{Red}1\leqslant k\leqslant \min\{n,m\}$。
• $1\leqslant q\leqslant 1000,\sum q\leqslant 1000$。

输入输出样例参见下文。

Translated by Eason_AC。