311207: CF1949K. Make Triangle

K. Make Triangletime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given $n$ positive integers $x_1, x_2, \ldots, x_n$ and three positive integers $n_a, n_b, n_c$ satisfying $n_a+n_b+n_c = n$.

You want to split the $n$ positive integers into three groups, so that:

• The first group contains $n_a$ numbers, the second group contains $n_b$ numbers, the third group contains $n_c$ numbers.
• Let $s_a$ be the sum of the numbers in the first group, $s_b$ be the sum in the second group, and $s_c$ be the sum in the third group. Then $s_a, s_b, s_c$ are the sides of a triangle with positive area.

Determine if this is possible. If this is possible, find one way to do so.

Input

Each test contains multiple test cases. The first line contains an integer $t$ ($1\le t\le 100\,000$) — the number of test cases. The descriptions of the $t$ test cases follow.

The first line of each test case contains the integers $n, n_a, n_b, n_c$ ($3 \leq n \leq 200\,000, 1\leq n_a,n_b,n_c \leq n-2, n_a+n_b+n_c = n$) — the number of integers to split into three groups, and the desired sizes of the three groups.

The second line of each test case contains $n$ integers $x_1, x_2, \ldots, x_n$ ($1 \leq x_i \leq 10^{9}$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $200\,000$.

Output

For each test case, print $\texttt{YES}$ if it is possible to split the numbers into three groups satisfying all the conditions. Otherwise, print $\texttt{NO}$.

If such a split exists, then describe the three groups as follows.

On the next line, print $n_a$ integers $a_1, a_2, \ldots, a_{n_a}$ — the numbers in the first group.

On the next line, print $n_b$ integers $b_1, b_2, \ldots, b_{n_b}$ — the numbers in the second group.

On the next line, print $n_c$ integers $c_1, c_2, \ldots, c_{n_c}$ — the numbers in the third group.

These $n_a+n_b+n_c=n$ integers should be a permutation of $x_1, x_2, \ldots, x_n$, and they should satisfy the conditions from the statement.

If there are multiple solutions, print any of them.

ExampleInput

4
6 2 2 2
1 1 1 1 1 1
5 3 1 1
1 1 1 1 1
6 2 2 2
1 1 1 1 1 3
8 1 2 5
16 1 1 1 1 1 1 12

Output

YES
1 1 
1 1 
1 1 
NO
NO
YES
16 
12 1 
1 1 1 1 1 

Note

In the first test case, we can put two $1$s into each group: the sum in each group would be $2$, and there exists a triangle with positive area and sides $2$, $2$, $2$.

In the second and third test cases, it can be shown that there is no such way to split numbers into groups.

In the fourth test case, we can put number $16$ into the first group, with sum $16$, numbers $12$ and $1$ into the second group, with sum $13$, and the remaining five $1$s into the third group, with sum $5$, as there exists a triangle with positive area and sides $16, 13, 5$.

题目大意：
给定n个正整数\(x_1, x_2, \ldots, x_n\)和三个正整数\(n_a, n_b, n_c\)，满足\(n_a + n_b + n_c = n\)。要求将这n个正整数分成三组，使得：

- 第一组包含\(n_a\)个数，第二组包含\(n_b\)个数，第三组包含\(n_c\)个数。
- 设第一组的和为\(s_a\)，第二组的和为\(s_b\)，第三组的和为\(s_c\)，则\(s_a, s_b, s_c\)构成一个具有正面积的三角形的边长。

判断是否可以做到这一点。如果可以，找出一种分组方式。

输入数据格式：
每个测试包含多个测试用例。第一行包含一个整数\(t\)（\(1 \le t \le 100,000\)）——测试用例的数量。接下来是t个测试用例的描述。

每个测试用例的第一行包含四个整数\(n, n_a, n_b, n_c\)（\(3 \leq n \leq 200,000, 1 \leq n_a, n_b, n_c \leq n-2, n_a + n_b + n_c = n\)）——要分成三组的整数数量和三组的大小。

每个测试用例的第二行包含n个整数\(x_1, x_2, \ldots, x_n\)（\(1 \leq x_i \leq 10^9\)）。

保证所有测试用例的n之和不超过\(200,000\)。

输出数据格式：
对于每个测试用例，如果可以将数字分成满足所有条件的三组，则打印\texttt{YES}，否则打印\texttt{NO}。

如果存在这样的分组，则按以下格式描述三组：

- 在下一行打印\(n_a\)个整数\(a_1, a_2, \ldots, a_{n_a}\)——第一组的数字。
- 在下一行打印\(n_b\)个整数\(b_1, b_2, \ldots, b_{n_b}\)——第二组的数字。
- 在下一行打印\(n_c\)个整数\(c_1, c_2, \ldots, c_{n_c}\)——第三组的数字。

这\(n_a + n_b + n_c = n\)个整数应该是\(x_1, x_2, \ldots, x_n\)的一个排列，并且它们应该满足题目中的条件。

如果有多个解决方案，则打印其中任何一个。题目大意： 给定n个正整数\(x_1, x_2, \ldots, x_n\)和三个正整数\(n_a, n_b, n_c\)，满足\(n_a + n_b + n_c = n\)。要求将这n个正整数分成三组，使得： - 第一组包含\(n_a\)个数，第二组包含\(n_b\)个数，第三组包含\(n_c\)个数。 - 设第一组的和为\(s_a\)，第二组的和为\(s_b\)，第三组的和为\(s_c\)，则\(s_a, s_b, s_c\)构成一个具有正面积的三角形的边长。 判断是否可以做到这一点。如果可以，找出一种分组方式。 输入数据格式： 每个测试包含多个测试用例。第一行包含一个整数\(t\)（\(1 \le t \le 100,000\)）——测试用例的数量。接下来是t个测试用例的描述。 每个测试用例的第一行包含四个整数\(n, n_a, n_b, n_c\)（\(3 \leq n \leq 200,000, 1 \leq n_a, n_b, n_c \leq n-2, n_a + n_b + n_c = n\)）——要分成三组的整数数量和三组的大小。 每个测试用例的第二行包含n个整数\(x_1, x_2, \ldots, x_n\)（\(1 \leq x_i \leq 10^9\)）。 保证所有测试用例的n之和不超过\(200,000\)。 输出数据格式： 对于每个测试用例，如果可以将数字分成满足所有条件的三组，则打印\texttt{YES}，否则打印\texttt{NO}。 如果存在这样的分组，则按以下格式描述三组： - 在下一行打印\(n_a\)个整数\(a_1, a_2, \ldots, a_{n_a}\)——第一组的数字。 - 在下一行打印\(n_b\)个整数\(b_1, b_2, \ldots, b_{n_b}\)——第二组的数字。 - 在下一行打印\(n_c\)个整数\(c_1, c_2, \ldots, c_{n_c}\)——第三组的数字。 这\(n_a + n_b + n_c = n\)个整数应该是\(x_1, x_2, \ldots, x_n\)的一个排列，并且它们应该满足题目中的条件。 如果有多个解决方案，则打印其中任何一个。