B. Дарвуулт завь

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Цагаан баавгайнууд загасчилж байна. Тэд ($s_x, s_y$)-ээс ($e_x, e_y$)-рүү аялах гэж байгаа. Тэдний завь зөвхөн салхины хүчээр явдаг. Секунт бүрд салхи урд, хойд, баруун, зүүн зүгрүү салхилдаг. Завь нь ($x, y$) байгаа гэж үзвэл

  • Хэрвээ салхи зүүн зүгт салхилвал завь ($x+1, y$)-рүү шилжинэ
  • Хэрвээ салхи урд зүгт салхилвал завь ($x, y-1$)-рүү шилжинэ
  • Хэрвээ салхи баруун зүгт салхилвал завь ($x-1, y$)-рүү шилжинэ
  • Хэрвээ салхи хойд зүгт салхилвал завь ($x$, $y+1$)-рүү шилжинэ

Мөн тэд завиа зангуугаар зогсоож болдог. Энэ тохиолдолд завь ($x, y$) координат дээрээ үлдэнэ. Өгөгдсөн салхи $t$ секунт үргэлжлэх үеийн чиглэл өгөгдсөн бол ($e_x, e_y$)-т очиход зарцуулах хамгийн бага хугацааг ол.

Оролт

Эхний мөр $t$, $s_x$, $s_y$, $e_x$, $e_y$ ($1 ≤ t ≤10^5$, $-10^9 ≤ s_x, s_y, e_x, e_y ≤ 10^9$) тоонууд өгөгдөнө. Эхлэх байрлал нь төгсөх байрлалаас ялгаатай байна.

Хоёрдох мөр нь $t$ тэмдэгт агуулна. $i$ дах тэмдэгт нь салхины $i$ дахь секунд дахь чиглэлийг заана. Энэ нь дараах 4 боломжтой : E (зүүн) S (урд) W (баруун) N (хойд).

Гаралт

Хэрвээ тэд ($e_x, e_y$)-д $t$ секундэд очсон байж чадах бол очиход зарцуулах хамгийн бага цагийг чадахгүй бол "-1"-г хэвлэ.

Орчуулсан: Баттулга

Жишээ тэстүүд

Оролт
5 0 0 1 1
SESNW
Гаралт
4
Оролт
10 5 3 3 6
NENSWESNEE
Гаралт
-1

Тэмдэглэл

In the first sample, they can stay at seconds $1$, $3$, and move at seconds $2$, $4$.

In the second sample, they cannot sail to the destination.

Сэтгэгдлүүдийг ачааллаж байна...