Ở thành phố nọ có một nhà hàng nổi tiếng. Nhà hàng này có một thực đơn đa dạng với ~n~ món khai vị, ~n~ món chính và ~n~ món tráng miệng. Quang yêu thích một số món của nhà hàng, nhưng cũng có một số món cậu ta không thích. Với mỗi món, cậu xác định chỉ số độ ngon của nó. Món cậu càng yêu thích thì chỉ số càng lớn, ngược lại món cậu càng ghét thì chỉ số càng thấp. Lưu ý rằng độ ngon có thể âm. Khi ăn một món, độ hạnh phúc của cậu tăng lên đúng bằng độ ngon của món đó.

Do công việc bận rộn, Quang muốn đặt đồ ăn về nhà thông qua ứng dụng gọi món. Không may, ứng dụng gặp lỗi: nếu Quang chọn hai món cùng giá, đơn hàng sẽ bị xóa và phải chọn lại các món từ đầu. Vì cũng đã muộn nên để không mất thời gian lướt lên và xuống, Quang sẽ chọn món theo thứ tự xuất hiện: ~x~ món khai vị đầu tiên, ~y~ món chính đầu tiên và ~z~ món tráng miệng đầu tiên để đặt.

Yêu cầu: Hãy giúp Quang tính các giá trị ~x, y, z~ sao cho app không bị lỗi để có độ hạnh phúc lớn nhất sau khi ăn tất cả các món mình đặt. Giả sử rằng Quang luôn có đủ tiền để thanh toán bất cứ đơn đồ ăn nào từ app. Biết rằng độ hạnh phúc ban đầu của Quang bằng ~0~ , và cậu có thể không đặt món khai vị, món chính hay món tráng miệng, thậm chí là không đặt bất kỳ món nào.

Dữ liệu:

Dòng thứ nhất chứa một số nguyên dương ~t~ là số bộ test. Bảy dòng tiếp theo mô tả bộ test đầu tiên với cấu trúc như sau:

• Dòng thứ nhất chứa một số nguyên dương ~n~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_{1}, a_{2}, \ldots, a_{n}~ lần lượt là giá của ~n~ món khai vị.
• Dòng thứ ba chứa ~n~ số nguyên dương ~w a_{1}, w a_{2}, \ldots, w a_{n}~ lần lượt là độ ngon của ~n~ món khai vị.
• Dòng thứ bốn chứa ~n~ số nguyên dương ~b_{1}, b_{2}, \ldots, b_{n}~ lần lượt là giá của ~n~ món chính.
• Dòng thứ năm chứa ~n~ số nguyên dương ~w b_{1}, w b_{2}, \ldots, w b_{n}~ lần lượt là độ ngon của ~n~ món chính.
• Dòng thứ sáu chứa ~n~ số nguyên dương ~c_{1}, c_{2}, \ldots, c_{n}~ lần lượt là giá của ~n~ món tráng miệng.
• Dòng thứ bảy chứa ~n~ số nguyên dương ~w c_{1}, w c_{2}, \ldots, w c_{n}~ lần lượt là độ ngon của ~n~ món tráng miệng.

Mỗi dòng trong số ~t-1~ dòng còn lại chứa hai số nguyên ~e, s~. Bộ test tiếp theo được tạo ra từ bộ test đầu tiên bằng cách giữ nguyên ~n, a, b, c~. Với mỗi phần tử ~w~ trong ~[w a, w b, w c]~ gán ~w:=\left(\left(\left(\left(t+2^{20}\right)\right.\right.\right.~ XOR ~\left.e\right)+~ s) MOD ~\left.2^{21}\right)-2^{20}~.

Kết quả:

• Ghi ra ~t~ dòng, mỗi dòng một số nguyên là độ hạnh phúc lớn nhất tìm được tương ứng với mỗi bộ test.

Ràng buộc:

Trong tất cả các test: ~1 \leq t \leq 50,1 \leq n \leq 2 \times 10^{5} ; 1 \leq a_{i}, b_{i}, c_{i} \leq 10^{6} ;-2^{20} \leq w a_{i}, w b_{i}, w c_{i}<2^{20}~; ~0 \leq e, s<2^{21}~.

• Subtask ~1~: ~20 \% t=1, n \leq 30~.
• Subtask ~2~: ~20 \% t=1, n \leq 400~.
• Subtask ~3~: ~15 \% t=1, n \leq 5000~.
• Subtask ~4~: ~15 \% t=1, n \leq 2 \cdot 10^{5}, w a_{i}=w b_{i}=w c_{i}=1~ với mọi ~1 \leq i \leq n~.
• Subtask ~5~: ~15 \% t=1, n \leq 2 \cdot 10^{5}~.
• Subtask ~6~: ~15 \%~ không có ràng buộc gì thêm.

Ví dụ:

Sample Input 1

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

Sample Output 1

9

Sample Input 2

2
8
50 45 40 35 30 25 20 15
5 2 -3 8 -1 4 6 -2
48 42 38 32 28 22 18 15
3 6 -2 1 -5 2 4 -3
35 40 45 30 25 20 55 60
1 -3 5 -2 4 6 -1 3
10 5

Sample Output 2

30
151

Lưu ý:

Ở ví dụ thứ nhất, cách tối ưu là chọn ~4~ món khai vị, ~3~ món chính và ~2~ món tráng miệng.

Ở ví dụ thứ hai, cách chọn tối ưu cho bộ test thứ nhất là: ~7~ món khai vị, ~2~ món chính và 0 món tráng miệng. Các dãy ~w a, w b, w c~ cho bộ test thứ hai là: ~w a=\{20,13,-4,7,-6,19,17,-7\}, w b=~ ~\{14,17,-7,16,-10,13,19,-4\}, w c=\{16,-4,20,-7,19,17,-6,14\}~. Phương án tối ưu là chọn ~1~ món khai vị, ~7~ món chính và ~8~ món tráng miệng.