Kỳ nghỉ hè, Per rủ các bạn lập băng hải tặc để ra khơi tìm kho báu. Per đã tìm thấy một hòn đảo lý tưởng để tìm kiếm. Ban đầu thuyền đang ở điểm ~(x_1, y_1)~ (coi mặt biển là mặt phẳng tọa độ ~Oxy~) và Per muốn di chuyển đến hòn đảo ở điểm ~(x_2, y_2)~.

Per biết trước dự báo thời tiết: xâu ~s~ độ dài ~n~ chỉ gồm các chữ cái ~U~, ~D~, ~L~, ~R~, mỗi ký tự ứng với một hướng gió. Dự báo có tính chu kỳ: ngày thứ nhất gió thổi theo ~s_1~, ngày thứ hai theo ~s_2~, ..., ngày thứ ~n~ theo ~s_n~, ngày thứ ~n + 1~ lại theo ~s_1~, và cứ thế lặp lại.

Gió đẩy thuyền như sau:

• gió ~U~: thuyền đi từ ~(x, y)~ đến ~(x, y + 1)~;
• gió ~D~: thuyền đi từ ~(x, y)~ đến ~(x, y - 1)~;
• gió ~L~: thuyền đi từ ~(x, y)~ đến ~(x - 1, y)~;
• gió ~R~: thuyền đi từ ~(x, y)~ đến ~(x + 1, y)~.

Mỗi ngày, ngoài gió, thuyền còn có thể tự đi ~1~ đơn vị theo một trong bốn hướng trên hoặc đứng yên. Vị trí cuối ngày là tổng của hướng gió và hướng thuyền tự đi. Ví dụ, nếu gió thổi hướng ~U~ còn thuyền đi hướng ~L~ thì từ ~(x, y)~ thuyền tới ~(x - 1, y + 1)~; nếu thuyền cũng đi hướng ~U~ thì nó tới ~(x, y + 2)~.

Hãy giúp Per xác định số ngày ít nhất để thuyền tới được hòn đảo.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~x_1, y_1~ — tọa độ ban đầu của con thuyền.
• Dòng thứ hai chứa hai số nguyên ~x_2, y_2~ — tọa độ của hòn đảo. Dữ liệu đảm bảo hai tọa độ này khác nhau.
• Dòng thứ ba chứa một số nguyên ~n~ — độ dài của xâu ~s~.
• Dòng thứ tư chứa xâu ~s~ chỉ gồm các chữ cái ~U~, ~D~, ~L~, ~R~.

Kết quả

In ra số ngày ít nhất để Per tới được hòn đảo ở tọa độ ~(x_2, y_2)~. Nếu không thể tới được, in ra ~-1~.

Ví dụ

Đầu vào:

0 0
3 5
3
UDU

Đầu ra:

6

Giải thích: Thuyền tự đi theo dãy hướng ~RRRUUU~. Tọa độ thay đổi lần lượt là ~(0, 0) \to (1, 1) \to (2, 0) \to (3, 1) \to (3, 3) \to (3, 3) \to (3, 5)~.

Đầu vào:

0 0
0 2
1
R

Đầu ra:

-1

Giải thích: Con thuyền không bao giờ tới được hòn đảo.

Giới hạn

• ~0 \le x_1, y_1 \le 10^9~
• ~0 \le x_2, y_2 \le 10^9~
• ~(x_1, y_1) \ne (x_2, y_2)~
• ~1 \le n \le 10^5~