Compass Relay

Time limit: 2000 msMemory limit: 256 MB

A network activates one beacon on each of $N$ consecutive nights. Beacon $i$ is located at $(x_i,y_i)$ , has direction $d_i$ , and contributes charge $w_i$ when visited.

A route is a nonempty sequence of beacon indices $i_1<i_2<\cdots<i_k.$ For every consecutive pair and , beacon must lie in the closed quadrant indicated by beacon :

If $d_p$ is NE, then $x_q\ge x_p$ and .

All inequalities are non-strict, so a beacon on a quadrant boundary can receive the signal.

Moving between consecutive beacons loses charge equal to their Manhattan distance. Therefore, the charge of a route is

\sum_{t=1}^{k} w_{i_t} - \sum_{t=1}^{k-1} \left(\lvert x_{i_{t+1}}-x_{i_t}\rvert+ \lvert y_{i_{t+1}}-y_{i_t}\rvert\right).

Two routes are different if their index sequences are different. Determine the maximum possible charge and the number of routes attaining it, modulo $998244353$ .

Input

The first line contains an integer $N$ ( $1\le N\le 2\cdot 10^5$ ), the number of beacons.

The next $N$ lines describe the beacons in activation order. The -th line contains integers and , a string , and an integer (, ).

Output

Print two integers $S$ and $C$ . The value $S$ is the maximum charge of any valid route, and $C$ is the number of valid routes with charge $S$ , taken modulo $998244353$ .

Samples

Sample 1

Input

4
0 0 NE 5
2 1 SW 4
1 0 NE 3
2 0 NW 2

Output

8 2

The maximum charge is $8$ . It is attained by the routes with index sequences $[1,3,4]$ and $[1,2,3,4]$ .

Sample 2

Input

2
0 0 NE 3
2 0 SW 2

Output

3 2

The one-beacon route and the route both have charge .

Compass Relay

Input

Output

Samples

Sample 1

Sample 2

Submit

Submissions