该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

凡家物语是 Minecraft 游戏的一个模组，添加了大量的村民社交与互动，包括但不限于跟所有村民交谈、送礼甚至是结婚生子，旨在创造属于自己的故事。每个村民都有自己的名字，且有独立的好感度，任何互动都将对好感度产生影响。

小码哥酷爱这个模组，在游戏里他不会放过任何一个村民，每每遇见都会交流互动一番，并将每一位村民的名字和好感度记录在册。不幸的是他开的和平难度，没有村民死亡，随着时间的推移，其数量越来越多，而且有的村民还和别人同名，这使得名册越来越臃肿，所以他急需你帮他维护这个名册。

他需要你实现 $4$ 种操作：

1. 如果遇到新的村民，记录其名字 $s_i$ 及好感度 $a_i$；
2. 修改一个家族所有人的好感度，即给定名字前缀 $p_i$ 的所有人的好感度变化 $d_i$；
3. 查询名字为 $s_j$ 的村民们的声望值的和（因为会有重名的）；
4. 查询一个家族所有人的好感度总和，即名字前缀为 $p_j$ 的好感度的和。

对于操作 2 和操作 4 ，如出现尚未记录在名册的名字前缀，那么进行的操作无效。

输入格式

第一行为一个整数 $N$，表示接下来有 $N$ 个操作；

接下来 $N$ 行，每行输入一个操作，行首为一个整数，表示这一行的操作的种类，这一行的操作和格式为：

1. 插入人名，这一行的格式为：1 $s_i$ $a_i$
2. 前缀修改声望，这一行的格式为：2 $p_i$ $d_i$
3. 查询名字的声望和，这一行的格式为：3 $s_j$
4. 查询前缀的声望和，这一行的格式为：4 $p_j$

其中：$0 \le N \le 10^5$；$|a_i|,|d_i| \le 10^3$

输入保证插入人名的字符串均为小写字母且长度和小于或等于 $10^5$，总的字符串的长度和小于或等于 $10^6$。

输出格式

对于每一次询问操作，在一行里面输出答案。

20
1 a -10
1 abcba -9
1 abcbacd 5
4 a
2 a 9
3 aadaa
3 abcbacd
4 a
3 a
2 a 10
3 a
2 a -2
2 d -8
1 ab -2
2 ab -7
1 aadaa -3
4 a
3 abcba
4 a
4 c

-14
0
14
13
-1
9
11
1
11
0