Ông An đang đi mua đất để dành cho việc chăn nuôi gia súc. Sau một thời gian khảo sát tìm kiếm thì ông đã chọn được 2 mảnh cỏ hình chữ nhật xanh tưới lần lượt là \(A\) có góc trái trên là \((Ax_1, Ay_1)\) và góc phải dưới là \((Ax_2, Ay_2)\); \(B\) có góc trái trên là \((Bx_1, By_1)\) và góc phải dưới là \((Bx_2, By_2)\). Tuy nhiên, vì muốn nông trại của mình thật hoàn hảo nên ông quyết định sẽ chỉ mua đúng 1 mảnh đất hình vuông bao phủ cả 2 mảnh đất trên. Các bạn hãy giúp ông tìm mảnh đất nhỏ nhất thỏa mãn nhé!

Input

• Dòng đầu tiên chứa 4 số \(Ax_1, Ay_1, Ax_2, Ay_2\) \((1 \le Ax_1, Ay_1, Ax_2, Ay_2 \le 10^9)\).
• Dòng thứ hai chứa 4 số \(Bx_1, By_1, Bx_2, By_2\) \((1 \le Bx_1, By_1, Bx_2, By_2 \le 10^9)\).

Output

• Một dòng duy nhất là diện tích của mảnh đất hình vuông nhỏ nhất bao phủ cả hai mảnh đất \(A\) và \(B\).

Example

1 1 2 3
2 2 4 4

9

Đếm số lượng số đối xứng lẻ

Phân bổ test:

• 25% test tương ứng 25% số điểm khoảng cách từ L đến R <=100000 số.
• 25% test tương ứng 25% số điểm với R<=10^10.
• 25% test tương ứng 25% số điểm với R<=10^12.
• 25% test tương ứng 25% số điểm với R<=10^14.

Cho hai số nguyên \(n\) và \(k\). Hãy tìm số lượng số được tách từ \(n\) sao cho các số được tách từ \(n\) chia hết cho \(k\) và số lượng số tách được là lớn nhất(các số khi tách phải liên tiếp với nhau).
Ví dụ \(n=12345\) và \(k = 3\) có những cách tách là \(\{12;3;45\}\) hoặc \(\{12;345\}\) trong khi cách tách số không thỏa mãn là \(\{1245;3\}\).
Yêu cầu: In ra số lượng số lớn nhất tìm được.

12345
3

3

433
2

0

2222
2

4

Cho số nguyên dương \(n\) \((n \le 10^{18})\). Tính tổng \(1 - 2 + 3 - 4 + 5 - 6 + \cdots \pm n\).

Input

• Một dòng gồm số nguyên dương \(n\).

Output

• Một dòng là kết quả của bài toán.

Scoring

• Có \(50\%\) số điểm ứng với \(n \le 10^6\).
• Có \(50\%\) số điểm còn lại ứng với \(n \le 10^{18}\).

Example

5

3

6

-3

Một bộ đèn pha lê đẹp mắt đang được bày bán trên TikTok. Anh N (chủ nhân của giải thưởng 40 triệu đồng) đang dự tính mua nó để trang trí cho nhà hàng của mình.

Bộ đèn gồm \(a\) bóng đèn màu xanh và \(b\) bóng đèn màu đỏ. Giá của mỗi bóng đèn màu xanh là \(x\) và mỗi bóng đèn màu đỏ là \(y\). Để đổi một bóng đèn bất kì từ xanh sang đỏ hoặc ngược lại thì anh ta phải trả thêm \(c\) đồng cho chủ shop. N được dùng thao tác đổi bóng đèn vô số lần, hãy giúp anh ta tìm chi phí tối thiểu để mua được bộ đèn đó.

Input

• Dòng đầu tiên chứa số nguyên dương \(T\) là số bộ dữ liệu
• Tiếp theo gồm \(T\) dòng, tương ứng với \(T\) bộ dữ liệu. Mỗi dòng chứa các số nguyên dương \(a, b, x, y, c\).

Output

• Gồm một số nguyên duy nhất là số tiền tối thiểu cần để mua bộ đèn.

Scoring

• \(T \le 100\) với mọi testcase.
• Gọi \(n = a + b\):
  • Subtask \(1\) (\(50\%\) số điểm): \(n, x, y, c \le 10^3\).
  • Subtask \(2\) (\(50\%\) số điểm): \(n, x, y, c \le 10^5\).

Example

3
2 1 1 1 1
3 2 10 100 1
0 5 10 1 1

3
52
5