Մեքենայական ուսուցում

Ըմբոստ հացի փուռ

Մի ըմբոստ հացի փուռ ցանկանում է տարբերվել իր հարևաններից։ Յուրաքանչյուր հարևան հացի փուռ ունի պիտակ, որը ցույց է տալիս, թե ինչ համի թխվածք է սովորաբար պատրաստում - երկուսից մեկ համը: sweet կամ salty։ Ցանկացած նոր վայր դիտարկելիս, հացի փուռը նախ գտնում է k հարևանների համերը՝ հիմնվելով նրանց գտնվելու վայրերի միջև եղած ուղիղ գծով (Էվկլիդյան L2) հեռավորության վրա, ապա ընտրում է հակառակ համը։

Մուտքի առաջին տողում տրված է մեկ ամբողջ թիվ n որը ներկայացնում է հայտնի հացի փռերի քանակը։ Հաջորդ n տողերից յուրաքանչյուրը պարունակում է երկու իրական թիվ x y որին հաջորդում է տվյալ վայրի համը՝ կամ sweet կամ salty։

Հաջորդ տողում տրված է մեկ ամբողջ թիվ k։

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

Յուրաքանչյուր վայրի համար տպեք այն համը, որը հացի փուռը կընտրի տվյալ վայրի համար։ Եթե կան մի քանի հարևաններ՝ նույն հեռավորությամբ, պետք է ընտրել նրանց, որոնք մուտքային տվյալներում ավելի վաղ են նշված։

Մուտք

Ելք

4
0 0 sweet
2 0 salty
0 2 salty
-1 -1 sweet
1
sweet salty
3
0.9 0.1
1.1 0
1.5 0.2

salty
sweet
sweet

5
0 0 sweet
2 0 salty
0 2 salty
-1 -1 sweet
3 3 sweet
3
sweet salty
2
1 1
2.4 0.1

sweet
salty

4
0 0 sweet
2 0 salty
0 2 salty
2 2 sweet
2
salty sweet
2
1 0.1
1 1.9

sweet
sweet

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue