package main
import (
"bufio"
"os"
"sort"
)
type FastScanner struct {
r *bufio.Reader
}
func NewFastScanner() *FastScanner {
return &FastScanner{r: bufio.NewReaderSize(os.Stdin, 1<<20)}
}
func (fs *FastScanner) NextInt64() int64 {
var sign int64 = 1
var val int64
c, err := fs.r.ReadByte()
for (c < '0' || c > '9') && c != '-' {
c, err = fs.r.ReadByte()
if err != nil {
return 0
}
}
if c == '-' {
sign = -1
c, _ = fs.r.ReadByte()
}
for c >= '0' && c <= '9' {
val = val*10 + int64(c-'0')
c, err = fs.r.ReadByte()
if err != nil {
break
}
}
if err == nil {
_ = fs.r.UnreadByte()
}
return val * sign
}
type Candidate struct {
groups [3][]int64
sums [3]int64
metric [3]int64
}
type PV struct {
v int64
idx int
}
func sorted3Desc(a, b, c int64) [3]int64 {
x, y, z := a, b, c
if x < y {
x, y = y, x
}
if y < z {
y, z = z, y
}
if x < y {
x, y = y, x
}
return [3]int64{x, y, z}
}
func betterMetric(a, b [3]int64) bool {
if a[0] != b[0] {
return a[0] < b[0]
}
if a[1] != b[1] {
return a[1] < b[1]
}
return a[2] < b[2]
}
func isValidCandidate(c Candidate, caps [3]int, total int64) bool {
for i := 0; i < 3; i++ {
if len(c.groups[i]) != caps[i] {
return false
}
}
return 2*c.metric[0] < total
}
func deepCopyCandidate(c Candidate) Candidate {
var d Candidate
d.sums = c.sums
d.metric = c.metric
for i := 0; i < 3; i++ {
d.groups[i] = append([]int64(nil), c.groups[i]...)
}
return d
}
func max3(a, b, c int64) int64 {
if a < b {
a = b
}
if a < c {
a = c
}
return a
}
func simulateGreedy(desc []int64, capsActual [3]int, perm [3]int, tieMode int) Candidate {
var caps [3]int
for i := 0; i < 3; i++ {
caps[i] = capsActual[perm[i]]
}
var groups [3][]int64
for i := 0; i < 3; i++ {
groups[i] = make([]int64, 0, caps[i])
}
var sums [3]int64
var cnt [3]int
for _, v := range desc {
best := -1
for i := 0; i < 3; i++ {
if cnt[i] >= caps[i] {
continue
}
if best == -1 {
best = i
continue
}
if sums[i] != sums[best] {
if sums[i] < sums[best] {
best = i
}
continue
}
remI := caps[i] - cnt[i]
remB := caps[best] - cnt[best]
if tieMode == 0 {
if remI != remB {
if remI < remB {
best = i
}
continue
}
} else if tieMode == 1 {
if remI != remB {
if remI > remB {
best = i
}
continue
}
} else {
if caps[i] != caps[best] {
if caps[i] < caps[best] {
best = i
}
continue
}
if remI != remB {
if remI < remB {
best = i
}
continue
}
}
if i < best {
best = i
}
}
groups[best] = append(groups[best], v)
sums[best] += v
cnt[best]++
}
var actualGroups [3][]int64
var actualSums [3]int64
for i := 0; i < 3; i++ {
actualGroups[perm[i]] = groups[i]
actualSums[perm[i]] = sums[i]
}
return Candidate{
groups: actualGroups,
sums: actualSums,
metric: sorted3Desc(actualSums[0], actualSums[1], actualSums[2]),
}
}
func simulateTwoEnded(valsAsc []int64, capsActual [3]int, perm [3]int, mode int) Candidate {
n := len(valsAsc)
l, r := 0, n-1
var caps [3]int
for i := 0; i < 3; i++ {
caps[i] = capsActual[perm[i]]
}
var groups [3][]int64
for i := 0; i < 3; i++ {
groups[i] = make([]int64, 0, caps[i])
}
var sums [3]int64
var cnt [3]int
for i := 0; i < 3; i++ {
v := valsAsc[r]
r--
groups[i] = append(groups[i], v)
sums[i] += v
cnt[i]++
}
for l <= r {
best := -1
for i := 0; i < 3; i++ {
if cnt[i] >= caps[i] {
continue
}
if best == -1 {
best = i
continue
}
if mode == 0 {
if sums[i] != sums[best] {
if sums[i] < sums[best] {
best = i
}
continue
}
} else {
if sums[i] != sums[best] {
if sums[i] > sums[best] {
best = i
}
continue
}
}
remI := caps[i] - cnt[i]
remB := caps[best] - cnt[best]
if remI != remB {
if remI < remB {
best = i
}
continue
}
if i < best {
best = i
}
}
v := valsAsc[l]
l++
groups[best] = append(groups[best], v)
sums[best] += v
cnt[best]++
}
var actualGroups [3][]int64
var actualSums [3]int64
for i := 0; i < 3; i++ {
actualGroups[perm[i]] = groups[i]
actualSums[perm[i]] = sums[i]
}
return Candidate{
groups: actualGroups,
sums: actualSums,
metric: sorted3Desc(actualSums[0], actualSums[1], actualSums[2]),
}
}
func simulateCanonical(valsAsc []int64, capsActual [3]int, perm [3]int) Candidate {
n := len(valsAsc)
l, r := 0, n-1
var caps [3]int
for i := 0; i < 3; i++ {
caps[i] = capsActual[perm[i]]
}
var groups [3][]int64
for i := 0; i < 3; i++ {
groups[i] = make([]int64, 0, caps[i])
}
var sums [3]int64
for i := 0; i < 3; i++ {
v := valsAsc[r]
r--
groups[i] = append(groups[i], v)
sums[i] += v
for t := 1; t < caps[i]; t++ {
v2 := valsAsc[l]
l++
groups[i] = append(groups[i], v2)
sums[i] += v2
}
}
var actualGroups [3][]int64
var actualSums [3]int64
for i := 0; i < 3; i++ {
actualGroups[perm[i]] = groups[i]
actualSums[perm[i]] = sums[i]
}
_ = n
return Candidate{
groups: actualGroups,
sums: actualSums,
metric: sorted3Desc(actualSums[0], actualSums[1], actualSums[2]),
}
}
func addBest(best *[]Candidate, cand Candidate, caps [3]int, total int64, limit int) {
if isValidCandidate(cand, caps, total) {
return
}
b := *best
pos := len(b)
for i := 0; i < len(b); i++ {
if betterMetric(cand.metric, b[i].metric) {
pos = i
break
}
}
if pos == len(b) {
if len(b) < limit {
*best = append(b, cand)
}
return
}
b = append(b, Candidate{})
copy(b[pos+1:], b[pos:])
b[pos] = deepCopyCandidate(cand)
if len(b) > limit {
b = b[:limit]
}
*best = b
}
func tryBestSwap(c *Candidate, total int64, h, o, t int) (bool, int, int, [3]int64) {
hPairs := make([]PV, len(c.groups[h]))
for i, v := range c.groups[h] {
hPairs[i] = PV{v: v, idx: i}
}
oPairs := make([]PV, len(c.groups[o]))
for i, v := range c.groups[o] {
oPairs[i] = PV{v: v, idx: i}
}
sort.Slice(hPairs, func(i, j int) bool {
if hPairs[i].v != hPairs[j].v {
return hPairs[i].v > hPairs[j].v
}
return hPairs[i].idx < hPairs[j].idx
})
sort.Slice(oPairs, func(i, j int) bool {
if oPairs[i].v != oPairs[j].v {
return oPairs[i].v < oPairs[j].v
}
return oPairs[i].idx < oPairs[j].idx
})
oVals := make([]int64, len(oPairs))
for i := range oPairs {
oVals[i] = oPairs[i].v
}
curMetric := c.metric
bestFound := false
bestH, bestO := -1, -1
bestMetric := curMetric
eval := func(a int64, idxH int, idxO int) {
if idxO < 0 || idxO >= len(oPairs) {
return
}
bv := oPairs[idxO].v
newH := c.sums[h] - a + bv
newO := c.sums[o] - bv + a
m := sorted3Desc(newH, newO, c.sums[t])
if betterMetric(m, bestMetric) {
bestFound = true
bestMetric = m
bestH = idxH
bestO = oPairs[idxO].idx
}
}
for _, hp := range hPairs {
a := hp.v
lo := sort.Search(len(oVals), func(i int) bool {
return 2*(c.sums[o]-oVals[i]+a) < total
})
hi := sort.Search(len(oVals), func(i int) bool {
return !(2*(c.sums[h]-a+oVals[i]) < total)
}) - 1
target := (c.sums[o] - c.sums[h] + 2*a) / 2
idxT := sort.Search(len(oVals), func(i int) bool {
return oVals[i] >= target
})
cands := [6]int{lo, lo - 1, hi, hi + 1, idxT, idxT - 1}
used := map[int]bool{}
for _, idx := range cands {
if idx < 0 || idx >= len(oPairs) || used[idx] {
continue
}
used[idx] = true
eval(a, hp.idx, idx)
}
}
if !bestFound {
return false, -1, -1, curMetric
}
return true, bestH, bestO, bestMetric
}
func repairCandidate(c *Candidate, total int64, caps [3]int) bool {
for iter := 0; iter < 15; iter++ {
c.metric = sorted3Desc(c.sums[0], c.sums[1], c.sums[2])
if isValidCandidate(*c, caps, total) {
return true
}
h := 0
if c.sums[1] > c.sums[h] {
h = 1
}
if c.sums[2] > c.sums[h] {
h = 2
}
o1, o2 := (h+1)%3, (h+2)%3
found1, idxH1, idxO1, m1 := tryBestSwap(c, total, h, o1, o2)
found2, idxH2, idxO2, m2 := tryBestSwap(c, total, h, o2, o1)
var chosenO, chosenIdxH, chosenIdxO int
var chosenMetric [3]int64
ok := false
if found1 && (!found2 || betterMetric(m1, m2)) {
ok = true
chosenO = o1
chosenIdxH = idxH1
chosenIdxO = idxO1
chosenMetric = m1
} else if found2 {
ok = true
chosenO = o2
chosenIdxH = idxH2
chosenIdxO = idxO2
chosenMetric = m2
}
if !ok || !betterMetric(chosenMetric, c.metric) {
break
}
a := c.groups[h][chosenIdxH]
b := c.groups[chosenO][chosenIdxO]
c.groups[h][chosenIdxH], c.groups[chosenO][chosenIdxO] = b, a
c.sums[h] = c.sums[h] - a + b
c.sums[chosenO] = c.sums[chosenO] - b + a
c.metric = sorted3Desc(c.sums[0], c.sums[1], c.sums[2])
}
c.metric = sorted3Desc(c.sums[0], c.sums[1], c.sums[2])
return isValidCandidate(*c, caps, total)
}
func writeInt64(w *bufio.Writer, x int64) {
if x == 0 {
w.WriteByte('0')
return
}
if x < 0 {
w.WriteByte('-')
x = -x
}
var buf [24]byte
n := 0
for x > 0 {
buf[n] = byte('0' + x%10)
n++
x /= 10
}
for i := n - 1; i >= 0; i-- {
w.WriteByte(buf[i])
}
}
func writeSlice(w *bufio.Writer, a []int64) {
for i, v := range a {
if i > 0 {
w.WriteByte(' ')
}
writeInt64(w, v)
}
w.WriteByte('\n')
}
func main() {
in := NewFastScanner()
out := bufio.NewWriterSize(os.Stdout, 1<<20)
defer out.Flush()
t := int(in.NextInt64())
perms := [][3]int{
{0, 1, 2},
{0, 2, 1},
{1, 0, 2},
{1, 2, 0},
{2, 0, 1},
{2, 1, 0},
}
for ; t > 0; t-- {
n := int(in.NextInt64())
caps := [3]int{
int(in.NextInt64()),
int(in.NextInt64()),
int(in.NextInt64()),
}
vals := make([]int64, n)
var total int64
for i := 0; i < n; i++ {
vals[i] = in.NextInt64()
total += vals[i]
}
sort.Slice(vals, func(i, j int) bool { return vals[i] < vals[j] })
desc := make([]int64, n)
for i := 0; i < n; i++ {
desc[i] = vals[n-1-i]
}
found := false
var answer Candidate
bestInvalid := make([]Candidate, 0, 5)
tryCandidate := func(c Candidate) bool {
if isValidCandidate(c, caps, total) {
answer = c
return true
}
addBest(&bestInvalid, c, caps, total, 5)
return false
}
for _, perm := range perms {
for tieMode := 0; tieMode < 3; tieMode++ {
if tryCandidate(simulateGreedy(desc, caps, perm, tieMode)) {
found = true
break
}
}
if found {
break
}
for mode := 0; mode < 2; mode++ {
if tryCandidate(simulateTwoEnded(vals, caps, perm, mode)) {
found = true
break
}
}
if found {
break
}
if tryCandidate(simulateCanonical(vals, caps, perm)) {
found = true
break
}
}
if !found {
for _, cand := range bestInvalid {
cc := deepCopyCandidate(cand)
if repairCandidate(&cc, total, caps) {
answer = cc
found = true
break
}
}
}
if !found {
out.WriteString("NO\n")
continue
}
out.WriteString("YES\n")
writeSlice(out, answer.groups[0])
writeSlice(out, answer.groups[1])
writeSlice(out, answer.groups[2])
}
}