装备合成

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

小白很喜欢玩儿LOL,但是无奈自己是个坑货,特别是在装备的选择和合成上,总是站在泉水里为选装备而浪费时间。现在小白试图解决这个问题,为了使问题简单化,我们把游戏中的装备合成规则简化如下:

(1)装备的合成关系构成一棵合成关系树,如图(a)所示,装备的下级装备叫合成小件,直接连接的叫直接合成小件;上级装备叫合成件,直接连接的叫直接合成件。合成树上的每件装备都可以直接购买,如果钱不够也可以先购买这个装备的合成小件。

(2)每个装备都有一个合成价格和一个总价格,装备的总价格=该装备的合成价格+该装备所有直接合成小件的总价格之和(图(a)关系树上面显示的数字就是对应装备的总价格)。

(3)初始的时候(未拥有装备的任何部分),装备的当前价格等于总价格,当前价格会随着购买的小件而发生相应的变化。

(4)如果购买了某个装备,那么它所有上级可合成装备的当前价格都会相应地减少,减少的量等于这个装备的当前价格。

(5)如果购买了某个装备,那么它下级所有合成小件都会被购买,也就是说,这些小件都变成已拥有的状态,但是物品栏里只有最终合成的装备,因为是小件合成了这件装备。

(6)我们认为关系树上的每个装备的直接合成小件都不超过2件,关系树上同一件物品只会出现一次,我们也不考虑物品的出售问题,我们假设物品栏容量无限,金钱无限。

现在问题来了,按照格式给定一棵合成关系树,再给定一系列操作,完成相应的查询,具体格式见输入。

Input

多组输入,对于每组数据:

第一行有两个整数n m,分别代表关系树中物品的数量和后续的操作数。(1 <= n,m <= 10^4)

接下来的n行,每行对应一件物品的描述,格式为equipment p k,分别代表装备的名称,合成价格,直接合成小件的个数,然后有k个合成小件的名称synthesis1 synthesis2 ... synthesisk。(1 <= p <=10^4 , k <= 2 , 所有物品名称只包含小写英文字母,长度不超过20)

接下来的m行,每行对应一个操作,格式如下:

(1)B equipment ,表示物品equipment被购买。

(2)Q equipment ,表示要查询物品equipment的当前价格。

其中equipment代表物品的名称,保证合法且存在于合成关系树中。

注意:如果B指令购买的装备是当前已经拥有的装备(包括小件),那么忽略该条B购买指令。特别地,如果你已经拥有某件装备,那么查询该物品的当前价格时应该输出这件物品的总价格而不是0

Output

对于每次Q查询指令,输出一个整数,代表查询的物品的当前价格。

Sample Input

8 10
bannerofcommand 600 2 aegisofthelegion fiendishcodex
aegisofthelegion 400 2 nullmagicmantle crystallinebracer
fiendishcodex 465 1 amplifyingtome
nullmagicmantle 450 0
crystallinebracer 100 2 rubycrystal rejuvenationbead
amplifyingtome 435 0
rubycrystal 400 0
rejuvenationbead 150 0
B crystallinebracer
Q fiendishcodex
Q bannerofcommand
B nullmagicmantle
Q aegisofthelegion
B aegisofthelegion
Q bannerofcommand
Q crystallinebracer
B bannerofcommand
Q bannerofcommand

Sample Output

900
2350
400
1500
650
3000

Hint

Source

“师创杯”山东理工大学第八届ACM程序设计竞赛