Nhờ sự phát triển của công nghệ thông tin và truyền thông (ICT), xe hơi kết nối (connected car) — loại xe từng được coi là phương tiện của tương lai với khả năng cung cấp nhiều dịch vụ cho người lái thông qua kết nối Internet — đã trở thành hiện thực. Để bắt kịp xu hướng này, Hyundai AutoEver đang xây dựng nền tảng dịch vụ xe hơi kết nối thế hệ mới, áp dụng các công nghệ ICT tiên tiến bao gồm điện toán đám mây và Internet vạn vật (IoT), đồng thời tích lũy các công nghệ phần mềm cốt lõi để hoàn thiện những chiếc xe hơi kết nối tốt nhất.
Hyun-oh, một kỹ sư tại Hyundai AutoEver, trong khi đang suy nghĩ về các dịch vụ mới, đã quyết định thực hiện một thí nghiệm kết hợp giữa IoT và công nghệ định vị, vốn là những công nghệ cốt lõi của xe hơi kết nối. Chương trình thí nghiệm mà Hyun-oh phát triển có các chức năng sau:
- Hyun-oh có thể điều khiển từ xa các xe hơi kết nối đã được kết nối với IoT.
- Khi một xe hơi kết nối đã được kết nối với IoT ở cùng vị trí với một xe hơi kết nối chưa được kết nối, xe hơi đó có thể được kết nối với IoT. Sau đó, ngay cả khi hai xe hơi này di chuyển ra xa nhau, kết nối vẫn được duy trì.
Để thực hiện thí nghiệm, Hyun-oh đã sắp xếp $N$ chiếc xe hơi kết nối theo một hàng dọc, được đánh số từ $1$ đến $N$. Vị trí ban đầu của xe thứ $i$ là $x_i$ và lượng nhiên liệu là $h_i$. Tất cả các xe hơi kết nối đều tiêu thụ $1$ đơn vị nhiên liệu để di chuyển một khoảng cách bằng $1$, và không thể di chuyển thêm nếu đã tiêu thụ hết nhiên liệu.
Ban đầu, tất cả các xe hơi kết nối đều chưa được kết nối với IoT. Hyun-oh trước tiên kết nối xe thứ $S$ với IoT, sau đó sử dụng các chức năng của chương trình một cách hợp lý để lan truyền kết nối IoT sang các xe khác.
Tùy thuộc vào cách Hyun-oh điều khiển các xe, tập hợp các xe hơi kết nối với IoT trong thí nghiệm có thể thay đổi. Khi Hyun-oh thực hiện thí nghiệm nhiều lần theo nhiều cách khác nhau, hãy tìm tất cả các xe hơi kết nối có khả năng được kết nối với IoT.
Dữ liệu vào
- Dòng đầu tiên chứa $N$ và $S$. ($1 \le N \le 1\,000\,000$; $1 \le S \le N$)
- Dòng thứ hai chứa vị trí ban đầu của mỗi xe $x_1, x_2, \dots, x_N$ được phân cách bởi dấu cách. ($0 \le x_i \le 10^9$; $x_i \le x_{i+1}$)
- Dòng thứ ba chứa lượng nhiên liệu của mỗi xe $h_1, h_2, \dots, h_N$ được phân cách bởi dấu cách. ($1 \le h_i \le 10^9$)
Dữ liệu ra
- Dòng đầu tiên in ra số hiệu của tất cả các xe hơi kết nối có khả năng được kết nối với IoT, sắp xếp theo thứ tự tăng dần.
Ví dụ
Dữ liệu vào 1
5 3 1 2 4 5 8 2 1 2 2 3
Dữ liệu ra 1
1 2 3 4
Ghi chú
Trong ví dụ, các tập hợp xe hơi kết nối với IoT có thể thu được từ kết quả thí nghiệm là $\{1, 2, 3\}$, $\{2, 3\}$, $\{3\}$, và $\{3, 4\}$.