Մանհեթենյան հեռավորություն (L1 հեռավորություն)
Պատկերացրեք, որ զբոսնում եք Մանհեթենում։ Փողոցները ձգվում են հյուսիսից-հարավ և արևելքից-արևմուտք, ուստի դուք կարող եք շարժվել միայն ուղղահայաց կամ հորիզոնական ուղղություններով։ Երկու խաչմերուկների միջև հեռավորությունը հորիզոնական և ուղղահայաց ուղղություններով անցած թաղամասերի քանակների գումարն է։ Դուք չեք կարող անկյունագծով անցնել շենքերի միջով։
«Քաղաքային թաղամասերով» շարժվելու այս գաղափարը սահմանում է Մանհեթենյան հեռավորությունը (որը նաև անվանում են L1 հեռավորություն կամ տաքսու հեռավորություն)।
Երկչափ համակարգում գտնվող և կետերի համար Մանհեթենյան հեռավորությունը հաշվվում է հետևյալ բանաձևով․
Տաքսու թաղամասեր
Ցանցաձև կառուցվածք ունեցող քաղաքում տաքսին պետք է ընտրի ամենամոտ կանգառը՝ հաշվի առնելով թաղամասային հեռավորությունը։ Հայտնի են բոլոր կանգառների կոորդինատներն ու անունները։ Յուրաքանչյուր պատվերի վայրի համար պետք է գտնել Մանհեթենյան հեռավորությամբ ամենամոտ կանգառը և տաքսին ուղարկել այնտեղ।
Մուտքի առաջին տողում տրված է n ամբողջ թիվը՝ տաքսու կանգառների քանակը։
Հաջորդ n տողերից յուրաքանչյուրում տրված են երկու իրական թիվ՝ x և y, որոնց հաջորդում է կանգառի անունը (մեկ բառ՝ առանց բացատների)։ Այս տվյալները նկարագրում են կանգառի դիրքն ու անունը։
Այնուհետև հաջորդ տողում տրված է q ամբողջ թիվը՝ պատվերների վայրերի քանակը։
Վերջին q տողներից յուրաքանչյուրում տրված են երկու իրական թիվ՝ x և y, որոնք նկարագրում են պատվերի վայրը։
Յուրաքանչյուր պատվերի վայրի համար պետք է տպել ամենամոտ կանգառի անունը՝ օգտագործելով Մանհեթենյան (L1) հեռավորությունը՝ |x - xi| + |y - yi|։ Եթե մի քանի կանգառներ գտնվում են նույն նվազագույն հեռավորության վրա, ապա պետք է տպել այն կանգառի անունը, որը մուտքային տվյալներում ավելի շուտ է հանդիպել։
Մուտք | Ելք |
|---|---|
4 | central |
3 | west |
2 | alpha |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB