完美配对

• 时间限制：每个测试点 3 秒
• 内存限制：1024 MB
• 输入：标准输入
• 输出：标准输出

题目描述

在芭比的世界里，任何一对芭比与肯都必须是完美的，因为没有什么比完美更美好了。但并不是所有人都有幸找到伴侣，因此创立了“完美伴侣搜寻俱乐部”。

为了简化寻找伴侣的过程，每一位新成员都需要先完成一份问卷。之后，根据问卷的回答，每位芭比和每位肯都会获得一个代表其类型的字符串。这个字符串会被张贴在俱乐部的公告板上，任何人都可以前来查看并寻找合适的伴侣。

不幸的是，没有人愿意把这些特殊的字符串翻译成更易理解的属性，于是人们开始这样选择伴侣：将芭比的字符串和肯的字符串拼接起来，如果拼接后的字符串是回文串，那么这对组合就被认为是完美的——因为没有什么字符串比回文串更完美了。

为了统计可能存在的完美配对数量，俱乐部决定在每次更新公告板后输出当前能组成多少对完美配对。公告板有两个区域：一个是存放肯的字符串的区域，另一个是存放芭比的字符串的区域。初始时板上没有任何字符串。每当有人完成测试，其结果就会被添加到公告板上。有时，某位会员找到了伴侣（无论是俱乐部内还是俱乐部外），那么他的字符串就会从公告板上移除。

对于公告板的每一次更新，输出当前可组成的完美配对数量。

输入格式

第一行包含一个整数 $t$ —— 公告板更新的次数（$1 \le t \le 10^6$）。

接下来的 $t$ 行每行描述一次更新，格式如下：

• 1 + b ：一位芭比加入俱乐部，测试结果为字符串 $b$。
• 1 - b ：一位字符串为 $b$ 的芭比找到了伴侣并离开俱乐部。数据保证该字符串当前在公告板上。
• 2 + k ：一位肯加入俱乐部，测试结果为字符串 $k$。
• 2 - k ：一位字符串为 $k$ 的肯找到了伴侣并离开俱乐部。数据保证该字符串当前在公告板上。

保证所有第一种和第三种操作（即新增字符串）中字符串的总长度不超过 $5 \times 10^6$。

输出格式

每行输出一个整数，表示每次更新后当前可组成的完美配对数量。

样例

输入

6
1 + ken
2 + nek
1 + barbie
2 + ibrab
1 - ken
1 - barbie

输出

0
1
1
2
1
0