Con tàu phép thuật (Magic Ship)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Con tàu bắt đầu tại $(x_1,y_1)$ và cần đến $(x_2,y_2)$. Dự báo gió là chuỗi $s$ độ dài $n$, lặp lại vô hạn theo chu kỳ.

Mỗi ngày, gió tự động dịch tàu một đơn vị theo ký tự U, D, L hoặc R. Đồng thời, thuyền trưởng có thể chủ động:

• đi thêm một đơn vị theo một trong bốn hướng; hoặc
• đứng yên.

Hai độ dịch chuyển trong ngày được cộng lại.

Hãy tìm số ngày nhỏ nhất để có thể đến đúng đích. Nếu không bao giờ có thể tới, in -1.

Input

• Dòng 1: $x_1,y_1$.
• Dòng 2: $x_2,y_2$.
• Dòng 3: $n$.
• Dòng 4: chuỗi $s$ độ dài $n$.

Output

In số ngày nhỏ nhất hoặc -1.

Subtask

• Subtask 1 — 20%: $n\le100$.
• Subtask 2 — 30%: $n\le5000$.
• Subtask 3 — 50%: $0\le x_1,y_1,x_2,y_2\le10^9$, $1\le n\le10^5$. Hai điểm đầu và cuối khác nhau.

Ví dụ

Input

0 0
4 6
3
UUU

Output

5

Giải thích

Sau $5$ ngày, gió đẩy tổng cộng lên $5$ đơn vị; thuyền trưởng có $5$ bước chủ động và có thể dùng chúng để bù phần còn lại, nên tới được $(4,6)$. Không thể làm trong ít ngày hơn.