Source : 长沙雅礼中学
Description

小明正在学习一种新的编程语言B++,刚学会结构体的他激动地写了好多程序并给出了他自己算出的空间复杂度,可他的编程老师实在不想一个一个检查小明的程序,于是你的机会来了!下面请你编写程序来判断小明对他的每个程序给出的空间复杂度是否正确。

B++语言的结构体如下:

\begin{matrix}S & a \\ & & b &c \\ E \end{matrix}

其中S表示声明一个结构体,a表示结构体的名字,b表示另外一个结构体的名字,c表示b的维度。

然后会有一行单行的E表示结构体声明结束。

一开始会有一个标准型i占用O(1)的空间,我们自动认为,声明一个结构体就会占用它所需的空间。

比如node会占用O(n2)的空间,那么edge会占用o(n4)的空间,所以这段代码最后占用O(n4)的空间,此处假设n远远大于常数。

现在给你一段共有L行的代码,需要你输出它的空间复杂度。

Input

单组数据,总共L行代码,每行代码都如同上面的形式,保证没有B++语法错误。

Output

输出一行O(n^w),注意w=0时输出O(1),w=1时输出O(n)。

Sample Input 1
S xsc
	i [n][666][n]
E
S orz
	xsc [2333][n][n]
	i [n][n][n][23333]
E
S chuyu
	i [888]
E
Sample Output 1
O(n^4)
Sample Input 2
S a
	i [123][456][789]
E
S b
	a [123][456][789]
E
Sample Output 2
O(1)
Hint

数据范围

对于所有数据L<=1000。

保证每个结构体名字长度不超过20且全为小写字母,并且声明的[ ]个数不超过20(且里面的常量大小不超过109且不为0),保证声明结构体中使用的类型在之前一定存在,并不会重复声明。

对于30%的数据,不存在结构体嵌套的情况且保证结构体名字长度为1。

对于60%的数据,每个结构体里仅存在一个类型。

对于100%的数据,不存在特殊限制。