AT_ttpc2023_f N^a (log N)^b

正の整数 $ N $ についての関数 $ F(N) $ が次の [BNF 表記](https://ja.wikipedia.org/wiki/%E3%83%90%E3%83%83%E3%82%AB%E3%82%B9%E3%83%BB%E3%83%8A%E3%82%A6%E3%82%A2%E8%A8%98%E6%B3%95) の `` シンボルに従う文字列 $ F $ として与えられます。 ``` ::= | "+" ::= | "*" ::= "N" | "N^" | "log(" ")" | "log(" ")^" | "(" ")" ::= | ::= | ::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ::= "0" | ``` 記号はそれぞれ以下の意味を表します。 - `N` : $ N $ - `+` : 足し算 $ + $ - `*` : 掛け算 $ \times $ - `log` : 自然対数 $ \log $ - `(`, `)` : 括弧、ただし足し算 `+` や掛け算 `*` よりも先に計算される - `^` : 累乗、ただし足し算 `+` や掛け算 `*` よりも先に計算される `` は十進表記の整数を表し、 $ 1 $ 以上 $ 10^9 $ 以下であることが保証されます。また、 `"log(" ")^" ` は $ (\log( \text{} ))^{ \text{} } $ を表すものとします。 例えば、以下の文字列は `` シンボルになり得ます。 - `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))) $ を表します。 また、以下の文字列は `` シンボルになり得ません。 - `(log(N)+N)^2` - `` において、 `"(" ")^" ` は使われません。 - `(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 $

$ S $ の辞書順最小の組 $ (a, b) $ を空白区切りで出力せよ。

### 部分点 - 追加の制約「 $ F $ は部分文字列として `log` を含まない」を満たすデータセットに正解した場合は $ 30 $ 点が与えられる。 ### Sample Explanation 1 $ 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) $ が辞書順最小であることが示せます。このケースは部分点の制約を満たしていません。 ### Sample Explanation 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) $ が辞書順最小であることが示せます。このケースは部分点の制約を満たしていません。 ### Sample Explanation 3 $ F(N) = \left(((N))\times N^{234567890}+N^2\right) $ です。このケースは部分点の制約を満たしています。 ### Constraints - 関数 $ F(N) $ は問題文に示した BNF 記法の `` シンボルに従う文字列 $ F $ として与えられる - $ 1 \leq |F| \leq 10^5 $