{"raw_statement":[{"iden":"problem statement","content":"There are $N$ points in a two-dimensional plane. The initial coordinates of the $i$\\-th point are $(x_i, y_i)$. Now, each point starts moving at a speed of 1 per second, in a direction parallel to the $x$\\- or $y$\\- axis. You are given a character $d_i$ that represents the specific direction in which the $i$\\-th point moves, as follows:\n\n*   If $d_i =$ `R`, the $i$\\-th point moves in the positive $x$ direction;\n*   If $d_i =$ `L`, the $i$\\-th point moves in the negative $x$ direction;\n*   If $d_i =$ `U`, the $i$\\-th point moves in the positive $y$ direction;\n*   If $d_i =$ `D`, the $i$\\-th point moves in the negative $y$ direction.\n\nYou can stop all the points at some moment of your choice after they start moving (including the moment they start moving). Then, let $x_{max}$ and $x_{min}$ be the maximum and minimum among the $x$\\-coordinates of the $N$ points, respectively. Similarly, let $y_{max}$ and $y_{min}$ be the maximum and minimum among the $y$\\-coordinates of the $N$ points, respectively.\nFind the minimum possible value of $(x_{max} - x_{min}) \\times (y_{max} - y_{min})$ and print it."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 10^5$\n*   $-10^8 \\leq x_i,\\ y_i \\leq 10^8$\n*   $x_i$ and $y_i$ are integers.\n*   $d_i$ is `R`, `L`, `U`, or `D`."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$x_1$ $y_1$ $d_1$\n$x_2$ $y_2$ $d_2$\n$.$\n$.$\n$.$\n$x_N$ $y_N$ $d_N$"},{"iden":"sample input 1","content":"2\n0 3 D\n3 0 L"},{"iden":"sample output 1","content":"0\n\nAfter three seconds, the two points will meet at the origin. The value in question will be $0$ at that moment."},{"iden":"sample input 2","content":"5\n-7 -10 U\n7 -6 U\n-8 7 D\n-3 3 D\n0 -6 R"},{"iden":"sample output 2","content":"97.5\n\nThe answer may not be an integer."},{"iden":"sample input 3","content":"20\n6 -10 R\n-4 -9 U\n9 6 D\n-3 -2 R\n0 7 D\n4 5 D\n10 -10 U\n-1 -8 U\n10 -6 D\n8 -5 U\n6 4 D\n0 3 D\n7 9 R\n9 -4 R\n3 10 D\n1 9 U\n1 -6 U\n9 -8 R\n6 7 D\n7 -3 D"},{"iden":"sample output 3","content":"273"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}