S = gets.chomp C = '(*^)' C_MIN = Array.new(4){ Array.new(S.size + 2, S.size) } RB = Array.new(S.size + 2, 0) dp = Array.new(2){ Array.new(S.size + 1, 0) } (1 .. S.size).each do |d| i = S.size - d j_ = C.index(S[i]) 4.times{|j| C_MIN[j][i] = (j == j_ ? i : C_MIN[j][i + 1]) } RB[i] = (j_ == 3 ? RB[i + 1] + 1 : RB[i + 1]) end (0 ... S.size).each do |i| if S[i] == '(' dp[0][i + 1] = dp[0][i] + RB[C_MIN[1][C_MIN[2][C_MIN[2][i] + 1] + 1]] dp[1][i + 1] = dp[1][i] + RB[C_MIN[2][C_MIN[2][C_MIN[1][i] + 1] + 1]] else dp[0][i + 1] = dp[0][i] dp[1][i + 1] = dp[1][i] end end puts "#{dp[0][S.size]} #{dp[1][S.size]}"