MofK muốn nâng cấp cái TV cà tàng của mình bằng cách đem TV đến các tiệm nâng cấp xuyên suốt thành phố anh ấy sống. Thành phố có dạng lưới, với ~n~ con đường chạy ngang và ~m~ con đường chạy dọc. Khi nhìn trên bản đồ, các con đường ngang được đánh số từ ~1~ đến ~n~ từ trên xuống, và các con đường dọc được đánh số từ ~1~ đến ~m~ từ trái qua phải. Giao của đường ngang thứ ~r~ và đường dọc thứ ~c~ được kí hiệu là ~(r, c)~.

MofK xuất phát tại vị trí ~(1, 1)~. MofK sẽ di chuyển trên các con đường, với mục tiêu là đến được Điện Máy Vàng tại vị trí ~(n, m)~. Để đến được Điện Máy Vàng nhanh nhất có thể, tại mỗi bước, từ vị trí ~(r, c)~, MofK sẽ di chuyển đến ô ~(r + 1, c)~ hoặc ~(r, c + 1)~. MofK sẽ không di chuyển ra ngoài thành phố.

May thay, ở mỗi giao lộ đều có một tiệm nâng cấp TV. Khi MofK tiến đến một tiệm nâng cấp (bao gồm cả tiệm nâng cấp tại vị trí xuất phát và Điện Máy Vàng ở vị trí đích), MofK liền mua nâng cấp TV ở tiệm đấy ngay lập tức. Tất nhiên, điều này cũng có nghĩa là chiếc TV sẽ thay đổi kích thước:

• Trước khi xuất phát, TV có chiều cao là ~h~ và chiều rộng là ~w~.

• Khi được nâng cấp ở tiệm đặt tại giao lộ ~(i, j)~:

  • Chiều cao của TV tăng thêm ~a_i~;

  • Chiều rộng của TV tăng thêm ~b_j~.
    
    Trong đó ~a_1, a_2, \ldots, a_n~ và ~b_1, b_2, \ldots, b_m~ là hai dãy số nguyên dương.

MofK muốn kích thước đường chéo TV của mình càng lớn càng tốt. Nói cách khác, trong số tất cả các đường đi hợp lệ để đi từ vị trí ~(1, 1)~ đến ~(n, m)~, hãy giúp MofK tìm ra đường đi mà khi đến Điện Máy Vàng, giá trị ~h^2 + w^2~ (với ~h~ là chiều cao và ~w~ là chiều rộng của TV) là lớn nhất có thể. In ra ~h^2 + w^2~ tại Điện Máy Vàng sau khi MofK thực hiện đi trên con đường đó.

Input

Dòng đầu tiên chứa số nguyên ~t~ (~1 \le t \le 100~) — số lượng test case. Mô tả của mỗi test case như sau.

Dòng đầu tiên chứa bốn số nguyên ~n~, ~m~, ~h~, ~w~ (~1 \le n, m \le 1000~, ~0 \le h, w \le 10^6~) — số lượng con đường ngang, số lượng con đường dọc, chiều cao ban đầu và chiều rộng ban đầu của chiếc TV của MofK.

Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~0 \le a_i \le 10^6~) — với ~a_i~ là chiều cao mà TV sẽ tăng lên khi nâng cấp ở bất kỳ tiệm nào trên con đường ngang thứ ~i~.

Dòng thứ ba chứa ~m~ số nguyên ~b_1, b_2, \ldots, b_m~ (~0 \le b_j \le 10^6~) — với ~b_j~ là chiều rộng mà TV sẽ tăng lên khi nâng cấp ở bất kỳ tiệm nào trên con đường dọc thứ ~j~.

Đảm bảo rằng:

• tổng ~n~ qua các test case không quá ~1000~;

• tổng ~m~ qua các test case không quá ~1000~;

Output

Với mỗi test case, in ra một số nguyên duy nhất là giá trị ~h^2 + w^2~ lớn nhất có thể của MofK khi di chuyển từ vị trí ~(1, 1)~ đến ~(n, m)~ trong số các đường đi hợp lệ.

Scoring

Sample Input 1

4
1 3 1 1
2
1 2 3
2 2 10 20
10 20
30 40
2 3 3 1
4 1
5 9 2
10 6 11 9
7 30 49 49 48 10 45 41 37 12
31 34 7 38 19 39

Sample Output 1

98
19400
845
603200

Notes

• Ở test case đầu tiên, MofK có một cách đi duy nhất:

  • Ban đầu, MofK đứng ở ~(1, 1)~. Chiều cao tăng lên ~h = 1 + 2 = 3~, chiều rộng tăng lên ~w = 1 + 1 = 2~.

  • MofK đi đến ô ~(1, 2)~. Chiều cao tăng lên ~h = 3 + 2 = 5~, chiều rộng tăng lên ~w = 2 + 2 = 4~.

  • MofK đi đến ô ~(1, 3)~. Chiều cao tăng lên ~h = 5 + 2 = 7~, chiều rộng tăng lên ~w = 4 + 3 = 7~.

  Cuối cùng, ~h^2 + w^2 = 7^2 + 7^2 = 98~.

• Ở test case thứ hai, cách đi tối ưu của MofK là:

  • Ban đầu, MofK đứng ở ~(1, 1)~. Chiều cao tăng lên ~h = 10 + 10 = 20~, chiều rộng tăng lên ~w = 20 + 30 = 50~.

  • MofK đi đến ô ~(2, 1)~. Chiều cao tăng lên ~h = 20 + 10 = 30~, chiều rộng tăng lên ~w = 50 + 40 = 90~.

  • MofK đi đến ô ~(2, 2)~. Chiều cao tăng lên ~h = 30 + 20 = 50~, chiều rộng tăng lên ~w = 90 + 40 = 130~.

  Cuối cùng, ~h^2 + w^2 = 50^2 + 130^2 = 19400~.