You are looking at the floor plan of the Summer Informatics School's new building. You were tasked with SIS logistics, so you really care about travel time between different locations: it is important to know how long it would take to get from the lecture room to the canteen, or from the gym to the server room.

The building consists of n towers, h floors each, where the towers are labeled from 1 to n, the floors are labeled from 1 to h. There is a passage between any two adjacent towers (two towers i and i + 1 for all i: 1 ≤ i ≤ n - 1) on every floor x, where a ≤ x ≤ b. It takes exactly one minute to walk between any two adjacent floors of a tower, as well as between any two adjacent towers, provided that there is a passage on that floor. It is not permitted to leave the building.

 [Image]

The picture illustrates the first example. 

You have given k pairs of locations (t_{a}, f_{a}), (t_{b}, f_{b}): floor f_{a} of tower t_{a} and floor f_{b} of tower t_{b}. For each pair you need to determine the minimum walking time between these locations.


-----Input-----

The first line of the input contains following integers:

  n: the number of towers in the building (1 ≤ n ≤ 10^8),  h: the number of floors in each tower (1 ≤ h ≤ 10^8),  a and b: the lowest and highest floor where it's possible to move between adjacent towers (1 ≤ a ≤ b ≤ h),  k: total number of queries (1 ≤ k ≤ 10^4). 

Next k lines contain description of the queries. Each description consists of four integers t_{a}, f_{a}, t_{b}, f_{b} (1 ≤ t_{a}, t_{b} ≤ n, 1 ≤ f_{a}, f_{b} ≤ h). This corresponds to a query to find the minimum travel time between f_{a}-th floor of the t_{a}-th tower and f_{b}-th floor of the t_{b}-th tower.


-----Output-----

For each query print a single integer: the minimum walking time between the locations in minutes.


-----Example-----
Input
3 6 2 3 3
1 2 1 3
1 4 3 4
1 2 2 3

Output
1
4
2

Difficulty: interview

Starter code:

Solutions:
n, h, a, b, k = map(int, input().split())
for i in range(k):
    t1, f1, t2, f2 = map(int, input().split())
    if t1 == t2:
        print(abs(f1 - f2))
    elif f1 >= a and f1 <= b:
        print(abs(t2 - t1) + abs(f2 - f1))
    elif f1 < a:
        print(abs(a - f1) + abs(t2 - t1) + abs(f2 - a))
    elif f1 > b:
        print(abs(b - f1) + abs(t2 - t1) + abs(f2 - b))

import sys
import os

def solve(a, b, t1, f1, t2, f2):
    if t1 == t2:
        return abs(f1 - f2)
    elif (f1 >= a and f1 <= b) or (f2 >= a and f2 <= b):
        return abs(t1 - t2) + abs(f1 - f2)
    elif f1 > b and f2 > b:
        return abs(t1 - t2) + f1 + f2 - 2 * b
    elif f1 < a and f2 < a:
        return abs(t1 - t2) + 2 * a - f1 - f2
    else:
        return abs(t1 - t2) + abs(f1 - f2)

def main():
    n, h, a, b, k = map(int, input().split())
    for i in range(k):
        t1, f1, t2, f2 = map(int, input().split())
        print(solve(a, b, t1, f1, t2, f2))


def __starting_point():
    main()
__starting_point()

n, h, a, b, k = list(map(int, input().strip().split()))

for i in range(k):
    ta, fa, tb, fb = list(map(int, input().strip().split()))
    ans = 0
    to = fa
    if (ta == tb):
        print(abs(fa - fb))
        continue
    if (fa > b):
        ans = fa - b
        to = b
    if (fa < a):
        ans = a - fa
        to = a
    ans += abs(tb - ta)
    ans += abs(fb - to)
    print(ans)


n,h,a,b,k=list(map(int,input().strip().split()))
for i in range(k):
	t1,f1,t2,f2=list(map(int,input().strip().split()))
	if (t1==t2):
		print(abs(f1-f2))
		continue
	else:
		e=abs(t1-t2)
		if (f1>=a and f1<=b):
			print(e+abs(f1-f2))
		elif (f1<a):
			print(e+a-f1+abs(a-f2))
		else:
			print(e+f1-b+abs(b-f2))


def main():
    n, h, a, b, k = [int(x) for x in input().split()]

    for _ in range(k):
        ta, fa, tb, fb = [int(x) for x in input().split()]

        if ta == tb:
            print(abs(fa - fb))
            continue

        sum = 0
        if not (a <= fa <= b):
            if fa < a:
                sum += a - fa
                sum += abs(a - fb)
            else:
                sum += fa - b
                sum += abs(b - fb)
        else:
            sum = abs(fa - fb)

        print(abs(ta - tb) + sum)


def __starting_point():
    main()

__starting_point()

n, h, a, b, k = map(int, input().split())
for i in range(k):
    ta, fa, tb, fb = map(int, input().split())
    if (ta == tb):
        ans = abs(fa - fb)
    elif (fa < a and fb < a):
        ans = (a - fa) + (a - fb) + abs(ta - tb)
    elif (fa > b and fb > b):
        ans = (fa - b) + (fb - b) + abs(ta - tb)
    else:
        ans = abs(fa - fb) + abs(ta - tb)
    print(ans)

s=input().split()
n,h,a,b,k=int(s[0]),int(s[1]),int(s[2]),int(s[3]),int(s[4])
for que in range(k):
    s=input().split()
    ta,fa,tb,fb=int(s[0]),int(s[1]),int(s[2]),int(s[3])
    if ta==tb:
        print(abs(fa-fb))
    else:
        if a<=fa<=b:
            print(abs(fa-fb)+abs(ta-tb))
        elif fa<a:
            print(abs(a-fa)+abs(a-fb)+abs(ta-tb))
        elif fa>b:
            print(abs(b-fa)+abs(b-fb)+abs(ta-tb))


n, h, a, b, k = list(map(int, input(). split()))
for i in range(k):
    t1, f1, t2, f2 = list(map(int, input(). split()))
    if t1 == t2:
        print(abs(f1-f2))
        continue
    ans = abs(t1-t2)
    p = 0
    if f1 < a:
        ans += a - f1
        p = a
    elif f1 > b:
        ans += f1 - b
        p = b
    else:
        p = f1
    ans += abs(p - f2)
    print(ans)


n,h,a,b,k=list(map(int,input().strip().split()))
for i in range(k):
    ta,fa,tb,fb=list(map(int,input().strip().split()))
    if(ta==tb):
        print(abs(fa-fb))
    else:
        if(fa<=b and fa>=a):
            print(abs(ta-tb)+abs(fa-fb))
        else:
            if(fa>b):
                print(fa-b+abs(ta-tb)+abs(b-fb))
            else:#ie fa<a
                print(a-fa+abs(ta-tb)+abs(fb-a))


d = list(map(int, input().split()))
n = d[0]
h = d[1]
a = d[2]
b = d[3]
k = d[4]

ans = []

for i in range(k):
	t = 0
	d = list(map(int, input().split()))
	ta = d[0]
	fa = d[1]
	tb = d[2]
	fb = d[3]
	
	if ta == tb:
		ans.append(abs(fa - fb))
	else:
		if fa > b:
			ans.append((fa-b)+abs(ta-tb)+abs(b-fb))
		elif fa < a:
			ans.append((a-fa)+abs(ta-tb)+abs(a-fb))
		else:
			ans.append(abs(ta-tb)+abs(fa-fb))
			
for i in range(k):
	print(ans[i])
	



from sys import stdin as cin
from sys import stdout as cout

def main():
    n, h, a, b, k = list(map(int, cin.readline().split()))
    for i in range(k):
        ta, fa, tb, fb = list(map(int, cin.readline().split()))
        if ta == tb:
            print(abs(fa - fb))
        else:
            o = abs(ta - tb)
            if fa < a and fb < a:
                o += 2 * a - fa - fb
            elif fa > b and fb > b:
                o += fa + fb - 2 * b
            else:
                o += abs(fb - fa)
            print(o)

main()


n,h,a,b,k=map(int,input().split())
for i in range(k):
    ta,fa,tb,fb=map(int,input().split())
    if ta==tb:
        print(abs(fa-fb))
        continue
    ans=abs(ta-tb)
    if a<=fa<=b:
        first=fa
    elif abs(fa-a)<abs(fa-b):
        first=a
        ans+=abs(fa-a)
    else:
        first=b
        ans+=abs(fa-b)
    ans+=abs(fb-first)
    print(ans)

from sys import stdin
from math import *

line = stdin.readline().rstrip().split()
n = int(line[0])
h = int(line[1])
a = int(line[2])
b = int(line[3])
k = int(line[4])

for i in range(k):
    numbers = list(map(int, stdin.readline().rstrip().split()))
    ta = numbers[0]
    fa = numbers[1]
    tb = numbers[2]
    fb = numbers[3]

    if ta == tb:
        print(abs(fa-fb))
    else:
        total = 0
        if fa < a:
            total += a - fa
            total += abs(fb - a)
        elif fa > b:
            total += fa - b
            total += abs(fb - b)
        else:
            total += abs(fa-fb)
        total += abs(ta - tb)
        print(total)


n,h,a,b,k=map(int,input().split())
while(k):
    k-=1
    ta,fa,tb,fb=map(int,input().split())
    ans=0
    if ta==tb:
        print(abs(fa-fb))
        continue
    if fa<a:
        ans+=a-fa
        ans+=abs(fb-a)
    elif fa>b:
        ans+=fa-b
        ans+=abs(fb-b)
    else:
        ans+=abs(fa-fb)
    ans+=abs(ta-tb)
    print(ans)

n, h, a, b, k = list(map(int,input().split()))
for _ in range(k):
    x, y, w, z = list(map(int,input().split()))
    if x == w:
        print(abs(y-z))
    elif a <= min(y,z) and max(y,z) <= b:
        print(abs(y-z)+abs(x-w))
    else:
        print((min(
            abs(y-a)+abs(z-a)+abs(x-w),
            abs(y-b)+abs(z-b)+abs(x-w)
        )))


n, h, a, b, k = tuple(map(int, input().split()))

for _ in range(k):
    fa, ta, fb, tb = tuple(map(int, input().split()))
    s = abs(fa - fb) + abs(ta - tb)
    if fa != fb:
        if ta < a and tb < a:
            s += 2 * min(a - ta, a - tb)
        if ta > b and tb > b:
            s += 2 * min(ta - b, tb - b)
    print(s)


import sys
import io

stream_enable = 0

inpstream = """
3 6 2 3 3
1 2 1 3
1 4 3 4
1 2 2 3

"""

if stream_enable:
    sys.stdin = io.StringIO(inpstream)
    input()

def inpmap():
    return list(map(int, input().split()))

n, h, a, b, k = inpmap()
for i in range(k):
    ta, fa, tb, fb = inpmap()
    r = 0
    if ta != tb:
        if fa > b:
            r += fa - b
            fa = b
        if fa < a:
            r += a - fa
            fa = a
    r += abs(ta - tb)
    r += abs(fa - fb)
    print(r)


n,h,a,b,k=list(map(int,input().split()))
for i in range(k):
    ta,fa,tb,fb=list(map(int,input().split()))
    s=abs(ta-tb)
    if ((fa<a) or (fa>b)) and (ta!=tb):
        s+=min(abs(fa-a),abs(fa-b))
        if abs(fa-a)<abs(fa-b):
            e=a
        else:
            e=b
        s+=abs(fb-e)
    else:
        s+=abs(fa-fb)
    print(s)


inp = input().split(" ")
for i in range(len(inp)):
    inp[i] = int(inp[i])
n, h, a, b, k = inp
queries = []
for i in range(k):
    q = input().split(" ")
    for i in range(len(q)):
        q[i] = int(q[i])
    queries.append(q)
for query in queries:
    t1, f1, t2, f2 = query
    distance = abs(t2 - t1)
    if a <= f1 <= b or t1 == t2:
        distance += abs(f2 - f1)
    elif f1 < a:
        distance += (a - f1) + abs(f2 - a)
    else: # f2 > b:
        distance += (f1 - b) + abs(f2 - b)
    print(distance)


n, h, a, b, k = list(map(int, input().split()))
for i in range(k):
    fa, ta, fb, tb = list(map(int, input().split()))
    if (ta > tb):
        ta, tb = tb, ta
    if (fa == fb and ta == tb):
        print(0)
        continue
    
    ans = abs(fa - fb)
    
    if fa == fb:
        ans += abs(ta - tb)
    elif (ta > b):
        ans += abs(ta - b) + abs(b - tb)
    elif (tb < a):
        ans += abs(a - tb) + abs(a - ta)
    else:
        ans += abs(ta - tb)
    print(ans)


n, h, a, b, k = map(int, input().split())
for i in range(k):
    num = 0
    p, q, r, s = map(int, input().split())
    if p == r:
        num = abs(q - s)
    elif a <= q <= b:
        num += abs(p - r)
        num += abs(q - s)
    elif b < q:
        num += q - b
        num += abs(p - r)
        num += abs(b - s)
    else:
        num += a - q
        num += abs(p - r)
        num += abs(a - s)

    print(num)

USE_STDIO = False

if not USE_STDIO:
    try: import mypc
    except: pass

def main():
    n, h, a, b, k = list(map(int, input().split(' ')))
    for _ in range(k):
        ta, fa, tb, fb = list(map(int, input().split(' ')))
        if ta == tb:
            ans = abs(fa - fb)
        else:
            ans = abs(ta - tb)
            if fa > fb: fa, fb = fb, fa
            if a <= fa <= b or fa <= a <= fb:
                ans += fb - fa
            elif fa >= b:
                ans += fa - b + fb - b
            elif fb <= a:
                ans += a - fa + a - fb
        print(ans)


def __starting_point():
    main()




__starting_point()

n,h,a,b,k=map(int,input().split())
for i in range(k):
    y1,x1,y2,x2=map(int,input().split())
    if y1==y2:
        print(abs(x1-x2))
    else:
        if (x1<=b and x2>=a) or (x1>=a and x2<=b):
            print(abs(y1-y2)+abs(x1-x2))
        elif x1>=a:
            print(abs(y1-y2)+abs(x1-b)+abs(x2-b))
        elif x1<=a:
            print(abs(y1-y2)+abs(x1-a)+abs(x2-a))

n, h, a, b, k = list(map(int, input().split()))
for i in range(k):
    ta, fa, tb, fb = list(map(int, input().split()))
    if ta == tb:
        print(abs( fa - fb))
    elif a <= fa <= b:
        print(abs(ta - tb) + abs(fa - fb))
    elif fa > b:
        print(abs(fa - b) + abs(ta - tb) + abs(b - fb))
    elif fa < a:
        print(abs(fa - a) + abs(ta - tb) + abs(a - fb))



n,h,a,b,k=list(map(int,input().split()))
for i in range(k):
    ta,ha,tb,hb=list(map(int,input().split()))
    m=0
    if ta!=tb:
        if ha<a and hb<a:
            m=a-ha+a-hb+abs(ta-tb)
        elif ha<a and hb>=a:
            m=hb-ha+abs(ta-tb)
        elif ha>b and hb>b:
            m=ha-b+hb-b+abs(ta-tb)
        elif ha>b and hb<=b:
            m=ha-hb+abs(ta-tb)
        else:
            m=abs(ha-hb)+abs(ta-tb)
    else:
        m=abs(ha-hb)
    print(m)