Trang trại của Farmer John tràn đầy thảm thực vật xanh tốt và mọi con bò đều muốn chụp một bức ảnh về vẻ đẹp tự nhiên của nó. Không may, Bessie vẫn có nơi cần đến, nhưng cô không muốn làm gián đoạn bất kỳ buổi chụp ảnh nào.

Bessie hiện đang đứng tại \((X,0)\) trên mặt phẳng \(XY\) và muốn đi đến \((0,Y)\) (\(1\le X,Y\le 10^6\)). Không may, \(N\) (\(1 \leq N \leq 3 \cdot 10^5\)) con bò khác đã quyết định tạo dáng trên trục \(X\). Cụ thể hơn, bò \(i\) sẽ đứng tại \((x_i,0)\) với một nhiếp ảnh gia ở \((0,y_i)\) sẵn sàng chụp ảnh cho nó, trong đó \((1 \leq x_i,y_i \leq 10^6)\). Chúng sẽ bắt đầu tạo dáng ngay trước thời điểm \(s_i\) (\(1 \leq s_i < T\)) và tiếp tục tạo dáng trong thời gian rất dài (chúng phải chụp được bức ảnh thật hoàn hảo). Ở đây, \(1\le T\le N+1\).

Bessie biết lịch chụp ảnh của mọi con bò, và cô sẽ đi quãng đường Euclid ngắn nhất để đến đích mà không cắt qua đường ngắm từ bất kỳ nhiếp ảnh gia nào đến con bò tương ứng (đường đi của cô gồm một hoặc nhiều đoạn thẳng).

Nếu Bessie khởi hành tại thời điểm \(t\), cô sẽ tránh đường ngắm của tất cả các cặp nhiếp ảnh gia/bò bắt đầu tạo dáng tại thời điểm \(s_i \le t\), và gọi khoảng cách đến đích cuối cùng của cô là \(d_t\). Hãy xác định các giá trị \(\lfloor d_t\rfloor\) với mỗi số nguyên \(t\) từ \(0\) đến \(T-1\), tính cả hai đầu.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(T\), lần lượt biểu diễn số con bò tạo dáng trên trục \(x\) và khoảng thời gian Bessie có thể khởi hành.

Dòng thứ hai chứa \(X\) và \(Y\), lần lượt biểu diễn tọa độ \(X\) ban đầu của Bessie và tọa độ \(Y\) đích của cô.

\(N\) dòng tiếp theo chứa \(s_i\) \(x_i\) và \(y_i\). Đảm bảo mọi \(x_i\) đôi một khác nhau và khác \(X\), mọi \(y_i\) đôi một khác nhau và khác \(Y\). Mọi \(s_i\) được cho theo thứ tự không giảm, với \(s_i \leq s_{i+1}\).

Dữ liệu ra

In \(T\) dòng, trong đó dòng thứ \(t\) (đánh số từ \(0\)) chứa \(\lfloor d_t\rfloor\).

Ví dụ

4 5
6 7
1 7 5
2 4 4
3 1 6
4 2 9

9
9
9
10
12

2 3
10 7
1 2 10
1 9 1

12
16
16

5 6
8 9
1 3 5
1 4 1
3 10 7
4 9 2
5 6 6

12
12
12
12
14
14

Phân nhóm

• Inputs 4-6: \(N\le 100\).
• Inputs 7-9: \(N\le 3000\).
• Inputs 10-12: \(T\le 10\).
• Inputs 13-18: Không có ràng buộc bổ sung.

Nguồn

USACO 2025 January Contest, Gold — Photo Op

Đề bài: https://usaco.org/index.php?page=viewproblem2&cpid=1475

Tác giả đề: Suhas Nagar