题目背景

English statement. You must submit your code at the Chinese version of the statement.

题目描述

小 T 和 小 U 在一个 $n \times m$ 的初始为空的棋盘上玩游戏。小 T 先在上面摆 $k$ 个石头，然后小 U 会使用宇宙射线毁掉所有石头。但是小 U 的宇宙射线威力有限，只能每次销毁一行或一列的石头。

小 U 不想过多用他的宇宙射线发射器，所以他会按照最优策略销毁石头。反之，小 T 偏偏想让小 U 发射最多的宇宙射线，所以他会摆放石头以做到这一点。问题来了：小 T 不会摆放了。你能够找到一种方法帮助小 T 达到目标吗？

输入格式

本题有多组数据。

第一行一个整数 $T$。

然后 $T$ 行，每行 $n,m,k$ 三个整数，表示这组数据的游戏设定。

输出格式

对于每组数据，输出 $n$ 行 $m$ 列共 $nm$ 个字符，第 $i$ 行第 $j$ 个字符如果为 S 那么代表棋盘的第 $i$ 行第 $j$ 列有石头；如果为 . 那么代表棋盘的第 $i$ 行第 $j$ 列没石头。

你需要保证每组数据中输出的字符 S 的个数为 $k$。

2
3 5 2
5 4 7

S....
....S
.....
S..S
...S
S.S.
...S
.S..

提示

本题采用捆绑测试。

子任务 1（$20$ 分）：保证 $k \leq \min(n,m)$。

子任务 2（$12$ 分）：保证 $n = 2$。

子任务 3（$18$ 分）：保证 $T,n,m \leq 10$。

子任务 4（$20$ 分）：保证 $T \leq 10$，$n,m \leq 300$。依赖子任务 $3$。

子任务 5（$30$ 分）：无特殊限制。依赖子任务 $1 \sim 4$。

对于所有数据，保证 $1 \leq T \leq 10^4$，$1 \leq n,m \leq 2 \times 10^3$，$0 \leq k \leq nm$，$\sum nm \leq 5 \times 10^6$。