Problem Description

In this problem, “substring” means:

If there is a segment of continuous characters in a string $s$ that forms a string $p$, then $p$ is a substring of $s$.

We use a string to represent a sheet music score, and use a character to represent each note.

We define an “accent” as the occurrence of two consecutive identical characters in the sheet music. For example, there are $4$ “accents” in $\tt eeeee$.

Now Sept is going to write a sheet music of length $n$ for Tpes to see. His evaluation rules are as follows:

• Each time an “accent” appears in the sheet music, his anger value increases by $a$.
• For each substring of length $k$ that contains no “accent”, his anger value increases by $b$.

Given $n,k,a,b$, please help Sept construct a sheet music such that Tpes’s anger value $x$ is minimized.

Input Format

This problem has multiple test cases.

The first line contains an integer $T$, indicating the number of test cases.

The next $T$ lines each contain four integers $n,k,a,b$, with meanings as described in the statement.

Output Format

Output a total of $2 \cdot T$ lines. For each test case, output two lines:

• Line 1: Tpes’s minimum anger value $x$.
• Line 2: The sheet music you constructed.

2
4 5 2 2
8 6 3 2

0
Sept
3
2023yyds

Hint

Constraints and Notes

This problem uses bundled testdata.

For $100\%$ of the testdata, $2\le T\le 100$, $2\le n,k\le 10^5$, $1\le a,b\le 10^9$. Within a single test case, it is guaranteed that $\sum n\le 2\times 10^5$.

Output Notes

Outputting $x$ and constructing the sheet music can be considered as two separate subtasks. If you can only finish one of them, please use a valid character or number as a placeholder in the position corresponding to the other subtask.

You may output any characters in the sheet music, including digits, uppercase and lowercase letters, etc., but spaces are not allowed.

Special Judge Return Message Explanation

This problem uses a Special Judge to determine whether your answer is correct.

checker.cpp will return messages in the form $\texttt{Score=}\text A,\texttt{Type=}\text B$.

The $\tt Score$ category indicates your scoring status. $\text A$ can take the following values:

• $\text A=1$, meaning:
  $\text{Accepted.} \texttt{ Your Ans and SM are both proper.}$
  This means all $T$ answers meet the requirements.
• $\text A=2$, meaning:
  $\text{Partially Correct.}\texttt{ All Ans are right.}$
  This means in this test point, all your reported $x$ are correct, and you can get $20\%$ of the score for this test point.
• $\text A=3$, meaning:
  $\text{Partially Correct.}\texttt{ You pass 70\% tests!}$
  This means in this test point, the number of test cases you answered correctly is at least $\lfloor0.7\times T\rfloor$ (both $x$ and the sheet music meet the requirements), and you can get $10\%$ of the score for this test point.
• $\text A=4$, meaning you can only get $0$ points for this test point.

The $\tt Type$ category indicates your error type. $\text B$ can take the following values:

• $\text B=0$, meaning all your answers are correct, paired with $\text A=1$.
• $\text B=1$, meaning:
  $\text{Wrong Answer.}\texttt{ The length of your SM is not right!}$
  This means in one test case, the length of the sheet music you constructed is not $n$.
• $\text B=2$, meaning:
  $\text{Wrong Answer.}\texttt{ Your Ans is not right!}$
  This means in one test case, the value of $x$ you output is wrong.
• $\text B=3$, meaning:
  $\text{Wrong Answer.}\texttt{ Your Ans and SM are not matched!}$
  This means in one test case, the anger value produced by your constructed sheet music is not $x$.

Here, $\text{Ans, SM}$ stand for Answer (the value of $x$) and Sheet Music (the sheet music).

Note that $\tt Type$ only reflects the type of the first error in this test point.

Translated by ChatGPT 5