Magic Ship

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem Statement

A ship starts at $(x_1,y_1)$ and wants to reach $(x_2,y_2)$. A wind string $s$ of length $n$ repeats forever; each day wind moves the ship one unit accordingly. The captain may additionally move one unit in a cardinal direction or stay. Find the minimum number of days, or $-1$ if impossible.

Input

Lines contain start, destination, $n$, and the wind string.

Output

Print the minimum days or -1.

Subtasks

• Subtask 1 — 20%: $n\le100$.
• Subtask 2 — 30%: $n\le5000$.
• Subtask 3 — 50%: coordinates in $[0,10^9]$, $n\le10^5$.

Example

Input

0 0
4 6
3
UUU

Output

5

Explanation

Five days are sufficient and fewer are not.