HZNUOJ

KK与卡牌

Tags:
Time Limit:  1 s      Memory Limit:   256 MB
Submission:574     AC:30     Score:96.65

Description

在全新的卡牌世界里,每一张卡牌都代表了一个英雄,英雄有自己的名字s和武力值w,英雄的名字是一个字符串,武力值是一个浮点数,武力值越高,则代表英雄的武力越强,而在武力相同的情况下,名字的字典序越靠前,则能力越强。

kk拥有$n$张卡牌,而bm有$q$张卡牌,kk想知道对于bm的每一张卡牌,自己的$n$张卡牌中总共有几张卡牌能够战胜他,战胜的条件则是能力值比他高,或者在能力值相同的情况下英雄名字的字典序比他靠前,如果能力值和名字完全一样,则平手。


字典序的定义在下方的hint中。

Input

单组测试样例。
第一行是一个$n$,代表kk拥有$n$张卡牌。
接下来有$n$行,每行有一个字符串$s$,和一个浮点数$w$。
第$n+2$行是一个$q$,代表bm拥有$q$张卡牌。
接下来有$q$行,每行有一个字符串$s$,和一个浮点数$w$。
($s$ 和 $w$的含义如题目中描述,$(1 \leq n, q\leq 100000)$,$(1 \leq length(s)\leq 5)$,名字均为小写字母$(1 \leq w \leq 100)$,且$w$均为1位小数)

Output

对于bm的每张卡牌,都输出一个整数,代表kk的卡牌中,能打败bm的卡牌的数量,若没有能打败bm的卡牌,则输出$0$。

Samples

input
5 tom 3.5 joe 1.0 jark 2.1 emily 1.5 kk 1.2 4 kk 1.2 kk 1.6 aa 0.9 aa 2.2
output
3 2 5 1

Hint

名字可能会有重复。

不建议用c++的cin和cout做读入和输出,可能会导致超时。

字典序定义

按照第一个字母、以 a、b、c……z 的顺序排列;如果第一个字母一样,那么比较第二个、第三个乃至后面的字母。如果比到最后两个单词不一样长(比如,sigh 和 sight),那么把短者排在前。(来自百度百科)

Author

YU, Saikang