問題文

正の整数 N についての関数 F(N) が次の BNF 表記 の <expr> シンボルに従う文字列 F として与えられます。

<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 以上 10^9 以下であることが保証されます。また、 "log(" <expr> ")^" <number> は (\log( \text{<expr>} ))^{ \text{<number>} } を表すものとします。

例えば、以下の文字列は <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 を満たす全ての正の整数 N で F(N) が定義されることが証明できます。

そこで、極限

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

が有限の値（ 0 を含む）に収束するような非負整数の組 (a, b) 全体の集合を S とします。 S の辞書順最小の組を出力してください。

ただし、非負整数の組 (a, b) が S の辞書順最小の組であるとは、 (a, b) が S に属し、さらに S に属する任意の組 (a', b') について次のいずれかが成り立つこととします。

• a < a'
• a = a' かつ b \le b'

ここで、 S は空集合でなく、さらに S の辞書順最小の組が存在することが証明されます。

制約

• 関数 F(N) は問題文に示した BNF 記法の <expr> シンボルに従う文字列 F として与えられる
• 1 \leq |F| \leq 10^5

部分点

• 追加の制約「F は部分文字列として log を含まない」を満たすデータセットに正解した場合は 30 点が与えられる。

入力例 1

N*log(N^2)*log(N)+N+log(N^1+N)^2*N

出力例 1

1 2

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

このとき、問題文に示した極限が有限の値に収束するような非負整数の組 (a, b) は (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

N*log(log(N))

出力例 2

1 1

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

(((N))*N^234567890+N^2)

出力例 3

234567891 0

F(N) = \left(((N))\times N^{234567890}+N^2\right) です。このケースは部分点の制約を満たしています。