Robot

Je dána síť skládající se ze stejně velkých čtverců rozložených do obdélníku s M řádky a N sloupci.
Okolí jednoho čtverce je množina všech čtverců sítě, které hranou sousedí s tímto čtvercem. Každý čtverec v síti tak má nejvýše čtyři další ve svém okolí. Rohové čtverce sítě mají jen dva čtverce ve svém okolí a čtverce, které nejsou rohové a přiléhají k okraji sítě, mají ve svém okolí tři čtverce.
Každý čtverec je navíc označen určitým nezáporným celým číslem. Označení čtverce v řádku r a sloupci s sítě tj. na pozici [r, s] je dáno funkcí
f(r, s) = ((r×N+s) × a) mod b, kde a, b jsou kladná celá čísla. Levý horní rohový čtverec sítě má souřadnice [0, 0], pravý dolní rohový čtverec sítě má souřadnice [M−1, N−1].

Experimentální robot prohledává síť po krocích tak, že se v každém kroku přesune z jednoho čtverce do jiného čtverce v jeho okolí. Robot při prohledávání začne v určitém čtverci sítě a potom postupuje po krocích podle strategie prohledávání do hloubky. Pro postup vpřed si ve svém okolí pro příští krok vybere vždy ten čtverec, jehož označení má nejmenší hodnotu ze všech dosud nenavštívených čtverců. Pokud alespoň dva sousední čtverce sdílí stejnou minimální hodnotu označení, dává robot přednost pohybu nejprve po řádku doleva, pak doprava, pak ve sloupci vzhůru a nakonec dolů. Je zřejmé, že uvedené pravidlo pohybu novlivňuje korektnost postupu prohledávání do hloubky, a po prohledání celé sítě se robot vrací na svou výchozí pozici.

Našim úkolem je určit, kolik kroků robot provede, než se přemístí z výchozí pozice na jinou předem určenou význačnou pozici P v síti.

Vstup

Na vstupu jsou dva řádky. První řádek obsahuje hodnoty M, N, a, b v tomto pořadí. Druhý řádek obsahuje hodnoty r1, s1, r2, s2, v tomto pořadí. Hodnota r1 resp. s1 je číslo řádku resp. sloupce počáteční pozice robota, hodnota r2 resp. s2 je číslo řádku resp. sloupce význačné pozice P. Hodnoty v každém řádku jsou odděleny mezerou. Žádná z hodnot M, N, a, b nepřevýší 10000.

Výstup

Na výstupu je jediný řádek s číslem udávajícím počet kroků, které robot potřeboval na přemístění z počáteční pozice [r1, s1] do význačné pozice P = [r2, s2].

Příklad 1

Vstup:
3 6 7 11
1 2 2 4
Výstup:
11
Pro zadané parametry je vzhled sítě tento:
 0   7   3  10   6   2
 9   5   1   8   4   0
 7   3  10   6   2   9

Příklad 2

Vstup:
4 3 41 17
2 1 3 0
Výstup:
14
Pro zadané parametry je vzhled sítě tento:
   0   7  14
   4  11   1
   8  15   5
  12   2   9

Příklad 3

Vstup:
1000 1000 223 311
1 1 600 600
Výstup:
808168

Veřejná data k úloze jsou k dispozici. Veřejná data jsou uložena také v odevzdávacím systému a při každém odevzdání/spuštění úlohy dostává řešitel kompletní výstup na stdout a stderr ze svého programu pro každý soubor veřejných dat.

Veřejná data