题目描述

本题中「子串」指：

若字符串 $s$ 中有一段连续的字符构成字符串 $p$，则 $p$ 是 $s$ 的子串。

我们用一个字符串代替一份乐谱，用字符代替每一个音符。

我们定义「重音」表示乐谱中出现了两个连续的相同字符，如 $\tt eeeee$ 中存在 $4$ 个「重音」。

现在 Sept 准备写一份长度为 $n$ 的乐谱给 Tpes 看，他对乐谱的评价标准如下：

• 乐谱中每出现一个「重音」，他的愤怒值就会增加 $a$。
• 乐谱中每有一段长度为 $k$ 的子串中不存在「重音」，他的愤怒值就会增加 $b$。

现在已知 $n,k,a,b$，请你帮 Sept 构造出一份乐谱，使得 Tpes 的愤怒值 $x$ 最小。

输入格式

本题有多组数据。

第一行一个整数 $T$，表示数据组数。

接下来 $T$ 行，每行两个整数 $n,k,a,b$，意义如题目所述。

输出格式

共 $2 \cdot T$ 行，对于每组数据都输出两行：

• 第 1 行表示 Tpes 最小的愤怒值 $x$。
• 第 2 行表示你构造出的乐谱。

2
4 5 2 2
8 6 3 2

0
Sept
3
2023yyds

提示

数据规模与约定

本题采用捆绑测试。

$\bf{Subtask}$	$\bm{n\le}$	$\bm{\sum n\le}$	$\bm{T\le}$	$\bf{Score}$
$\sf 1$	$6$	$10$	$3$	$\tt 10$
$\sf 2$	$10^3$	$2\times 10^3$	无特殊限制	$\tt 30$
$\sf 3$	无特殊限制			$\tt 60$

对于 $100\%$ 的数据，有 $2\le T\le 100$，$2\le n,k\le 10^5$，$1\le a,b\le 10^9$。单组数据内保证 $\sum n\le 2\times 10^5$。

输出注意事项

输出 $x$ 和构造乐谱可以看作是两个子问题，如果你只会完成其中的一个，请在另一个子问题对应的地方用符合要求的字符或数字占位。

乐谱中你可以输出任意字符，包括数字、大小写字母等，但不能出现空格。

Special Judge 返回信息说明

本题采用 Special Judge 判断你的答案是否正确。

checker.cpp 将会以 $\texttt{Score=}\text A,\texttt{Type=}\text B$ 的方式返回信息。

$\tt Score$ 类表示你的得分情况，$\text A$ 有以下取值：

• $\text A=1$，表示含义如下：
  $\underline\text{Accepted.} \texttt{ Your Ans and SM are both proper.}$
  代表 $T$ 组答案全部符合要求。
• $\text A=2$，表示含义如下：
  $\underline\text{Partially Correct.}\texttt{ All Ans are right.}$
  表示该测试点中你的回答中 $x$ 全部正确，你能得到该测试点 $20\%$ 的分数。
• $\text A=3$，表示含义如下：
  $\underline\text{Partially Correct.}\texttt{ You pass 70\% tests!}$
  表示该测试点中你的回答正确的组数不少于$\lfloor0.7\times T\rfloor$（$x$ 与乐谱均符合要求），你能得到该测试点 $10\%$ 的分数。
• $\text A=4$，表示该测试点你只能拿到 $0$ 分。

$\tt Type$ 类表示你的得分情况，$\text B$ 有以下取值：

• $\text B=0$，表示你的答案全部正确，与 $\text A=1$ 配对。
• $\text B=1$，表示含义如下：
  $\underline\text{Wrong Answer.}\texttt{ The length of your SM is not right!}$
  代表你在一组数据中构造的乐谱的长度不为 $n$。
• $\text B=2$，表示含义如下：
  $\underline\text{Wrong Answer.}\texttt{ Your Ans is not right!}$
  代表你在一组数据中 $x$ 的值错误。
• $\text B=3$，表示含义如下：
  $\underline\text{Wrong Answer.}\texttt{ Your Ans and SM are not matched!}$
  代表你在一组数据中构造的乐谱使 Tpes 产生的愤怒值不为 $x$。

这里 $\text{Ans, SM}$ 分别表示 Answer（$x$ 的值）和 Sheet Music（乐谱）。

注意到 $\tt Type$ 只会反映你在该测试点中第一次错误的类型。