Description

对于两个序列 $x$ 和 $y$，我们定义 $LCS(x, y)$ 为它们的最长公共子序列的长度。

现在给定 4 个整数 $n, a, b, c$。请判断是否存在 3 个 $1 \sim n$ 的排列 $p, q, r$，满足：

• $LCS(p, q) = a$
• $LCS(p, r) = b$
• $LCS(q, r) = c$

如果存在这样的排列，请输出任意一组满足条件的排列三元组。

一个排列 $p$ 是 $1 \sim n$ 的一个排列，当且仅当 $p$ 是长度为 $n$ 的序列，并且其中所有元素互不相同，且取值范围为 $[1, n]$。例如，$(2, 4, 3, 5, 1)$ 是 $1 \sim 5$ 的一个排列，而 $(1, 2, 1, 3, 5)$ 和 $(1, 2, 3, 4, 6)$ 则不是。

一个序列 $c$ 是序列 $d$ 的一个子序列，当且仅当 $c$ 可以通过从 $d$ 中删除若干（可能是零个，也可能是全部）元素得到。例如，$(1, 3, 5)$ 是 $(1, 2, 3, 4, 5)$ 的子序列，而 $(3, 1)$ 不是。

两个序列 $x$ 和 $y$ 的最长公共子序列，指的是一个同时为 $x$ 和 $y$ 的子序列的最长序列。例如，$x = (1, 3, 2, 4, 5)$ 与 $y = (5, 2, 3, 4, 1)$ 的最长公共子序列为 $z = (2, 4)$，因为它既是两者的子序列，又是所有公共子序列中最长的一个。此时 $LCS(x, y) = 2$。

Input Format

输入的第一行包含一个整数 $t$（$1 \leq t \leq 10^5$），表示测试用例的数量。接下来是 $t$ 个测试用例。

每个测试用例包含一行 5 个整数 $n, a, b, c, output$（$1 \leq a \leq b \leq c \leq n \leq 2 \cdot 10^5$, $0 \leq output \leq 1$）。

• 若 $output = 0$，仅需判断是否存在这样的排列。
• 若 $output = 1$，在存在的情况下，还需输出一组满足条件的排列三元组。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

Output Format

对于每个测试用例，若存在满足条件的排列 $p, q, r$，则第一行输出 "YES"，否则输出 "NO"。

如果 $output = 1$ 且存在解，则再输出三行：

• 第一行输出排列 $p$：$p_1, p_2, \ldots, p_n$
• 第二行输出排列 $q$：$q_1, q_2, \ldots, q_n$
• 第三行输出排列 $r$：$r_1, r_2, \ldots, r_n$

如果有多组解，输出任意一组即可。

输出时字母大小写不敏感（例如 "YES"、"Yes"、"yes"、"yEs" 都视为正确）。

8
1 1 1 1 1
4 2 3 4 1
6 4 5 5 1
7 1 2 3 1
1 1 1 1 0
4 2 3 4 0
6 4 5 5 0
7 1 2 3 0

YES
1
1
1
NO
YES
1 3 5 2 6 4
3 1 5 2 4 6
1 3 5 2 4 6
NO
YES
NO
YES
NO

Hint

样例解释

在第一个测试用例中，$LCS((1), (1)) = 1$。

在第二个测试用例中，可以证明不存在这样的排列。

在第三个测试用例中，其中一种可能的解为：

• $p = (1, 3, 5, 2, 6, 4)$
• $q = (3, 1, 5, 2, 4, 6)$
• $r = (1, 3, 5, 2, 4, 6)$

此时：

• $LCS(p, q) = 4$（例如 $(1, 5, 2, 6)$ 是一个最长公共子序列）
• $LCS(p, r) = 5$（例如 $(1, 3, 5, 2, 4)$）
• $LCS(q, r) = 5$（例如 $(3, 5, 2, 4, 6)$）

在第四个测试用例中，可以证明不存在这样的排列。

评分规则

1. （3 分）：$a = b = 1, c = n, output = 1$
2. （8 分）：$n \leq 6, output = 1$
3. （10 分）：$c = n, output = 1$
4. （17 分）：$a = 1, output = 1$
5. （22 分）：$output = 0$
6. （40 分）：$output = 1$

翻译由 ChatGPT-5 完成