Cơ Hội Chụp Ảnh

Bessie bắt đầu tại vị trí $(X,0)$ và cần đi đến $(0,Y)$. Có $N$ con bò trên trục $X$ tại tọa độ $(x_i,0)$, mỗi con có một nhiếp ảnh gia tại $(0,y_i)$. Cặp bò - nhiếp ảnh gia thứ $i$ tạo ra một đường ngắm, chính là đoạn thẳng nối $(x_i,0)$ với $(0,y_i)$, và đường ngắm này bắt đầu bị chặn từ thời điểm $s_i$.

Bessie sẽ đi đường ngắn nhất (khoảng cách Euclid) đến đích mà không cắt qua bất kỳ đường ngắm nào đang hoạt động. Bessie được phép chạm vào hoặc đi dọc theo một đường ngắm, chỉ không được cắt ngang qua nó. Nếu Bessie xuất phát tại thời điểm $t$, cô phải tránh tất cả đường ngắm có $s_i\le t$.

Gọi $d_t$ là độ dài đường đi ngắn nhất khi xuất phát tại thời điểm $t$. Hãy tính $\lfloor d_t\rfloor$ cho mỗi $t$ từ $0$ đến $T-1$.

Dữ liệu vào

• Dòng 1: Hai số $N$ và $T$
• Dòng 2: Hai số $X$ và $Y$
• $N$ dòng tiếp: Ba số $s_i$, $x_i$, $y_i$ cho mỗi con bò

Dữ liệu ra

• $T$ dòng, dòng thứ $t$ chứa $\lfloor d_t\rfloor$.

Ràng buộc

• $1\le N\le 3·{10}^5$
• $1\le T\le N+1$
• $1\le X,Y\le {10}^6$
• $1\le x_i,y_i\le {10}^6$
• $1\le s_i\le T-1$

Ví dụ