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)$. Mỗi cặp nhiếp ảnh gia - bò tạo ra một đường ngắm 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. Nếu Bessie xuất phát tại thời điểm $t$, cô tránh tất cả đường ngắm có $s_i\le 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 X,Y\le {10}^6$
• $1\le N\le 3·{10}^5$
• $1\le T\le N+1$

Ví dụ