P11020 「LAOI-6」Radiation

Tom_nik and Uurist are playing a game on an $n\times m$ board. Initially the board is empty. First, Uurist places $k$ stones on the board, and then Tom_nik will destroy all the stones. **However, for one operation, Tom_nik can only destroy stones that share a row or column**. Uurist will destroy the stones using the minimum number of operations. However, Tom_nik wants to maximize the number of operations Uurist will take by placing the stone in a proper way. You need to give him a specific placement such that Tom_nik's goal will be achieved. Note that Uurist has to destroy **all** of the stones.

**This task contains multiple testcases.** For each test, the first line of the input contains an integer $T$, indicating the number of testcases. Then $T$ lines follow, each line containing three integers $n,m,k$.

For each test case, output $n$ lines containing $nm$ characters, indicating your answer: the character on the $i$-th line and $j$-th column should be "$\texttt S$" (withut quotes), if you think you should place a stone on this grid; otherwise it should be "$\texttt .$" (without quotes). You should guarantee that the number of grids with $\texttt S$ on it is $k$. If there are multiple answers, print any.

Subtasks are used in this problem. Subtask 1 ($20$ points): it is guaranteed that $k \leq \min(n,m)$. Subtask 2 ($12$ points): it is guaranteed that $n = 2$. Subtask 3 ($18$ points): it is guaranteed that $T,n,m \leq 10$. Subtask 4 ($20$ points): it is guaranteed that $T \leq 10$, $n,m \leq 300$. Subtask 5 ($30$ points): No special constraint. For all tests, it is guaranteed that $1 \leq T \leq 10^4$, $1 \leq n,m \leq 2 \times 10^3$, $0 \leq k \leq nm$, the sum of $nm$ over all test cases does not exceed $5\times 10^6$.