P13786 [eJOI 2022] LCS of Permutations

For two sequences $x$ and $y$, we define $LCS(x, y)$ as the length of their longest common subsequence. You are given 4 integers $n, a, b, c$. Determine if there exist 3 permutations $p, q, r$ of integers from 1 to $n$, such that: - $LCS(p, q) = a$ - $LCS(p, r) = b$ - $LCS(q, r) = c$ If such permutations exist, find any such triple of permutations. A permutation $p$ of integers from 1 to $n$ is a sequence of length $n$ such that all elements are distinct integers in the range $[1, n]$. For example, $(2, 4, 3, 5, 1)$ is a permutation of integers from 1 to 5 while $(1, 2, 1, 3, 5)$ and $(1, 2, 3, 4, 6)$ are not. A sequence $c$ is a subsequence of a sequence $d$ if $c$ can be obtained from $d$ by deletion of several (possibly, zero or all) elements. For example, $(1, 3, 5)$ is a subsequence of $(1, 2, 3, 4, 5)$ while $(3, 1)$ is not. The longest common subsequence of the sequences $x$ and $y$ is the longest sequence $z$ which is a subsequence of both $x$ and $y$. For example, the longest common subsequence of the sequences $x = (1, 3, 2, 4, 5)$ and $y = (5, 2, 3, 4, 1)$ is $z = (2, 4)$ since it is a subsequence of both sequences and is the longest among such subsequences. $LCS(x, y)$ is the length of the longest common subsequence, which is 2 in the example above.

The first line of the input contains a single integer $t$ ($1 \leq t \leq 10^5$) - the number of test cases. The description of the test cases follows. The only line of each test case contains 5 integers $n, a, b, c, output$ ($1 \leq a \leq b \leq c \leq n \leq 2 \cdot 10^5$, $0 \leq output \leq 1$). If $output = 0$, just determine if such permutations exist. If $output = 1$, you also have to find such a triple of permutations if it exists. It's guaranteed that the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.

For each test case, in the first line, output "YES", if such permutations $p, q, r$ exist, and "NO" otherwise. If $output = 1$, and such permutations exist, output three more lines: In the first line output $n$ integers $p_1, p_2, \ldots, p_n$ - the elements of the permutation $p$. In the second line output $n$ integers $q_1, q_2, \ldots, q_n$ - the elements of the permutation $q$. In the third line output $n$ integers $r_1, r_2, \ldots, r_n$ - the elements of the permutation $r$. If there are multiple triples, output any of them. You can output each letter in any case (for example, "YES", "Yes", "yes", "yEs", "yEs" will be recognized as a positive answer).

### Note In the first test case, $LCS((1), (1))$ is 1. In the second test case, it can be shown that no such permutations exist. In the third test case, one of the examples is $p = (1, 3, 5, 2, 6, 4)$, $q = (3, 1, 5, 2, 4, 6)$, $r = (1, 3, 5, 2, 4, 6)$. It's easy to see that: - $LCS(p, q) = 4$ (one of the longest common subsequences is $(1, 5, 2, 6)$) - $LCS(p, r) = 5$ (one of the longest common subsequences is $(1, 3, 5, 2, 4)$) - $LCS(q, r) = 5$ (one of the longest common subsequences is $(3, 5, 2, 4, 6)$) In the fourth test case, it can be shown that no such permutations exist. ### Scoring 1. (3 points): $a = b = 1, c = n, output = 1$ 2. (8 points): $n \leq 6, output = 1$ 3. (10 points): $c = n, output = 1$ 4. (17 points): $a = 1, output = 1$ 5. (22 points): $output = 0$ 6. (40 points): $output = 1$