Փրկի՛ր Սուրբ Ծնունդը
Սանտան կորցրել է նամակներով պարկը, բայց հիշում է մի պարզ կանոն. նույն թաղամասի հինգ հարևան տներ, որպես կանոն, նույնանման նվերներ են ուզում։ Նա գիտի որոշ տների գտնվելու վայրը և թե նրանցից յուրաքանչյուրն ինչ նվեր է խնդրել։ Յուրաքանչյուր վայրի համար, որտեղ նա կարող է հայտնվել, օգնե՛ք նրան գուշակել նվերը՝ Սուրբ Ծնունդը փրկելու համար։ Օգտագործե՛ք քաղաքային թաղամասերի (Manhattan) հեռավորությամբ հաշվարկված հինգ ամենամոտ հայտնի տները՝ կանխատեսելու համար, թե ինչ նվեր են ամենայն հավանականությամբ ցանկանում երեխաները։
Մուտքի առաջին տողում տրված է n ամբողջ թիվը՝ հայտնի տների քանակը։
Հաջորդ n տողերից յուրաքանչյուրը պարունակում է երկու իրական թիվ՝ x y, որոնց հաջորդում է մեկ բառ՝ նվերի անունը (առանց բացատների)։ Այս տվյալները նկարագրում են մեկ տան գտնվելու վայրը և նվերը։
Հաջորդ տողում տրված է q ամբողջ թիվը՝ վայրէջքի հնարավոր կետերի քանակը։
Հաջորդ q տողերից յուրաքանչյուրը պարունակում է երկու իրական թիվ՝ x y, որոնք Սանտայի վայրէջքի կետի կոորդինատներն են։
Յուրաքանչյուր վայրէջքի կետի համար կանխատեսե՛ք ամենահավանական նվերը՝ օգտագործելով քաղաքային թաղամասերի (Manhattan) հեռավորությամբ հաշվարկված հինգ ամենամոտ տները։ Եթե կան մի քանի հավասարապես հավանական նվերներ, տպե՛ք դրանցից այբբենական կարգով ամենափոքրը։ Եթե հինգ ամենամոտ տներն ընտրելիս մի քանի տներ ունեն նույն սահմանային հեռավորությունը, նախապատվությունը տվեք նրանց, որոնք մուտքային տվյալներում ավելի շուտ են հանդիպում։
Մուտք | Ելք |
|---|---|
7 | toys |
6 | blocks |
8 | books |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB