#P18322. Inversions of PQ and QP

Inversions of PQ and QP

Inversions of PQ and QP

给定三个整数 N,A,BN,A,B。请判断是否存在两个由 1,2,…,N1,2,\ldots,N 组成的排列 P=(P1,P2,…,PN)P=(P_1,P_2,\ldots,P_N) 和 Q=(Q1,Q2,…,QN)Q=(Q_1,Q_2,\ldots,Q_N),满足:

  • 序列 (PQ1,PQ2,…,PQN)(P_{Q_1},P_{Q_2},\ldots,P_{Q_N}) 的逆序对数恰好为 AA;
  • 序列 (QP1,QP2,…,QPN)(Q_{P_1},Q_{P_2},\ldots,Q_{P_N}) 的逆序对数恰好为 BB。

如果存在,请构造任意一组符合要求的排列。

长度为 MM 的序列 RR 的逆序对数,定义为满足 1≤i<j≤M1\le i<j\le M 且 Ri>RjR_i>R_j 的整数对 (i,j)(i,j) 的数量。

输入格式

第一行一个整数 TT,表示测试用例的数量。

接下来 TT 行,每行三个整数 N,A,BN,A,B,描述一个测试用例。

输出格式

依次输出每个测试用例的答案。

如果不存在符合要求的排列,输出一行 No。

否则,按以下格式输出三行:

Yes
P1 P2 ... PN
Q1 Q2 ... QN

两行分别给出排列 PP 和排列 QQ。有多个答案时,输出任意一个均可。

数据范围

  • 1≤T≤2×1051\le T\le2\times10^5;
  • 1≤N≤2×1051\le N\le2\times10^5;
  • 0≤A,B≤N(N−1)/20\le A,B\le N(N-1)/2;
  • 同一输入文件中,所有测试用例的 NN 之和不超过 2×1052\times10^5;
  • 所有输入值均为整数。

样例

样例输入 1

3
3 3 1
3 1 2
8 13 11

样例输出 1

Yes
1 3 2
2 3 1
No
Yes
2 5 8 4 6 3 7 1
2 1 8 5 3 7 4 6

说明

第一个测试用例中,样例输出的两个复合序列分别为 (3,2,1)(3,2,1) 和 (2,1,3)(2,1,3),逆序对数分别为 33 和 11。