Cho 4 điểm \(A(x_A, y_A)\), \(B(x_B, y_B)\), \(C(x_C, y_C)\), \(D(x_D, y_D)\) trên hệ trục tọa độ Descartes.
Đường thẳng \((d)\) đi qua hai điểm \(A\) và \(B\). Đường thẳng \((d')\) đi qua hai điểm \(C\) và \(D\).
Gọi \(K(x_K, y_K)\) là giao điểm của hai đường thẳng \((d)\) và \((d')\).

Input

• Dòng đầu tiên nhập vào một số nguyên dương \(t\) (\(t \leq 10^5\)) - số lượng truy vấn.
• \(t\) dòng tiếp theo, mỗi dòng nhập vào tám số nguyên \(x_A, y_A, x_B, y_B, x_C, y_C, x_D, y_D\) (\(0 \leq |x_A|, |y_A|, |x_B|, |y_B|, |x_C|, |y_C|, |x_D|, |y_D| \leq 10^9\)) - toạ độ các điểm \(A, B, C, D\).

Output

• Với mỗi truy vấn, hãy in ra hai số \(x_K, y_K\) là toạ độ điểm \(K\) nếu hai đường thẳng có duy nhất \(1\) điểm chung. Nếu hai đường thẳng \((d)\) và \((d')\) có vô số điểm chung, in ra \(1000000000000000000\) (\(10^{18}\)). Còn nếu chúng không có điểm chung, in ra \(-1\).

Trong trường hợp hai đường thẳng \((d)\) và \((d')\) có duy nhất \(1\) điểm chung, kết quả của bạn sẽ được chấp nhận nếu sai số không vượt quá \(10^{-6}\).
Dữ liệu luôn đảm bảo \(|x_K|, |y_K| < 2^{63}\).

Example

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

-1
1000000000000000000
2.2 1.4
3.4 1.8