#P17715. [2026年江苏省队集训]记忆中的排列

[2026年江苏省队集训]记忆中的排列

题目描述

小Z珍藏了三个排列 P,Q,RP,Q,R,据说它们记录着过往的种种。

可如今时过境迁,这些排列早已残缺到无法辨认。为了重塑那段时光,小Z开始了“追忆”——可惜的是,他并不会“追忆”,早已记不起完整的排列了。他只依稀记得一些重复出现的时间线:具体来说,他还能想起这三个排列两两之间的最长公共子序列的长度。

为了找回丢失的排列,小Z找到了传说中的L神。L神扫了一眼,便看穿了所有可能的结果,还不忘嘲讽一句:“你会了之后就很简单了啊。”

无奈之下,可怜的小Z只好找到了你。请你帮他找出一组可能的排列吧——当然,小Z的记忆也常常出错,如果不存在任何一组能满足条件的排列,也请告诉小Z哦~

输入格式

第一行一个整数 TT,表示测试用例的数量。接下来是 tt 个测试用例。

每个测试用例包含一行 55 个整数 n,a,b,c,outputn,a,b,c,output,表示 LCS(P,Q)=a,LCS(P,R)=b,LCS(Q,R)=cLCS(P,Q)=a,LCS(P,R)=b,LCS(Q,R)=c,outputoutput 表示询问类型:

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

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

输出格式

对于每个测试用例,若存在满足条件的排列 P,Q,RP,Q,R,则第一行输出 "YES",否则输出 "NO"。

如果 output=1output=1 且存在解,则再输出三行,分别表示排列 P,Q,RP,Q,R。

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

样例输入

3
1 1 1 1 1
4 2 3 4 1
6 4 5 5 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

数据范围

对于全部测试数据,$1\leq a,b,c\leq n\leq 2\cdot 10^5,output \in \{0,1\}$。

子任务编号 分值 n a b c output
1 10 ≤2⋅105\leq 2\cdot 10^5 =1=1 =n=n =1=1
2 ≤6\leq 6 ≤n\leq n ≤n\leq n ≤n\leq n
3 15 ≤2⋅105\leq 2\cdot 10^5 =n=n
4 =1=1 ≤n\leq n
5 20 ≤n\leq n =0=0
6 30 =1=1