Հետևիր զույգին

Ճանապարհորդ բլոգերը քաղաքի քարտեզի վրա նշում է հայտնի վայրերը։ Յուրաքանչյուր վայր ունի պիտակ, օրինակ՝ ռամեն, տակո կամ պիցցա։ Երբ բլոգերը հայտնվում է նոր վայրում, նա հարցնում է իրեն ամենամոտ գտնվող երեք տեղացիներին։ Եթե երկրորդ և երրորդ ամենամոտ գտնվողների կարծիքները համընկնում են, բայց տարբերվում են ամենամոտի կարծիքից, բլոգերը վստահում է զույգին։ Հակառակ դեպքում կիրառվում է 3-ամենամոտ հարևանների (3-nearest-neighbors) սովորական քվեարկությունը։ Հեռավորությունները հաշվարկվում են ուղիղ գծով՝ Էվկլիդեսյան (L2) հեռավորությամբ։

Մուտքի առաջին տողում տրված է n ամբողջ թիվը՝ հայտնի վայրերի քանակը։

Հաջորդ n տողերից յուրաքանչյուրում տրված են երկու իրական թիվ x y և դրանց հաջորդող պիտակը։

Այնուհետև տրված է q ամբողջ թիվը՝ ստուգվելիք վայրերի քանակը։
Վերջին q տողերից յուրաքանչյուրում տրված են երկու իրական թիվ x y՝ բլոգերի գտնվելու վայրի կոորդինատները։

Յուրաքանչյուր վայրի համար ծրագիրը պետք է տպի այն վայրի պիտակը, ուր բլոգերը կգնա։ Եթե հարևաններ ընտրելիս հեռավորությունները համընկնում են, պետք է ընտրել այն վայրը, որը մուտքային տվյալներում ավելի շուտ է նշված։ Եթե 2-րդ և 3-րդ հարևանների պիտակները նույնն են, բայց տարբերվում են 1-ին հարևանի պիտակից, ապա պետք է տպել նրանց ընդհանուր պիտակը։ Հակառակ դեպքում պետք է տպել այն պիտակը, որն ամենահաճախն է հանդիպում երեք հարևանների մեջ։ Եթե քվեները հավասար են, տպել այբբենական կարգով ամենափոքր պիտակը։