OI题库

【题目描述】

wikipedia上提供的一段背景资料：“集合理论是数学理沦的一个分支，它主要由德国数学家Georg cantor在19世纪末创立。集合理论已经逐渐成为现代数学的基本理论。正式的集合理论学说为数学证明的严格性提供了保障。”

一些古怪的理论工作者开始构造一个超级计算机，用来实现集合之间的操作，而不再是数字之间的操作。他们希望你来帮他们模拟一下集合运算的过程。

计算机的操作对象是一个以集合为元素的栈，一开始这个栈是空的。在每一步操作之后，栈顶集合中所含元素的个数是需要你输出的东西。计算机的操作指令有PUSH，DUP，UNION，INTERSECT，ADD。

·PUSH操作将一个空集合{}入栈

·DUP操作将把一个和栈顶元素相同的集合入栈

·UNION操作进行两次出栈操作，并且把出栈的两个集合的并入栈

·INTERSECT操作进行两次出栈操作，并且把出栈的两个集合的交入栈

·ADD操作进行两次出栈操作，并且把第一个出栈的集合作为一个元素，放入第二个出栈的集合中，然后把这个结果入栈

举一个例子，假设栈顶的元素是A={{}，{{}}}，而它下面的一个元素是B={{}，{{{}}}}。

显然，集合A有2个元素，集弁B也是。对于这个情况：

·UNION操作会产生集合{{}，{{}}，{{{}}}}，这个集合有3个元素，所以要输出3

·INTERSECT操作会产生{{}}，所以要输出1

·ADD操作会产生{{}，{{{}}}，{{}，{{}}}}，所以要输出3

【输入格式】

第一行一个整数N，保证0≤N≤2000。

接着的N行，每行有一条指令。保证输入的指令是合法的，不会出现让你在一个空的栈中弹出元素的情况。

【输出格式】

对于输入中的每一条指令，输出执行指令之后栈顶集合里的元素个数。

【样例输入】

9
PUSH
DUP
ADD
PUSH
ADD
DUP
ADD
DUP
UNION

【样例输出】

0
0
1
0
1
1
2
2
2