Farmer John потерял любимый коровий колокольчик, и Bessie согласилась помочь! Они ищут на ферме по разным маршрутам, поддерживая радиосвязь. Но батарейки садятся, поэтому они хотят спланировать движение, стараясь всегда быть близко и экономить энергию.

Farmer John начинает в $(f_x, f_y)$ и идёт по маршруту из $N$ шагов: 'N' (север), 'E' (восток), 'S' (юг) или 'W' (запад). Bessie начинает в $(b_x, b_y)$ и идёт по аналогичному маршруту из $M$ шагов. Маршруты могут иметь общие точки. На каждом временном шаге Farmer John либо стоит, либо, если ещё не дошёл до конца, делает следующий шаг своего маршрута в указанном направлении. Bessie выбирает аналогично. На каждом шаге, кроме начального в исходных точках, рации тратят энергию, равную квадрату расстояния между ними.

Помогите им выбрать совместную стратегию, минимизирующую суммарную энергию до шага, когда они впервые оба окажутся в конечных точках своих маршрутов, включая этот шаг.

Входные данные

Первая строка содержит $N$ и $M$ ($1 \leq N, M \leq 1000$), вторая — целые $f_x$, $f_y$, третья — $b_x$, $b_y$ ($0 \leq f_x, f_y, b_x, b_y \leq 1000$). Далее строка длины $N$ описывает маршрут FJ, последняя строка длины $M$ — маршрут Bessie.

Всё путешествие координаты находятся в $0 \leq x,y \leq 1000$. Восток — положительное направление $x$, север — положительное направление $y$.

Выходные данные

Выведите целое число — минимальную энергию, затраченную FJ и Bessie в путешествии.

Примеры

Входные данные 1

2 7
3 0
5 0
NN
NWWWWWN

Выходные данные 1

28

Автор задачи: Brian Dean