解题思路

本题的本质是求执行过程中，同时嵌套的有效 $O(n)$ 循环的最大层数。

一层循环若执行 $n$ 次，相当于在当前复杂度上乘一个 $n$。例如当前复杂度为 $n^{cur}$，再进入一层执行 $n$ 次的循环后，复杂度变为 $n^{cur}\times n=n^{cur+1}$，所以令 $cur+1$；常数次循环只乘一个常数，不影响指数。若某层循环一次也不执行，则它内部的代码也不会执行，因此这些内部循环都不能产生复杂度贡献。

由于 $END$ 总是结束最近的 $FOR$，使用栈模拟循环嵌套。维护 $cur$ 表示当前有效的 $O(n)$ 循环层数，$ans$ 表示最大的 $cur$，$bad$ 表示当前处于多少层不执行的循环中。

栈中用 $3$ 种状态表示当前 $FOR$：

题目内容

某巡检平台用脚本扫描数据。脚本有 $L$ 行，每行是下面两种之一（单词、变量、常数之间以空格分隔）：

• FOR x a b：进入一层循环，循环变量为小写字母 $x$，下界 $a$、上界 $b$ 均为闭区间。$a$、$b$ 各自要么是正整数，要么是规模符号 $n$。
• END：退出最近一层尚未退出的 FOR循环。

规模 $n$ 视为正无穷大，大于脚本里出现的任何正整数。

一层循环是否执行，以及它对复杂度的贡献，按下面规则判断（若某一外层循环不执行，则它内部的所有语句均不会执行，对复杂度不产生贡献）：

• $a$、$b$ 都是整数且 $a \le b$，或 $a$、$b$ 都是 $n$：该层循环执行常数次，对复杂度指数贡献 $0$；
• $a$ 为整数且 $b$ 为 $n$：该层循环执行$n$次，对复杂度指数贡献 $1$；
• $a$ 为 $n$ 且 $b$ 为整数，或 $a$、$b$ 都是整数且 $a > b$：该层循环一次也不执行，该层及其内部所有语句均不会执行。

对于脚本执行过程中的任意位置，设当前所有尚未结束且实际会执行的循环中，对复杂度指数贡献为 $1$ 的循环共有 $t$ 层，则当前位置的复杂度为 $n^t$。

整段脚本的复杂度指数 $w$，定义为整个脚本执行过程中出现过的最大 $t$，因此整段脚本的复杂度为 $n^w$。当 $w=0$ 时，复杂度记为 1。

例如，两层贡献为 $1$ 的循环互相嵌套时，复杂度为 $n^2$；而两个贡献为 $1$ 的循环先后执行、互不嵌套时，复杂度仍为 $n^1$。

脚本第一行会给出声明值，格式为 1 或 n^k（$k \ge 1$）。

仅当 FOR / END 无法一一配对时，脚本不合法。循环变量允许重复使用：例如先后或嵌套出现两个 FOR i a b，变量名 $i$ 仍然合法，按各自所在层照常计算复杂度。

合法且实际复杂度与声明一致，输出 Yes；合法但与声明不一致，输出 No；不合法输出 ERR。

输入描述

第一行两个内容：$L$ 和声明值（1 或 n^k）。

接下来 $L$ 行，为脚本正文。

约束

$1 \le L \le 100$

循环变量为单个小写字母

正整数在 $[1,100]$ 内

声明中若为 $n^k$，则 $1 \le k \le 8$

输出描述

输出一行：Yes、No 或 ERR。

样例1

输入

4 n^2
FOR i 1 n
FOR j 1 n
END
END

输出

Yes

说明

两层循环都是「从常数到 $n$」，且互相嵌套，因此同时执行时复杂度指数为 $2$，实际复杂度为 $n^2$，与声明一致。

样例2

输入

4 n^1
FOR i n 5
FOR j 1 n
END
END

输出

No

说明

外层下界为 $n$、上界为 $5$。由于 $n$ 充分大，因此外层循环一次也不执行，内部的循环也不会执行。

实际复杂度为 1，与声明的 n^1 不一致。

样例3

输入

8 n^2
FOR i 1 n
FOR j 1 n
END
FOR k 1 9
FOR p 1 n
END
END
END

输出

Yes

说明

FOR i 在最外层，对复杂度指数贡献 $1$。它内部有两段彼此不嵌套的循环结构：

• FOR j 1 n：对复杂度指数贡献 $1$，与外层 i 同时执行时，总指数为 $1+1=2$；
• FOR k 1 9：只执行常数次，对复杂度指数贡献 $0$；其内层 FOR p 1 n 对复杂度指数贡献 $1$，因此与外层 i 同时执行时，总指数为 $1+0+1=2$。

整个脚本执行过程中出现的最大复杂度指数为 $2$，因此实际复杂度为 $n^2$，与声明一致。

样例4

输入

4 n^2
FOR i 1 n
FOR i 1 n
END
END

输出

Yes

说明

内外两层都使用循环变量 $i$，这是合法的。两层都是从常数到 $n$，互相嵌套，同时执行时复杂度指数为 $2$，与声明 $n^2$ 一致。