You Are Given a WASD-string...
Contest: Educational Codeforces Round 70 (Rated for Div. 2)
Difficulty rating: 2100
Tags: brute force, data structures, dp, greedy, implementation, math, strings

You have a string $$$s$$$ — a sequence of commands for your toy robot. The robot is placed in some cell of a rectangular grid. He can perform four commands:

- 'W' — move one cell up;
- 'S' — move one cell down;
- 'A' — move one cell left;
- 'D' — move one cell right.

Let $$$Grid(s)$$$ be the grid of minimum possible area such that there is a position in the grid where you can place the robot in such a way that it will not fall from the grid while running the sequence of commands $$$s$$$. For example, if $$$s = \text{DSAWWAW}$$$ then $$$Grid(s)$$$ is the $$$4 \times 3$$$ grid:

1. you can place the robot in the cell $$$(3, 2)$$$;
2. the robot performs the command 'D' and moves to $$$(3, 3)$$$;
3. the robot performs the command 'S' and moves to $$$(4, 3)$$$;
4. the robot performs the command 'A' and moves to $$$(4, 2)$$$;
5. the robot performs the command 'W' and moves to $$$(3, 2)$$$;
6. the robot performs the command 'W' and moves to $$$(2, 2)$$$;
7. the robot performs the command 'A' and moves to $$$(2, 1)$$$;
8. the robot performs the command 'W' and moves to $$$(1, 1)$$$.

You have $$$4$$$ extra letters: one 'W', one 'A', one 'S', one 'D'. You'd like to insert at most one of these letters in any position of sequence $$$s$$$ to minimize the area of $$$Grid(s)$$$.

What is the minimum area of $$$Grid(s)$$$ you can achieve?

Input format:
The first line contains one integer $$$T$$$ ($$$1 \le T \le 1000$$$) — the number of queries.

Next $$$T$$$ lines contain queries: one per line. This line contains single string $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$, $$$s_i \in \{\text{W}, \text{A}, \text{S}, \text{D}\}$$$) — the sequence of commands.

It's guaranteed that the total length of $$$s$$$ over all queries doesn't exceed $$$2 \cdot 10^5$$$.

Output format:
Print $$$T$$$ integers: one per query. For each query print the minimum area of $$$Grid(s)$$$ you can achieve.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first query you have to get string $$$\text{DSAWW}\underline{D}\text{AW}$$$.

In second and third queries you can not decrease the area of $$$Grid(s)$$$.

Example input:
3
DSAWWAW
D
WA

Example output:
8
2
4

Editorial:
The problem asks us to maintain the bounding box while inserting the character of one of $$$4$$$ types between every adjacent characters in $$$s$$$. Of course, we can do it, but do we really need to do it in such cumbersome way?
Let's think a little. Inserting 'W' or 'S' doesn't affect the width of the bounding box, and 'A' or 'D' doesn't affect the height. So, they are absolutely independent! And we can divide our WASD-string on WS-string and AD-string. Moreover, inserting 'W' or 'S' in WS-string and 'A' or 'D' in AD-string is almost same thing, so we don't even need to write different code for different string!
How to handle only WS-string? Let's replace 'W' as $$$+1$$$ and 'S' as $$$-1$$$ and suppose that we started in position $$$0$$$. Then the position, where we go after $$$i$$$ commands, is just prefix sum of first $$$i$$$ elements ($$$i \ge 0$$$). Then the length of the bounding box is (maximum position - minimum position + 1). The maximum (minimum) position is a maximum (minimum) element in array of prefix sums $$$pSum$$$.
What the inserted value do? It add $$$\pm 1$$$ to suffix of $$$pSum$$$. Let's choose, for example, $$$+1$$$. The $$$+1$$$ can't decrease the maximum, but can increase the minimum, so we need to place it somewhere before all minimums in $$$pSum$$$ (or before the first minimum). But, if we place it before any of maximum elements then we will increase it and prevent decreasing the length of bounding box. So we need to place $$$+1$$$ somewhere after all maximums on $$$pSum$$$ (or after the last maximum). And here goes the solution: find position $$$firstMin$$$ of the first minimum in $$$pSum$$$ and position $$$lastMax$$$ of the last maximum. If $$$lastMax < firstMin$$$ then we can insert $$$+1$$$ and decrease the length of bounding box (but, since, we insert command that move robot, we can't achieve bounding box of length $$$< 2$$$).
What to do with $$$-1$$$? Just multiply $$$pSum$$$ by $$$-1$$$ and now we can insert $$$+1$$$ instead of $$$-1$$$ in absolutely same manner.
What to do with AD-string? Denote 'A' as $$$+1$$$ and 'D' as $$$-1$$$ and everything is absolutely the same.