問題文

ヤチヨ、かぐや、いろはの $3$ 人がライブを行います。

ライブで歌う候補となる $N$ 曲には、あらかじめ「どのユニットで歌うか」が指定されています。

$i (1 \leq i \leq N)$ 番目の曲は、以下の $6$ 種類のいずれかです。

• $t_i = 1$：ソロ曲（ヤチヨ） ヤチヨの体力を $1$ 消費する。
• $t_i = 2$：ソロ曲（かぐや） かぐやの体力を $1$ 消費する。
• $t_i = 3$：ソロ曲（いろは） いろはの体力を $1$ 消費する。
• $t_i = 4$：デュエット曲（ヤチヨ＆かぐや） ヤチヨとかぐやの体力をそれぞれ $1$ 消費する。
• $t_i = 5$：デュエット曲（ヤチヨ＆いろは） ヤチヨといろはの体力をそれぞれ $1$ 消費する。
• $t_i = 6$：デュエット曲（かぐや＆いろは） かぐやといろはの体力をそれぞれ $1$ 消費する。

また、$i$ 番目の曲を選ぶと、観客は満足度 $v_i$ を得ます。

ヤチヨ、かぐや、いろはの体力はそれぞれ $Y, K, I$ です。

同じ曲を $2$ 回以上選ぶことや、各人物の消費体力の合計がそれぞれ $Y, K, I$ を超えるような選び方はできません。

条件を満たすように選べる曲数の最大値を $C$ とします。

各整数 $c\ (1 \leq c \leq C)$ について、合計 $c$ 曲を選ぶ場合の観客の満足度の合計の最大値 $X_c$ を求めてください。

$T$ 個のテストケースが与えられるので、それぞれについて解いてください。

制約

• $1 \leq T \leq 10^5$
• $1 \leq N \leq 3 \times 10^5$
• $0 \leq Y, K, I \leq N$
• $1 \leq t_i \leq 6$
• $|v_i| \leq 10^9$
• 全てのテストケースにおける $N$ の総和は $3 \times 10^5$ 以下
• 入力はすべて整数

入力

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$:$
$\mathrm{case}_T$

ここで、$\mathrm{case}_i$ は $i$ 番目のテストケースであり、以下の形式で与えられる。

$N$ $Y$ $K$ $I$
$t_1$ $v_1$
$t_2$ $v_2$
$:$
$t_N$ $v_N$

出力

$T$ 行出力せよ。$i$ 行目には $\mathrm{case}_i$ の答えを以下の形式で出力せよ。

$C$ $X_1$ $X_2$ $\cdots$ $X_C$

$C=0$ の場合は $0$ のみを出力せよ。

サンプル

1
6 1 1 1
1 5
2 4
3 3
4 10
5 9
6 8

3 10 13 12

2
5 2 1 1
1 8
1 8
4 10
5 10
6 9
6 0 2 2
1 100
2 -2
2 -3
3 -4
3 -5
5 -1

3 10 20 25
4 -2 -5 -9 -14

2
3 3 3 0
3 1
5 2
6 3
3 1 1 1
4 0
5 0
6 0

0
1 0