P10096 [ROIR 2023] Cleaning Robot (Day 1)

Translated from [ROIR 2023 D1T3](https://neerc.ifmo.ru/school/archive/2022-2023/ru-olymp-regional-2023-day1.pdf)。 A cleaning robot is cleaning a 2D coordinate plane. The cleaning robot is a square of side length $k\times k$, with its sides parallel to the coordinate axes. Initially, the bottom-left corner of the robot is at $(0,0)$, and the top-right corner is at $(k,k)$.

You are given a sequence of $n$ move operations. The $i$-th move operation consists of a direction $d_i$ (`N` means up, increasing the $y$ coordinate; `E` means right, increasing the $x$ coordinate; `W` means left, decreasing the $x$ coordinate; `S` means down, decreasing the $y$ coordinate) and a distance $a_i$ (the distance the robot moves). Based on the given robot moves, compute the total cleaned area (a point is considered cleaned if it has been covered by the robot at least once).

The first line contains two integers: the robot size $k$ and the number of operations $n$. In the next $n$ lines, each line contains one move operation and the corresponding distance $a_i$. The move operation is given by a letter $d_i$ (`N` for up, `E` for right, `W` for left, `S` for down), and the distance $a_i$ is an integer.

Output the total area cleaned by the robot.

Sample explanation: The figure below shows the robot movements in the two samples.  #### Constraints **This problem uses bundled testdata.** | Subtask ID | Points | $k$ | $n$ | $a_i$ | |:---:|:--:|:--------:|:--------:|:--------:| | $1$ | $9$ | $= 1$ | $\le 10$ | $\le 10$ | | $2$ | $10$ | $\le 10$ | ^ | $\le 100$ | | $3$ | $11$ | $\le 1000$ | $\le 1000$ | $= 1$ | | $4$ | $8$ | $\le 10^4$ | $\le 10^5$ | $= k$ | | $5$ | $14$ | $= 1$ | $\le 1000$ | $\le 10^9$| | $6$ | $15$ | $\le 10^4$ | ^ | ^ | | $7$ | $16$ | $= 1$ | $\le 10^5$ | ^ | | $8$ | $17$ | $\le 10^4$ | ^ | ^ | For $100\%$ of the testdata, $1 \le k \le 10^4$, $1 \le n \le 10^5$, $1 \le a_i \le 10^9$. Translated by ChatGPT 5