题目描述

学校里有 $n$ 名同学，初始时第 $i$ 位同学从 ($x_i,y_i$) 出发，以每秒 $1$ 米的速度散步。

同学们散步的方向有东南西北四种可能。假设有一位同学正在位于 ($0,0$)，则下一秒︰

• 如果向东走，到达 ($1,0$)
• 如果向西走，到达 ($−1,0$)
• 如果向南走，到达 ($0,−1$)
• 如果向北走，到达 ($0,1$)

假设散步过程会进行无限长的时间，同学们散步的方向不会改变，并且忽略碰撞的情况（允许某个时刻多人在同一个点，互不影响）。

现在你可以选择某个非负整数秒时刻抓拍照片。

一张照片可以用长方形 $((e,n),(w,s))$ 表示，东北角为 ($e,n$)，西南角为 ($w,s$)。

只有抓拍的照片包含了所有同学时，我们才称这张照片是完美的。

请选择某个时刻抓拍一张完美的照片，使得照片的周长最小。

输入格式

第一行一个整数 $n$ ($1≤n≤2×10^5$)，代表人数。

接下来 $n$ 行，第 $i$ 行包含两个整数 $x_i,y_i$ ($−10^9≤x_i,y_i≤10^9$) 和一个字符 $d_i$ ，由空格分隔，描述第 $i$ 位同学。

$d_i$ 是 $\text{E}, \text{W}, \text{S}, \text{N}$ 之一，分别代表第 $i$ 位同学散步的方向是东、西、南、北。

输出格式

输出一行一个整数，代表最短的完美照片的周长。

输入样例

5
0 2 E
0 6 S
2 0 N
2 6 S
4 4 W

输出样例

8