Hệ trục tọa độ ~Oxy~ chia mặt phẳng thành bốn phần: góc trên bên phải là góc phần tư thứ ~I~, cứ thế đi ngược chiều kim đồng hồ, ta sẽ có góc phần tư thứ ~II, III, IV~. Lần lượt cho vào các góc phần tư đó các điểm phân biệt (không nằm trên hai trục tọa độ) với số lượng là ~a,b,c,d~. Hãy tính xem có thể có nhiều nhất bao nhiêu tam giác với ba đỉnh (mỗi đỉnh ở 1 phần tư khác nhau) lấy từ các điểm đã cho và chứa gốc tọa độ ~O~ bên trong?

Input

Các số nguyên dương ~a,b,c,d~ không vượt quá ~10^6.~

Output

Một số nguyên duy nhất là đáp số của bài toán (cho biết rằng giá trị này vẫn tính được trong kiểu Int64).

Sample input

1 1 1 1

Sample output

2

Trong dải ngân hà có hai ngôi sao chuyển động theo quỹ đạo vòng tròn và nằm trên cùng mặt phẳng. Cho biết tọa độ tâm và bán kính của hai quỹ đạo (hai quỹ đạo không trùng nhau), hỏi khoảng cách gần nhất và xa nhất của hai ngôi sao có thể có là bao nhiêu?

Input

Gồm hai dòng cho biết tọa độ tâm ~(x_i,y_i)~ và bán kính ~R_i~ của sao ~i~ với ~i = 1,2~. Các giá trị có trị tuyệt đối không quá ~10^4.~

Output

In ra khoảng cách gần nhất và xa nhất, làm tròn đến ~2~ chữ số thập phân.

Sample input

0 0 1
0 0 2

Sample output

1.00 3.00

Giải thích: các bạn có thể vẽ hình ra cho dễ hình dung.

Trải qua những cuộc thi ICPC, và cả những cuộc tình dang dở, lúc về già, coder Luna đã để dành được một kho châu báu quý giá của cả cuộc đời mình. Cụ ấy đã cẩn thận chôn nó vào cái hộp tròn bán kính ~1~ ở một khu rừng hoang vắng. Tuy nhiên, một ngày nọ, các nhà thám hiểm từ CLB H3.2 đã lần mò ra dấu vết kho báu này, vì họ nghe tương truyền rằng trong kho báu đó, có chứa nhiều bí kíp thượng thừa, code đâu AC đó, rõ ràng là một loại vũ khí cực mạnh. Mỗi nhà thám hiểm sẽ có một máy định vị, chấm ra ba điểm trong bề mặt khu rừng và nối lại thành tam giác. Nếu cái hộp và miền mặt phẳng chứa tam giác có điểm chung nào đó (kể cả trường hợp cạnh của tam giác chạm vào cái hộp) thì máy sẽ phát ra tiếng Bíp bíp bíp. Hãy giúp coder già Luna xem những kẻ tò mò có tìm được kho châu báu này không nhé?

Input

Dòng đầu tiên chứa số ~t~ với ~1 \le t \le 3~ cho biết số nhà thám hiểm. Ba dòng tiếp theo, mỗi dòng chứa ~6~ số nguyên là tọa độ các điểm mà máy dò tìm chấm lên. Cho biết rằng chúng không thẳng hàng và giá trị tuyệt đối không vượt quá ~100.~ Chú ý rằng tâm của cái hộp hình tròn trùng với gốc tọa độ.

Output

Ứng với mỗi nhà thám hiểm, in ra YES / NO ứng với việc họ có tìm được châu báu hay không?

Sample input 1

2
1 1 -1 2 3 2
1 0 2 0 1 -1

Sample output 1

NO
YES

Sample input 2

2
-2 -1 -2 2 1 -2
0 0 1 1 3 1

Sample output 2

YES
YES

Giải thích: tham khảo thêm các hình vẽ minh họa.

Bạn Tài trong CLB H3.2 học rất giỏi nhưng cũng rất introvert. Trong một dịp CLB H3.2 đi du lịch đảo Cần Giờ, sau nhiều ngày được năn nỉ thì cuối cùng bạn ấy cũng chịu tham gia cùng team. Khu du lịch là một vùng đất rộng lớn và nắng gắt có dạng lưới ô vuông, mỗi điểm trong lưới được gán tọa độ ~(x,y)~. Team sẽ dừng chân tại hai địa điểm có tọa độ nguyên ~A~ và ~B~ đã đặt lịch từ trước. Team muốn chọn thêm một điểm ~C~ (cũng có tọa độ nguyên nhưng không thuộc đường thẳng ~AB~) để đi dạo vòng quanh giữa 3 điểm ~A,B,C~ này. Tài bị buộc phải đi dạo cùng team nhưng vì không muốn đi nhiều nên bạn đề xuất với team điểm ~C~ mà diện tích tam giác ~ABC~ đó càng nhỏ càng tốt. Hãy giúp Tài introvert xác định diện tích đó nhé.

Input

Một dòng duy nhất là tọa độ hai điểm phân biệt ~x_A, \, y_A, \, x_B, \, y_B~ là các số tự nhiên không vượt quá ~10^9.~

Output

Diện tích tam giác cần tìm, nếu là số thập phân thì làm tròn đến 1 chữ số sau dấu phẩy.

Sample Input 1.

0 1 1 0

Sample Output 1.

0.5

Sample Input 2.

5 6 23 22

Sample Output 2.

1

Giải thích: Trong VD1, Tài có thể chọn điểm ~C(0,0)~ thì diện tích tam giác ~ABC~ lúc bấy giờ là ~1/2~, là nhỏ nhất có thể. Trong VD2, Tài có nhiều cách chọn điểm ~C~ để ra được diện tích bằng ~1~, chẳng hạn như ~C(4,5),C(6,7),C(13,13),...~

C và Q đã đi qua những ngày giông bão và những cánh đồng hoa tulip thơ mộng, ... trải qua biết bao nhiêu thử thách cùng nhau. Nhưng hôm nay, trong một chuyến dạo chơi trên biển, bất ngờ hai bạn gặp phải một thử thách tồi tệ hơn: lạc trôi vào tam giác quỷ Bermuda. Đây là địa điểm nổi tiếng là có thể cuốn phăng mọi thứ đi qua nó mà không để lại dấu vết, và câu chuyện của Q và C cũng có nguy cơ chịu chung số phận.

May mắn thay, vị thiên sứ tình yêu lại một lần nữa xuất hiện. Giữa vòng vây của tam giác quỷ, thiên sứ mách bảo họ là hãy đi đến vị trí trong tam giác mà tổng bình phương khoảng cách từ điểm đó đến ba cạnh tam giác quỷ là nhỏ nhất, vị trí đó chính là nơi có thể giải thoát cho họ, đưa họ đến nơi có những cánh đồng hoa hướng dương trong mơ ước.

Trong thời gian gấp rút, C đã dùng máy định vị của con tàu để tìm ra được tọa độ của ba đỉnh tam giác quỷ, hãy giúp đôi bạn trẻ tìm ra tọa độ của vị trí kia nhanh nhất có thể nhé (vì muốn chính xác nên tất cả thông tin đều là số nguyên). Đôi khi máy định vị của C bị sai, lại ra tọa độ ba đỉnh thẳng hàng, lúc đó ta không cần tìm nữa và kết cục đã được định đoạt.

Input

Tọa độ ba điểm ~A,B,C~ là ba đỉnh của tam giác quỷ dưới dạng ~(x,y)~, trong đó ~x,y~ là các số nguyên thỏa mãn ~-10^5 \le x,y \le 10^5.~ Các điểm này phân biệt nhau.

Output

Nếu ~A,B,C~ thẳng hàng thì in ra ~-1~, còn nếu không thì in ra tọa độ điểm cần tìm là điểm ~D~ ở dạng phân số tối giản: dòng đầu là hoành độ, dòng sau là tung độ, tử và mẫu số cách nhau bởi dấu /, ngoài ra quy ước mẫu số luôn là số nguyên dương. Nếu tọa độ của điểm là nguyên thì vẫn in dạng phân số với mẫu là ~1.~

Sample input 1:

0 0 0 1 1 1

Sample output 1:

1/4
3/4

Sample input 2:

13 8 2 0 2 3

Sample output 2:

779/340
627/340

Sample input 3:

0 0 1 1 2 2

Sample output 3:

-1

Giải thích; trong VD1, ta có ba tọa độ là ~A(0,0),B(0,1), C(1,1)~ và bằng các tính toán thích hợp, ta tìm được tọa độ điểm ~D~ như trên; tương tự với VD2. Còn ở VD3 thì ba điểm thẳng hàng nên in ra ~-1.~

Mong rằng mọi thứ chỉ là một giấc mơ trưa, mong bình yên sẽ lại quay về bên ngọn đồi đón gió.

Em Phú phá phách vừa mới lớn nên đã bắt đầu tập tành xếp hình. Đây là một trò chơi giải trí lành mạnh rất kích thích phát triển tư duy. Em đã bắt đầu với các quân domino (gồm ~2~ ô vuông ghép lại), rồi tromino (gồm ~3~ ô vuông ghép lại). Hôm nay, em bắt đầu chơi với level cao hơn là tetromino gồm ~4~ ô vuông ghép lại. Chị gái mua cho em nhiều mảnh ghép có dạng tetromino (mỗi mảnh có số lượng tùy ý). Em Phú bèn lấy áo dài của chị để cắt ra thành một hình chữ nhật ~2 \times n~ để xếp lên đó cho dễ. Em đang thắc mắc là có bao nhiêu cách xếp khác nhau với các quân tetromino này để có thể phủ kín được mảnh áo dài của chị mình? Hai cách lát được xem là khác nhau nếu dùng các loại tetromino khác nhau hoặc thứ tự sắp xếp của chúng là khác nhau.

Input:

Một dòng duy nhất gồm số nguyên dương ~n~ với ~1 \le n \le 10^{18}~.

Output:

Đáp số của bài toán. Vì đáp số có thể rất lớn nên lấy modulo ~10^9+7~.

Sample input 1:

1

Sample output 1:

0

Sample input 2:

2

Sample output 2:

1

Sample input 3:

2022

Sample output 3:

12973685

Giải thích: ta thấy với ~n=1~ thì nền nhà chỉ có ~2~ ô gạch, không thể lát được, còn với ~n=2~, ta thấy nền nhà có kích thước ~2 \times 2~ nên có một cách duy nhất là dùng hình vuông.