Bộ phim mới Thành Long (diễn viên nổi tiếng của Hollywood) vào vai một điệp viên. Trong phim anh được tổ chức giao nhiệm vụ theo dõi một tên trùm Mafia. Theo tìm hiểu của anh, tên trùm Mafia thường vừa đi vừa trao đổi điện thoại trên xe ô tô trong thị trấn. Vì vậy, anh quyết định ngồi ở một vị trí nào đó và nghe lỏm thông tin trao đổi của hắn.
Trị trấn được biểu diễn như là một mặt phẳng hệ trục tọa độ. Trùm Mafia đi từ vị trí (0,0), và mỗi vị trí hắn có thể di chuyển 1 đơn vị theo một trong 4 hướng: phải, trái, lên hoặc xuống.
Chàng điệp viên đang ngồi ở vị trí (x,y), và anh chỉ nghe lỏm được về thông tin của tên trùm nếu vị trí của anh trùng vị trí của tên trùm hoặc vị trí tên trùm thuộc 1 trong 8 vị trí liền kề với vị trí của anh.
Nhiệm vụ của bạn là viết chương trình tìm các thời điểm mà Chàng điệp viên đã nghe được cuộc trò chuyện.
Dữ liệu vào:
- Dòng đầu chứa hai số nguyên x và y, -104 ≤ x, y ≤ 104 là vị trí của chàng điệp viên
- Dòng tiếp theo chứa số nguyên k, 1 ≤ k ≤ 105, là độ dài đường di chuyển của trên trùm Mafia
- Dòng tiếp theo chứa K ký tự chỉ cho ta biết con đường mà tên trùm đi hôm đó. Trong đó ký tự ‘R’ – Phải, ‘U’ – Trên, ‘L’ – trái, và ‘D’ – dưới.
Kết quả ra:
- Nếu không thể nghe được cuộc trò chuyện nào thì ghi ra số -1.
- Nếu nghe được các cuột trò chuyện thì ghi ra các thời điểm nghe được cuộc trò chuyện. Mỗi thời điểm trên một dòng.