对于正整数 $N$，函数 $F(N)$ 以一个符号串 $F$ 给出，符号串 $F$ 满足如下 BNF 表记 中 <expr> 符号的定义。

<expr> ::= <term> | <expr> "+" <term>
<term> ::= <factor> | <term> "*" <factor>
<factor> ::= "N" | "N^" <number> | "log(" <expr> ")" | "log(" <expr> ")^" <number> | "(" <expr> ")"
<number> ::= <non_zero_digit> | <non_zero_digit> <digit_string>
<digit_string> ::= <digit> | <digit> <digit_string>
<non_zero_digit> ::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
<digit> ::= "0" | <non_zero_digit>

每个记号含义如下：

• N：表示 $N$
• +：加法 $+$
• *：乘法 $\times$
• log：自然对数 $\log$
• (, )：括号，括号内的内容优先于加法 + 和乘法 * 计算
• ^：乘方运算符，优先级高于加法 + 和乘法 *

<number> 表示十进制整数，保证 1 \leq \text{<number>} \leq 10^9。其中 "log(" <expr> ")^" <number> 表示 $ \left(\log(\text{})\right)^{\text{}} $。

例如，下列字符串可以作为 <expr> 符号：

• N+log(N)*N
  • 表示 $N + \log(N) \times N$。
• N^1+N^2+log(N)+log(N)^1000000000
  • 表示 $N^1 + N^2 + \log(N) + (\log(N))^{1000000000}$。
• N*(N+(log(N+N)^2*N))+(((N)))
  • 表示 $N \times (N + (\log(N+N))^2 \times N)+(((N)))$。
• (log((N)))
  • 表示 $(\log((N)))$。

相反，下列字符串不是 <expr> 符号：

• (log(N)+N)^2
  • 在 <factor> 内不允许 "(" <expr> ")^" <number> 形式。
• (log(N))^2
• (N
• )N(
• N^1000000001
• N^02
• N^0
• N^N
• 2
• log(3)
• N-log(N)
• log(N)/N

对于某些正整数 $N$，$F(N)$ 未必有定义，但对于任意输入，总存在某个正整数 $N_0$，使得对所有 $N \geq N_0$ 的正整数，$F(N)$ 都有定义。

令极限

[
\lim_{N \to \infty} \frac{F(N)}{N^a (\log N)^b}
]

能够收敛于有限值（包括 $0$）的所有非负整数对 $(a,b)$ 的集合记为 $S$。请输出 $S$ 的字典序最小的对。

即，假设非负整数对 $(a, b)$ 属于 $S$，并且对于任意 $(a', b') \in S$，满足如下之一：

• $a < a'$
• $a = a'$ 且 $b \le b'$

则 $(a, b)$ 是 $S$ 的字典序最小对。

可以证明 $S$ 非空且其字典序最小的对存在。

输入通过标准输入给出：

$F$

请输出 $S$ 的字典序最小的对 $(a, b)$，以空格分隔。

部分分

• 对于附加约束“$F$ 不包含部分字符串 log”的数据集，若正确解答，则可获得 $30$ 分。

样例解释 1

$F(N) = N \times \log(N^2) \times \log(N) + N + (\log(N^1+N))^2 \times N$。

此时使得极限收敛到有限值的非负整数对 $(a, b)$ 包括 $(1, 2), (1, 3), (2, 0)$ 等。极限如下：

[
\lim_{N \to \infty} \frac{F(N)}{N^1 (\log N)^2} = 3
]

[
\lim_{N \to \infty} \frac{F(N)}{N^1 (\log N)^3} = 0
]

[
\lim_{N \to \infty} \frac{F(N)}{N^2 (\log N)^0} = 0
]

这里 $0$ 也算收敛到有限值。对于 $(a, b) = (1, 1)$，有：

[
\lim_{N \to \infty} \frac{F(N)}{N^1 (\log N)^1} = \infty
]

即不收敛。

因此 $S$ 字典序最小的是 $(a, b) = (1, 2)$。本组数据不满足部分分约束。

样例解释 2

$F(N) = N \times \log(\log(N))$，对于 $(a, b) = (1, 1)$，

[
\lim_{N \to \infty} \frac{F(N)}{N^1 (\log N)^1} = 0
]

极限收敛。此时 $S$ 的字典序最小对为 $(a, b) = (1, 1)$。本组数据不满足部分分约束。

样例解释 3

$F(N) = \left(((N))\times N^{234567890}+N^2\right)$。本组数据满足部分分约束。

数据范围

• $F(N)$ 表达式为题目中给出的 BNF 记法 <expr> 符号的字符串
• $1 \leq |F| \leq 10^5$

由 ChatGPT 5 翻译