Luyện Bắn II

Nong dan John huan luyen ban cung cho $4N$ con bo. Co $N$ bia hinh chu nhat can ban. Moi bia co 4 dinh, va moi con bo duoc gan voi mot dinh khac nhau.

Moi con bo dung tren truc $y$ (tai $x=0$) va ban theo duong thang voi do doc $s_i$. Moi mui ten di theo duong $y=s_i·x+b$ (voi $b$ la vi tri cua bo tren truc $y$). Mot phat ban that bai neu mui ten di qua phan ben trong cua bia truoc khi den dinh duoc gan.

Tat ca cac bia co canh trai tai $x=X_1$. Bia thu $i$ co goc duoi trai $(X_1,y_1^{(i)})$ va goc tren phai $(x_2^{(i)},y_2^{(i)})$.

Hay tim cach gan bo vao cac dinh va dat vi tri cac bo tren truc $y$ sao cho khoang cach giua hai bo xa nhat la nho nhat. In gia tri khoang cach nho nhat do, hoac $-1$ neu khong the thuc hien.

Du lieu vao

• Dong 1: So nguyen $T$ ($1\le T\le 10$) -- so test case.
• Voi moi test case:
  • Dong 1: Hai so nguyen $N$ va $X_1$.
  • $N$ dong tiep theo: Ba so nguyen $y_1^{(i)}$, $y_2^{(i)}$, $x_2^{(i)}$.
  • Dong cuoi: $4N$ so nguyen la cac do doc $s_1,s_2,\dots ,s_{4N}$.

Du lieu ra

Voi moi test case, in khoang cach nho nhat hoac $-1$.

Rang buoc

• $1\le N\le 4\times {10}^4$
• Tong $N$ qua cac test case $\le 4\times {10}^4$
• $1\le X_1<x_2^{(i)}\le {10}^9$
• $1\le y_1^{(i)}<y_2^{(i)}\le {10}^9$
• $0<|s_i|<{10}^9$

Vi du