Có ~n + m + 1~ ứng cử viên xin việc tại một công ty. Ứng cử viên thứ ~i~ có kỹ năng code là ~a_i~ và kỹ năng test là ~b_i~. Bạn cần chọn ra ~n~ coder và ~m~ tester sao cho tổng hiệu suất của cả công ty là lớn nhất. Mỗi ứng viên sẽ đóng góp vào hiệu suất tổng là ~a_i~ nếu như được chọn làm coder, ~b_i~ nếu được chọn làm tester, và ~0~ nếu họ không được chọn vào công ty. Để thấy được tương quan giữa tất cả các khả năng chọn, bạn cần in ra tổng hiệu suất lớn nhất khi ứng cử viên thứ ~i~ bị loại.

Input

Dòng đầu tiên chứa số nguyên dương ~t~ thể hiện số test (~1 \le t \le 5 \cdot 10^5~).

~t~ nhóm dòng sau có dạng:

• Dòng đầu tiên chứa hai số nguyên không âm ~n~ và ~m~ thể hiện số coder và tester cần tuyển (~0 \le n,m \le 5 \cdot 10^5~; ~2 \le n + m + 1 \le 5 \cdot 10^5~);

• Dòng tiếp theo chứa ~n + m + 1~ số nguyên dương ~a_1,a_2,...,a_{n + m + 1}~(~1 \le a_i \le 10^9~), với ~a_i~ là hiệu suất của người thứ ~i~ nếu được chọn làm coder.

• Dòng cuối cùng chứa ~n + m + 1~ số nguyên dương ~b_1,b_2,...,b_{n+m+1}~ (~1 \le b_i \le 10^9~), với ~b_i~ là hiệu suất của người thứ ~i~ nếu được chọn làm tester.

Dữ liệu vào đảm bảo tổng các (~n + m + 1~) trong tất cả các test không vượt quá ~5 \cdot 10^5~.

Output

Với mỗi test case: ghi ra ~n + m + 1~ số nguyên trên một dòng, trong đó số nguyên thứ ~i~ là hiệu suất tối đa của công ty nếu người thứ ~i~ không được chọn vào công ty.

Scoring

Đặt ~N~ = ~\sum n + m + 1~ trong tất cả các testcases.

Sample Input 1

1
1 1
3 2 3
1 2 3

Sample Output 1

5 6 5

Sample Input 2

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

Sample Output 2

1 2 
5 6 9 
9 12 11 12 
13 13 14 13 16

Notes

Giải thích bộ test ví dụ đầu tiên:

Nếu người thứ ~1~ nghỉ, ta có thể cho người thứ ~2~ làm tester, người còn lại làm coder. Khi đó tổng hiệu suất là ~2 + 3 = 5~

Nếu người thứ ~2~ nghỉ, ta có thể cho người thứ ~3~ làm tester, người còn lại làm coder. Khi đó tổng hiệu suất là ~3 + 3 = 6~

Nếu người thứ ~3~ nghỉ, ta có thể cho người thứ ~2~ làm tester, người còn lại làm coder. Khi đó tổng hiệu suất là ~2 + 3 = 5~