Game

Time Limit: 1000 ms

Memory Limit: 65535 ms

Description

幼儿园的孩子们在玩一个游戏:游戏开始时每个人有100张卡片,每次老师可以点两个人的名字,甲 乙,那么乙要将自己卡片的一半(向下取整)给甲。问M次点名后每个人手上卡片的张数(M<=100000,人数<=10000,人名为长度<=10的字符串),按照第一次被点名的先后顺序输出。

Input

第一行输入一个整数M 下面M行每行两个字符串表示两个人名

Output

最后每个人手上的卡片数

Sample Input

5
gangbei  wuyao
shuiren  gangbei
xiaoxiao siqi
xiaoxiao shuiren
shuiren  xiaoxiao

Sample Output

75
50
206
119
50

Hint

Source


提交代码