#!/usr/bin/python3 def debug(msg): # print(msg) pass # Manhattanská (součtová) vzdálenost dvou bodů def manhattan(a, b): return abs(a[0]-b[0]) + abs(a[1]-b[1]) # Najde cestu mezi políčky z1, z2 v bludišti řádu r # Vrátí buďto (vzdálenost, None, None), pokud cesta vede vnitřkem # nebo (dosavadní vzdálenost, p1, p2), pokud je třeba propojit venkem portály p1, p2. # Při zavolání se z2=None hledá výstupní portál k políčku z1, vrací (vzdálenost k portálu, p1, None). def propoj(z1, z2, r): debug("< z1={} z2={} r={}".format(z1, z2, r)) # Triviální bludiště řádu 0: každé volné políčko je portálem if r == 0: debug("> d=0 p1={} p2={}".format(z1, z2)) return 0, z1, z2 # w = šířka bludiště - 1, s = poloviční šířka (pozice tunelů) s = 1 << r w = 2*s d = 0 debug("\ts={} w={}". format(s, w)) # Zjistí, ve kterém kvadrantu leží bod z def quad(z): x, y = z i = 1 if x > s: i += 2 if y > s: i += 1 return i # Převádí z globálních souřadnic na lokální uvnitř kvadrantu i def zoom(z, i): x, y = z if i >= 3: x -= s if i == 2 or i == 4: y -= s if i == 1: x, y = y, s-x elif i == 2: x, y = s-y, x return x, y # Převádí naopak z lokálních souřadnic na globální def unzoom(z, i): x, y = z if i == 1: x, y = s-y, x elif i == 2: x, y = y, s-x if i == 2 or i == 4: y += s if i >= 3: x += s return x, y # Pokud z leží uvnitř tunelu, vrátí jeho portál; jinak vrátí None def tunel(z): x, y = z if x > 0 and x < s and y == s or \ x == s and y > 0 and y < w: return 0, s if x > s and x < w and y == s: return w, s return None # Pokud jsme dostali jen jeden bod, máme pro něj najít portál if z2 == None: q1 = quad(z1) debug("\tq1={}".format(q1)) d, p1, _ = propoj(zoom(z1, q1), None, r-1) p1 = unzoom(p1, q1) t1 = tunel(p1) if t1 != None: d += manhattan(p1, t1) p1 = t1 debug("> d={} p1={}".format(d, p1)) return d, p1, None # Dostali jsme dva body q1 = quad(z1) q2 = quad(z2) debug("\tq1={} q2={}".format(q1, q2)) if q1 == q2: # Leží ve stejném kvadrantu: rekurze na tento kvadrant d, p1, p2 = propoj(zoom(z1, q1), zoom(z2, q2), r-1) if p1 == None: # Propojeno vnitřkem debug("> d={}".format(d)) return d, None, None # Převedeno na propojení portálů p1, p2 else: # Leží v různých kvadrantech: převedeme na propojení portálů p1, p2 d1, p1, _ = propoj(zoom(z1, q1), None, r-1) d2, p2, _ = propoj(zoom(z2, q2), None, r-1) d = d1 + d2 p1 = unzoom(p1, q1) p2 = unzoom(p2, q2) # Pokud portály leží uvnitř tunelů, najdeme konce tunelů t1 = tunel(p1) t2 = tunel(p2) if t1 != None and t1 == t2: # Oba ve stejném tunelu => propojíme vnitřkem d += manhattan(p1, p2) return d, None, None if t1 != None: d += manhattan(p1, t1) p1 = t1 if t2 != None: d += manhattan(p2, t2) p2 = t2 debug("> d={} p1={} p2={}".format(d, p1, p2)) return d, p1, p2 # Vypočítá vzdálenost políček z1, z2 v bludišti řádu r def vzdalenost(z1, z2, r): d, p1, p2 = propoj(z1, z2, r) debug("=> d={} p1={} p2={}".format(d, p1, p2)) d += 1 if p1 == None: # Cesta vede vnitřkem => vzdálenost už je kompletní return d # Ještě zbývá propojit portály p1, p2 w = 1 << (r+1) x1, y1 = p1 x2, y2 = p2 if x1 == 0 and x2 == w or x1 == w and x2 == 0: # Jeden nahoře, druhý dole: buď levem nebo pravem d += min(y1+y2, (w-y1)+(w-y2)) + w elif y1 == 0 and y2 == w or y1 == w and y2 == 0: # Jeden nalevo, druhý napravo: buď horem nebo dolem d += min(x1+x2, (w-x1)+(w-x2)) + w else: # V ostatních případech stačí započítat manhattanskou vzdálenost portálů d += manhattan(p1, p2) return d # Hlavní program r, x1, y1, x2, y2 = map(int, input().split(" ")) print(vzdalenost((x1,y1), (x2,y2), r))