n = gets.not_nil!.to_i t = gets.not_nil!.to_i a = gets.not_nil!.split.map(&.to_i) # Use hash-based DP to avoid bounds issues completely dp = Array(Hash(Int32, Bool)).new(n + 1) { Hash(Int32, Bool).new } dp[n][t] = true # Fill DP table backwards (n - 1).downto(0) do |i| dp[i + 1].each_key do |current_val| # Check subtraction if current_val >= a[i] prev_val = current_val - a[i] dp[i][prev_val] = true end # Check division (only if divisible) if a[i] != 0 && current_val % a[i] == 0 prev_val = current_val // a[i] dp[i][prev_val] = true end end end # Check if solution exists unless dp[0].has_key?(a[0]) puts -1 else # Reconstruct the solution ans = "" current = a[0] (1...n).each do |i| if dp[i + 1].has_key?(current + a[i]) ans += '+' current += a[i] elsif dp[i + 1].has_key?(current * a[i]) ans += '*' current *= a[i] else raise "Invalid solution path" end end puts ans end