• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

رادزینکا دوبرامیل ویچشسلافوویچ (Rodzyanko Dobromil Vyacheslavovich) که فردی تنبل و طماع است، میخواهد به خانه‌ی مادربزرگش برود. رادزینکا در شهر استاوروپل زندگی میکند و مادربزرگ او در چیرکیسک میزید. روسیه به شکل یک جدول خیلی بزرگ است(روسیه کشور بزرگی است). سطرها و ستون‌های جدول با اعداد صحیح شماره گذاری شده است و خانه‌ی واقع در سطر i و ستون j را (i, j) مینامیم. استاوروپل در خانه (0, 0) این جدول وجود دارد و چیرکیسک در (x, y) است. رادزینکا در هر مرحله میتواند به خانه‌‌هایی که مجاور ضلعی خانه‌ی فعلی خود در جدول است، برود. در روسیه رشته کوه های بسیاری وجود دارد که در جدول به شکل مستطیل‌هایی موازی با سطر و ستون‌های جدول است. هیچ دو رشته کوهی با هم تقاطع نداشته و حتی مماس هم نیستند. به دلیل سرمای زیاد رادزینکا نمیتواند به کوهستان وارد شود. شما باید به رادزینکا کمک کنید تا طول کوتاه‌ترین مسیر از استاوروپل به چیرکسیک را بیابد.

ورودی

در سطر اول ورودی دو عدد $x$ و $y$ آمده است که نمایانگر موقعیت چیرکیسک در جدول است در سطر دوم عدد $n$ آمده که برابر تعداد رشته کوه‌ها(مستطیل‌ها) است. سپس در $n$ سطر بعدی در هر سطر چهار عدد $x_1$ و $y_1$ و $x_2$ و $y_2$ که نشان دهنده‌ی دو راس مقابل به هم مستطیل(رشته کوه) است. $$1 \le n \le 100\ 000$$ $$1 \le x, x_1, x_2 \le 1\ 000\ 000$$ $$-1\ 000\ 000 \le y, y_1, y_2 \le 1\ 000\ 000$$

خروجی

در سطر اول خروجی طول کوتاه‌ترین مسیر باید چاپ شود.

مثال

ورودی نمونه ۱

9 1
2
5 -3 8 3
10 -3 13 3

خروجی نمونه ۱

16

ورودی نمونه ۲

12 0
5
2 -1 3 1
6 -7 8 -1
6 1 8 6
4 3 4 5
10 -5 10 3

خروجی نمونه ۲

24