备受喜爱的编程语言 Fygon 发布了新版本!全新的 Fygon 2.0 仍然只有两条语句。第一条语句是 lag。它几乎可以替代任何其他语句。第二条语句是 for 循环:
for <variable> in range(<from>, <to>):
<body>for循环使<variable>从<from>迭代到<to>,且包含这两个端点。- 如果
<from>大于<to>,则<body>不会执行。 <variable>是从a到z的小写字母,但不能是n,n是在给定代码片段之前定义的变量。<from>和<to>可以等于外层循环中定义的任何变量。此外,<from>可以是1,<to>可以是n。- 循环的
<body>缩进四个空格,并至少包含一条语句。
如果你熟悉 Fygon 1.0,你会注意到,秉承最佳编程实践的精神,Fygon 2.0 不向后兼容,因为 range 函数现在需要两个参数。
新版本的性能得到了显著提升,因此你可以编写更多嵌套的 for 循环。这就是为什么我们不再关心操作的确切次数,而是关心程序的渐进复杂度。为简单起见,所有的 for 循环都嵌套在一条链中,并且恰好有一个 lag 语句位于所有 for 循环内部。所有循环变量各不相同,且都不等于 n。
设 $f(n)$ 为给定 Fygon 程序执行的 lag 操作次数,它是 $n$ 的函数。对于非负整数 $k$ 和正有理数 $C$,如果满足以下条件,我们称 $C \cdot n^k$ 为该程序的渐进复杂度:
$$\lim_{n \to \infty} \frac{f(n)}{C \cdot n^k} = 1$$
给定一个 Fygon 2.0 程序,求其渐进复杂度。
输入格式
输入的第一行包含一个整数 $m$ —— Fygon 2.0 程序的行数。接下来的 $m$ 行包含程序本身。程序至少包含 1 个,至多包含 20 个 for 语句。每个 for 语句包含一个嵌套的 for 语句或 lag 语句。
输出格式
输出数字 $k$ 和 $C$。$C$ 应以不可约分数 $p/q$ 的形式输出,其中 $p$ 和 $q$ 互质。
样例
输入 1
4
for i in range(1, n):
for j in range(1, i):
for k in range(j, n):
lag输出 1
3 1/3