XYDs = readlines.drop(1).map{|l| x, y, d = l.split; [x.to_i, y.to_i, d]}

f = ->(e){XYDs.select{|x, y, d| d == e}.map{|a| a[0, 2]}.transpose}
(@rx, @ry), (@lx, @ly), (@ux, @uy), (@dx, @dy) = ['R', 'L', 'U', 'D'].map{|d| f[d].empty? ? [[], []] : f[d]}

def g(t)
  dx = (@ux + @dx + @rx.map{|x| x + t} + @lx.map{|x| x - t}).minmax.inject(:-).abs
  dy = (@ry + @ly + @uy.map{|y| y + t} + @dy.map{|y| y - t}).minmax.inject(:-).abs
  dx * dy
end

xys = XYDs.group_by{|x, y, d| d}.values
vs = ->(i){xys.flat_map{|a| a.map{|b| b[i]}.minmax}.combination(2).flat_map{|a, b| d = (a - b).abs; [d, d/2.0]}}
puts ([0] + vs[0] + vs[1]).uniq.map{|t| g(t)}.min