시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 1024 MB1000.000%

문제

For two sequences $x$ and $y$, we define $\text{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:

  • $\text{LCS}(p, q) = a$
  • $\text{LCS}(p, r) = b$
  • $\text{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. $\text{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 ≤ t ≤ 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 ≤ a ≤ b ≤ c ≤ n ≤ 2 ⋅ 10^5$, $0 ≤ output ≤ 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 ⋅ 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 , \dots , p_n$ - the elements of the permutation $p$.

In the second line output $n$ integers $q_1 , q_2 , \dots , q_n$ - the elements of the permutation $q$.

In the third line output $n$ integers $r_1 , r_2 , \dots , 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).

서브태스크

번호배점제한
13

$a = b = 1$, $c = n$, $output = 1$

28

$n ≤ 6$, $output = 1$

310

$c = n$, $output = 1$

417

$a = 1$, $output = 1$

522

$output = 0$

640

$output = 1$

예제 입력 1

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

예제 출력 1

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

노트

In the first test case, $\text{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:

  • $\text{LCS}(p, q) = 4$ (one of the longest common subsequences is $(1, 5, 2, 6)$)
  • $\text{LCS}(p, r) = 5$ (one of the longest common subsequences is $(1, 3, 5, 2, 4)$)
  • $\text{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.

채점 및 기타 정보

  • 예제는 채점하지 않는다.
  • 이 문제의 채점 우선 순위는 2이다.