SPOJ in Armenian

Անվերջ քաղաքը անվերջ քանակով հարավ-հյուսիսային և արևմուտք-արևելյան փողոցներով տրոհված է միավոր քառակուսի բլոկների։ Հարավ-հյուսիսային փողոցներից մեկը նշված է 0 համարով, և դեպի արևելք փողոցների համարները աճում են, իսկ դեպի արևմուտք՝ նվազում։ Նմանապես, արևմուտք-արևելյան փողոցներից մեկը նշված է 0 համարով, և դեպի հյուսիս համարները աճում են, իսկ դեպի հարավ՝ նվազում։ Յուրաքանչյուր խաչմերուկ նշված է այն փողոցների համարների կարգավորված զույգով (առաջինը հարավ-հյուսիսային փողոցի համարն է), որոնք հատվում են այդտեղ։ Որոշ փողոցների հատվածներ ավելի կարևոր են և կոչվում են գլխավոր փողոցներ։

Մի օր շերիֆ Վոլֆը շրջում էր քաղաքում և (A,B) խաչմերուկում նկատեց մի մեքենա, որում նստած էին լավ հայտնի ԱՐՋ ավազակախմբի մի քանի անդամներ։ Վոլֆը իմացավ, որ “արջերը” պլանավորում են կողոպտել Մեղրի Պահեստը, որ գտնվում է (0, 0) խաչմերուկում և որոշեց կանգնեցնել նրանց։

Քանի դեռ նրանք ոչ մի հանցանք չեն գործել, Վոլֆը չի կարող ձերբակալել նրանց։ Բայց նա կարող է իր մեքենան կանգնեցնել ցանկացած խաչմերուկում և փակել այդ խաչմերուկում հատվող չորս միավոր հատվածներից ճիշտ մեկը։ Սակայն նա չի կարող փակել գլխավոր փողոցներին պատկանող միավոր հատվածները։

Այսպիսով, Վոլֆը որոշում է հետապնդել “արջերին”, և մինչ նրանք հասնեն խաչմերուկի, նա կարող է առաջ անցնել նրանց մեքենայից և փակել խաչմերուկի չորս միավոր հատվածներից մեկը։ “Արջերը” կկարողանան մտնել խաչմերուկ, բայց նրանք չեն կարող խաչմերուկից դուրս գալ այն ուղղությամբ, որը փակել է շերիֆի մեքենան։

Շերիֆը ցանկանում է “արջերին” Մեղրի Պահեստից որքան հնարավոր է հեռու պահել։ Գտեք D մեծագույն հեռավորությունը՝ այնպիսին, որ “արջերի” համար հասանելի բոլոր (x,y) խաչմերուկները բավարարեն max(|x|, |y|) ≤ D պայմանին։

Մուտքը

Առաջին տողում տրված են երկու ամբողջ A և B (|A| ≤ 10⁶, |B| ≤ 10⁶) թվեր - արջերի սկզբնական կետը։ Երկրորդ տողում տրված է հիմնական փողոցների N (0 ≤ N ≤ 500) քանանկը։ Հաջորդ N տողերից յուրաքանչյուրը պարունակում է չորս ամբողջ թվեր.  X1, Y1, X2, Y2 (|Xi| ≤ 10⁶, |Yi| ≤ 10⁶), նշանակում է (X1, Y1) և (X2, Y2) խաչմերուկների միջև ընկած փողոցը գլխավոր փողոց է։ Կամ X1 = X2, կամ Y1 = Y2 :

Ելքը

Ելքում պետք է արտածել մի թիվ՝ D-ի մեծագույն արժեքը։

Օրինակ

Մուտքը.
3 3
3
1 0 3 0
0 0 0 3
3 0 3 1


Ելքը.
1

Հետևյալ նկարը ցույց  է տալիս, թե ինչպես են կարող “արջերը” պահեստին մոտենալ մինչև մեկ միավոր հեռավորության վրա։

Բայց նրանք ինչպես էլ փորձեն, շերիֆը միշտ կարող է նրանց խանգարել պահեստին ավելի մոտենալու համար։