CS_033 VẬN CHUYỂN

Năm 2226 Việt Nam đã thành công đưa con người lên sao Hỏa và bước đầu xây dựng các căn cứ ở đó. Tuy nhiên do vật tư khan hiếm nên cứ mỗi một thời gian sẽ có các chuyến tàu vũ trụ mang vật tư tiếp tế cho các căn cứ. Có N thùng tiếp tế, mỗi thùng sẽ do một Robot vận chuyển từ tàu vũ trụ cho đến N căn cứ khác nhau.

Các Robot sẽ mô phỏng bề mặt sao Hỏa là hệ trục tọa độ Oxy sao cho gốc tọa độ là vị trí hạ cánh của tàu vũ trụ, đồng thời các căn cứ luôn nằm tại các điểm có tọa độ nguyên. Mỗi Robot được lập trình sẵn một chuỗi lệnh điều khiển độ dài S, bao gồm các ký tự:
: Điều khiển Robot di chuyển từ (x, y) đến (x, y + 1)
D: Điều khiển Robot di chuyển từ (x, y) đến (x, y - 1)
L: Điều khiển Robot di chuyển từ (x, y) đến (x - 1, y)
R: Điều khiển Robot di chuyển từ (x, y) đến (x + 1, y)
Ban đầu, tất cả Robot có chung một chuỗi lệnh điều khiển giống nhau, điều này khiến cho các Robot có thể không đến được căn cứ được chỉ định. Để khắc phục, các kỹ sư cho phép Robot chọn duy nhất một đoạn lệnh liên tiếp và thay thế tùy ý các ký tự trong đoạn đó bằng các ký tự mới sao cho độ dài đoạn không đổi.

Yêu cầu: Với mỗi căn cứ, hãy tìm độ dài ngắn nhất của đoạn lệnh liên tiếp cần phải sửa để Robot kết thúc hành trình đúng tại tọa độ của căn cứ đó.

Dữ liệu vào có cấu trúc như sau:
Dòng 1: Gồm 2 số nguyên dương N là số lượng căn cứ và S là độ dài chuỗi lệnh.
Dòng 2: Xâu ký tự điều khiển ban đầu có độ dài S.
N dòng tiếp theo: Mỗi dòng chứa 2 số nguyên x, y là tọa độ (x,y) của các căn cứ.

Dữ liệu ra gồm N dòng, mỗi dòng là một số nguyên là độ dài đoạn lệnh ngắn nhất cần sửa. Nếu không thể sửa để đến được căn cứ, in ra -1.

Ví dụ INPUT

3 5

UUURR

3 1

2 3

3 2

Dữ liệu ra:

-1

0

1