Weighted KNN: Որքան մոտ, այնքան բարձր

Քաղաքի հրապարակում երաժշտական ճաշակի արագ հարցում է անցկացվում։ Դուք արդեն գիտեք, թե որոշ ունկնդիրներ որտեղ են կանգնած և ինչ երաժշտական ժանր են նախընտրում։ Երբ հայտարարվում է նոր դիրք, մոտակա ունկնդիրների կարծիքը պետք է ավելի մեծ կշիռ ունենա, քան հեռվում գտնվողներինը։

Ձեզանից պահանջվում է յուրաքանչյուր նոր դիրքի համար որոշել երաժշտական ժանրը՝ կիրառելով հեռավորությունից կախված կշռային քվեարկություն։ Որպես հեռավորություն օգտագործեք ուղիղ գծով (Էվկլիդյան L2) հեռավորությունը.

Դրա համար դուք պետք է՝

• Գտնեք k ամենամոտ հարևաններին։

• Հաշվեք յուրաքանչյուր ժանրի կշռված ձայները (բոլոր կշիռների գումարը)։

• Արտածեք ամենամեծ կշիռ ունեցողը։

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

Հաջորդ n տողերից յուրաքանչյուրը պարունակում է երկու իրական թիվ՝ x y, որոնց հաջորդում է ժանրի անվանումը (օրինակ՝ rock, pop կամ jazz)։ Այս տվյալները նկարագրում են մեկ ունկնդրի դիրքն ու նախընտրությունը։

Հաջորդ տողում տրված է k ամբողջ թիվը, որը ցույց է տալիս, թե քանի ամենամոտ ունկնդիր պետք է մասնակցի քվեարկությանը։

Հաջորդ տողում տրված է q ամբողջ թիվը՝ գնահատման ենթակա դիրքերի թիվը։

Վերջին q տողերից յուրաքանչյուրը պարունակում է երկու իրական թիվ՝ x y, որոնք ներկայացնում են գնահատվող դիրքի կոորդինատները։

Յուրաքանչյուր դիրքի համար գտեք ամենաբարձր կշռային ձայներ հավաքած ժանրը։ Եթե կշիռները հավասար լինեն, տպեք հավասար միավորներ հավաքած ժանրերից այբբենական կարգով ամենափոքրը։ Երաշխավորվում է, որ չկան կետեր, որոնք 0 հեռավորություն ունեն հարցվող դիրքից։