#P18217. The Emperor

The Emperor

The Emperor

注意:本题是 The Empress 的逆版本,两题的数据限制不同。

咖波发明了一种有趣的解释型语言 Push-Pop。解释器初始有一个容量无限的空栈,并从程序的第一条指令开始执行。这种语言只有以下两种指令。

POP a GOTO x; PUSH b GOTO y

如果栈非空且栈顶元素等于 aa,弹出栈顶元素,接下来执行第 xx 条指令;否则,把元素 bb 压入栈中,接下来执行第 yy 条指令。

HALT; PUSH b GOTO y

如果栈为空,执行完本条指令后整个程序停机;否则,把元素 bb 压入栈中,接下来执行第 yy 条指令。

咖波想升级自己的简易解释器,以处理更多的指令。给定一个最多包含 10241024 条指令的程序,请计算它在停机前一共执行了多少条指令。

输入格式

第一行包含整数 nn,表示程序的指令数量。

之后 nn 行,每行包含上述两种格式之一的一条指令。指令从 11 到 nn 编号。

输出格式

如果程序永远不会停机,输出 -1。

否则,输出程序执行的指令总数对 998244353998244353 取模的结果。使程序停机的那条指令也计入总数。

数据范围

  • 1≤n≤10241\le n\le1024;
  • 每条指令中,1≤a,b≤10241\le a,b\le1024,1≤x,y≤n1\le x,y\le n。

样例 1

输入:

1
HALT; PUSH 1 GOTO 1

输出:

1

样例 2

输入:

5
POP 1 GOTO 2; PUSH 1 GOTO 2
HALT; PUSH 1 GOTO 3
POP 1 GOTO 4; PUSH 2 GOTO 4
POP 1 GOTO 2; PUSH 2 GOTO 4
HALT; PUSH 99 GOTO 4

输出:

5

样例 3

输入:

1
POP 1 GOTO 1; PUSH 1 GOTO 1

输出:

-1

与 The Empress 相比,本题的主要区别是:指令数量上限为 10241024;程序可能永远不停机,此时输出 -1;对于会停机的程序,只需输出执行指令数对 998244353998244353 取模的结果。