type tree = Br of int * tree * tree | Lf

module IntSet = Set.Make
                  (
                    struct
                      type t = int
                      let compare (x : int) y = compare x y
                    end
                  )

let drop_chars str n =
  let len = String.length str in
  assert (n <= len);
  String.sub str n (len - n)

let parse_tree expr =
  let rec parse_tree expr n =
    if expr.[0] <> '(' then (Lf, expr)
    else
      let expr = drop_chars expr 1 in
      let lhs, expr = parse_tree expr (n * 2) in
      assert (expr.[0] = ',');
      let expr = drop_chars expr 1 in
      let rhs, expr = parse_tree expr (n * 2 + 1) in
      assert (expr.[0] = ')');
      (Br (n, lhs, rhs), drop_chars expr 1) in
  fst @@ parse_tree expr 1

let node_numbers tree =
  let rec node_numbers set = function
    | Lf -> set
    | Br (n, lhs, rhs) ->
       let set = IntSet.add n set in
       let set = node_numbers set lhs in
       node_numbers set rhs in
  node_numbers IntSet.empty tree

let encode_node_numberes set =
  let rec encode n =
    let lhs = if IntSet.mem (n * 2) set then encode (n * 2) else "" in
    let rhs = if IntSet.mem (n * 2 + 1) set then encode (n * 2 + 1) else "" in
    Printf.sprintf "(%s,%s)" lhs rhs in
  encode 1

let rec loop () =
  try
    let line = read_line () in
    let encoded =
      Scanf.sscanf
        line
        "%c %s %s"
        (fun c t1 t2 ->
         let t1, t2 =
           (node_numbers @@ parse_tree t1), (node_numbers @@ parse_tree t2) in
         let op = if c = 'i' then IntSet.inter else IntSet.union in
         encode_node_numberes (op t1 t2)) in
    print_endline encoded;
    loop ()
  with End_of_file -> ()

let () = loop ()