Cho nhật ký (log) kết nối gồm n dòng, mỗi dòng ghi lại một lần một địa chỉ IP nguồn kết nối tới một cổng đích tại một thời điểm (giây):
timestamp src_ip dst_port
Dữ liệu được đảm bảo cho theo thứ tự không giảm dần của timestamp (các dòng có cùng timestamp có thể xuất hiện theo thứ tự bất kỳ).
Cho hai tham số W (độ rộng cửa sổ thời gian, tính bằng giây) và K (ngưỡng số cổng khác nhau). Một địa chỉ IP nguồn được coi là SCANNER (có dấu hiệu quét cổng) nếu tồn tại một cửa sổ thời gian [t,t+W] (đóng ở cả hai đầu) sao cho trong khoảng đó, IP này đã kết nối tới ít nhất K cổng đích khác nhau (mỗi cổng chỉ tính một lần dù xuất hiện nhiều lần).
Hãy in ra danh sách các địa chỉ IP bị đánh dấu là SCANNER, theo thứ tự từ điển tăng dần, mỗi IP một dòng. Nếu không có IP nào bị đánh dấu, in ra NO SCAN DETECTED.
Ví dụ:
Input:
8
1 10.0.0.5 22
1 10.0.0.7 22
2 10.0.0.5 23
2 10.0.0.7 22
3 10.0.0.5 24
4 10.0.0.5 25
5 10.0.0.6 80
100 10.0.0.5 26
5 4
Output:
10.0.0.5
(Từ t=1 đến t=4 (độ rộng 3≤W=5), 10.0.0.5 đã kết nối tới 4 cổng khác nhau (22,23,24,25) ≥K=4 nên bị đánh dấu. 10.0.0.7 chỉ kết nối lặp lại cổng 22 nên không đủ. 10.0.0.6 chỉ có 1 kết nối.)
Dòng đầu là số nguyên n (0≤n≤2000) — số dòng log.
n dòng tiếp theo, mỗi dòng dạng timestamp src_ip dst_port (0≤timestamp≤109, 0≤dst_port≤65535), được sắp xếp theo timestamp không giảm dần.
Dòng cuối cùng gồm hai số nguyên W và K (1≤W≤109, 1≤K≤2000), cách nhau bởi khoảng trắng.
Nếu có ít nhất một IP bị đánh dấu SCANNER, in ra các IP đó theo thứ tự từ điển tăng dần, mỗi IP một dòng. Nếu không có IP nào, in ra đúng một dòng NO SCAN DETECTED.
Ví dụ:
Đầu vào:
2
1 1.1.1.1 22
2 1.1.1.1 22
5 4
Đầu ra:
NO SCAN DETECTED
Đầu vào:
8
1 10.0.0.5 22
1 10.0.0.7 22
2 10.0.0.5 23
2 10.0.0.7 22
3 10.0.0.5 24
4 10.0.0.5 25
5 10.0.0.6 80
100 10.0.0.5 26
5 4
Đầu ra:
10.0.0.5
Đang tải editor...