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:  you can place the robot in the cell $(3, 2)$;  the robot performs the command 'D' and moves to $(3, 3)$;  the robot performs the command 'S' and moves to $(4, 3)$;  the robot performs the command 'A' and moves to $(4, 2)$;  the robot performs the command 'W' and moves to $(3, 2)$;  the robot performs the command 'W' and moves to $(2, 2)$;  the robot performs the command 'A' and moves to $(2, 1)$;  the robot performs the command 'W' and moves to $(1, 1)$.  [Image] 

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-----

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-----

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


-----Example-----
Input
3
DSAWWAW
D
WA

Output
8
2
4



-----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)$.

Difficulty: interview

Starter code:

Solutions:
n = int(input())

def area(width, height) :
    return (width+1) * (height+1)

def calcul(s1, c, s2) :
    maxx, maxy, minx, miny = 0, 0, 0, 0
    x, y = 0, 0
    for k in range(len(s1)) :
        if s1[k] == "W" :
            y += 1
        if s1[k] == "S" :
            y -= 1
        if s1[k] == "A" :
            x -= 1
        if s1[k] == "D" :
            x += 1
        maxx = max(maxx, x)
        minx = min(minx, x)

        maxy = max(maxy, y)
        miny = min(miny, y)




    if c == "W" :
        y += 1
    elif c == "S" :
        y -= 1
    elif c == "A" :
        x -= 1
    elif c == "D" :
        x += 1
    else :
        print(c, "ok")

    maxx = max(maxx, x)
    minx = min(minx, x)

    maxy = max(maxy, y)
    miny = min(miny, y)

    for k in range(len(s2)) :
        if s2[k] == "W" :
            y += 1
        if s2[k] == "S" :
            y -= 1
        if s2[k] == "A" :
            x -= 1
        if s2[k] == "D" :
            x += 1
        maxx = max(maxx, x)
        minx = min(minx, x)

        maxy = max(maxy, y)
        miny = min(miny, y)



    diffx = maxx - minx
    diffy = maxy - miny
    tmp = area(diffx, diffy)


    return tmp

def pre_calcul(s, moment, pre_avant, date_debut) :
    x, y, maxx, minx, maxy, miny = pre_avant
    for k in range(date_debut, moment) :
        if s[k] == "W" :
            y += 1
        if s[k] == "S" :
            y -= 1
        if s[k] == "A" :
            x -= 1
        if s[k] == "D" :
            x += 1
        maxx = max(maxx, x)
        minx = min(minx, x)

        maxy = max(maxy, y)
        miny = min(miny, y)

    return (x, y, maxx, minx, maxy, miny)

def calcul2(s, c, moment, precalcul) :
    x, y, maxx, minx, maxy, miny = precalcul



    if c == "W" :
        y += 1
    elif c == "S" :
        y -= 1
    elif c == "A" :
        x -= 1
    elif c == "D" :
        x += 1
    else :
        print(c, "ok")

    maxx = max(maxx, x)
    minx = min(minx, x)

    maxy = max(maxy, y)
    miny = min(miny, y)

    for k in range(moment, len(s)) :
        if s[k] == "W" :
            y += 1
        if s[k] == "S" :
            y -= 1
        if s[k] == "A" :
            x -= 1
        if s[k] == "D" :
            x += 1
        maxx = max(maxx, x)
        minx = min(minx, x)

        maxy = max(maxy, y)
        miny = min(miny, y)



    diffx = maxx - minx
    diffy = maxy - miny
    tmp = area(diffx, diffy)


    return tmp

for _ in range(n) :
    s = input()
    maxx, maxy, minx, miny = 0, 0, 0, 0
    x, y = 0, 0
    momentminx, momentmaxx, momentminy, momentmaxy = -1, -1, -1, -1
    for k in range(len(s)) :
        if s[k] == "W" :
            y += 1
        if s[k] == "S" :
            y -= 1
        if s[k] == "A" :
            x -= 1
        if s[k] == "D" :
            x += 1

        if x > maxx :
            momentmaxx = k
        if y > maxy :
            momentmaxy = k
        if x < minx :
            momentminx = k
        if y < miny :
            momentminy = k
        maxx = max(maxx, x)
        minx = min(minx, x)

        maxy = max(maxy, y)
        miny = min(miny, y)
    diffx = maxx - minx
    diffy = maxy - miny


    tmp = 999999999999999999999999999999999999
    l = [momentmaxx, momentmaxy, momentminx, momentminy]
    l = list(set(l))
    l = [i for i in l if i != -1]
    l.sort()
    if l != [] :
        precalcul = pre_calcul(s, l[0], (0, 0, 0, 0, 0, 0), 0)
        avant = l[0]
        for moment in l :
            precalcul = pre_calcul(s, moment, precalcul, avant)
            avant = moment
            tmp = min(tmp, calcul2(s, 'W', moment, precalcul))
            tmp = min(tmp, calcul2(s, 'S', moment, precalcul))
            tmp = min(tmp, calcul2(s, 'A', moment, precalcul))
            tmp = min(tmp, calcul2(s, 'D', moment, precalcul))
    print(tmp)


import sys
input = sys.stdin.readline
    
Q=int(input())

for testcases in range(Q):
    S=input().strip()

    X=Y=0
    MAXX=MINX=MAXY=MINY=0

    for s in S:
        if s=="D":
            X+=1
            MAXX=max(MAXX,X)

        elif s=="A":
            X-=1
            MINX=min(MINX,X)

        elif s=="W":
            Y+=1
            MAXY=max(MAXY,Y)

        else:
            Y-=1
            MINY=min(MINY,Y)

    #print(MAXX,MINX,MAXY,MINY)

    MAXXLIST=[]
    MINXLIST=[]
    MAXYLIST=[]
    MINYLIST=[]

    if MAXX==0:
        MAXXLIST.append(0)

    if MAXY==0:
        MAXYLIST.append(0)

    if MINX==0:
        MINXLIST.append(0)

    if MINY==0:
        MINYLIST.append(0)

    X=Y=0
        

    for i in range(len(S)):
        s=S[i]
        if s=="D":
            X+=1
            if X==MAXX:
                MAXXLIST.append(i+1)
                
        elif s=="A":
            X-=1
            if X==MINX:
                MINXLIST.append(i+1)

        elif s=="W":
            Y+=1
            if Y==MAXY:
                MAXYLIST.append(i+1)

        else:
            Y-=1
            if Y==MINY:
                MINYLIST.append(i+1)

    #print(MAXXLIST)
    #print(MAXYLIST)
    #print(MINXLIST)
    #print(MINYLIST)

    ANS=(MAXX-MINX+1)*(MAXY-MINY+1)

    #print(ANS)


    if MAXX-MINX>1:
        if MAXXLIST[0]>MINXLIST[-1] or MINXLIST[0]>MAXXLIST[-1]:
            ANS=min(ANS,(MAXX-MINX)*(MAXY-MINY+1))

    if MAXY-MINY>1:
        if MAXYLIST[0]>MINYLIST[-1] or MINYLIST[0]>MAXYLIST[-1]:
            ANS=min(ANS,(MAXX-MINX+1)*(MAXY-MINY))

    print(ANS)
        


T = int(input())

for _ in range(T):
	s = input()

	cleft=cup=cdown=cright=0
	left=up=down=right=0
	fleft=lleft=0
	fright=lright=0
	fup=lup=0
	fdown=ldown=0

	x=y=0
	for i, c in enumerate(s):
		if c=="W":
			y -= 1
			cup += 1
		elif c=="S":
			y += 1
			cdown += 1
		elif c=="A":
			x -= 1
			cleft += 1
		elif c=="D":
			x += 1
			cright += 1

		if x == left:
			lleft = i
		if x == right:
			lright = i
		if y == down:
			ldown = i
		if y == up:
			lup = i

		if x < left:
			left = x
			fleft=i
			lleft=i

		if x > right:
			right = x
			fright=i
			lright=i


		if y < up:
			up = y
			fup=i
			lup=i


		if y > down:
			down = y
			fdown=i
			ldown=i

	width = right - left + 1
	height = down - up + 1

	best = width * height

	if height > 2:
		if ldown < fup or lup < fdown:
			best = min(best, width * (height-1))
	if width > 2:
		if lleft < fright or lright < fleft:
			best = min(best, (width-1) * height)
	print(best)

t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	fa, fd, fs, fw = [0], [0], [0], [0]
	ba, bd, bs, bw = [0], [0], [0], [0]
	cur = [0, 0]
	for i in range(n):
		if s[i] == "A":
			cur[0] -= 1
			
		elif s[i] == "D":
			cur[0] += 1
			
		elif s[i] == "S":
			cur[1] -= 1
			
		elif s[i] == "W":
			cur[1] += 1
			
		fa.append(min(fa[-1], cur[0]))
		fd.append(max(fd[-1], cur[0]))
		fs.append(min(fs[-1], cur[1]))
		fw.append(max(fw[-1], cur[1]))

	h = fd[-1]-fa[-1]
	v = fw[-1]-fs[-1]
	area = (h+1)*(v+1)

	cur = [0, 0]
	for i in range(n-1, -1, -1):
		if s[i] == "D":
			cur[0] -= 1
		elif s[i] == "A":
			cur[0] += 1
		elif s[i] == "W":
			cur[1] -= 1
		elif s[i] == "S":
			cur[1] += 1

		ba.append(min(ba[-1], cur[0]))
		bd.append(max(bd[-1], cur[0]))
		bs.append(min(bs[-1], cur[1]))
		bw.append(max(bw[-1], cur[1]))

	ba.reverse()
	bd.reverse()
	bs.reverse()
	bw.reverse()

	#print(fa, fd, fs, fw)
	#print(ba, bd, bs, bw)

	hok, vok = False, False
	for i in range(1, n):
		#print(n, i)
		if fd[i]-fa[i] < h and abs(bd[i]-ba[i]) < h:
			hok = True
		if fw[i]-fs[i] < v and abs(bw[i]-bs[i]) < v:
			vok = True

	if hok:
		area = min(area, h*(v+1))
	if vok:
		area = min(area, v*(h+1))
	print(area)


for q in range(int(input())):

    data = input()
    # if data in ["WW", "AA", "SS", "DD"]:
    #     print(2)
    #     continue
    mx = [0,0,0,0]
    x = 0
    y = 0
    pos = [[-1],[-1],[-1],[-1]]
    for i in range(len(data)):
        # print(x,y)
        d = data[i]
        if d == "W":
            y += 1
            if y > mx[0]:
                
                mx[0] = y
                pos[0] = []
        elif d == "S":
            y -= 1
            if y < mx[2]:
                
                mx[2] = y
                pos[2] = []
        elif d == "A":
            x -= 1
            if x < mx[1]:
                
                mx[1] = x
                pos[1] = []
        else:
            x += 1
            if x > mx[3]:
                
                mx[3] = x
                pos[3] = []
        if x == mx[3]:
            pos[3].append(i)
        if x == mx[1]:
            pos[1].append(i)
        if y == mx[0]:
            pos[0].append(i)
        if y == mx[2]:
            pos[2].append(i)

    # print(mx)
    # print(pos)
    wid = mx[3] - mx[1] + 1
    hei = mx[0] - mx[2] + 1
    ans = wid * hei

    
    
    if pos[3][0] > pos[1][-1] + 1 or pos[1][0] > pos[3][-1] + 1:
        ans -= hei
    if pos[0][0] > pos[2][-1] + 1 or pos[2][0] > pos[0][-1] + 1:
        ans = min((hei-1)*(wid), ans)
    print(ans)

T = int(input())

w = [[-1, 0], [1, 0], [0, 1], [0, -1]]
mp = {'A':0, 'D':1, 'W':2, 'S':3}
while T > 0:
	T-=1
	s = input()
	l = [0]; r = [0];
	u = [0]; d = [0];

	for dir in s[::-1]:
		l.append(l[-1])
		r.append(r[-1])
		u.append(u[-1])
		d.append(d[-1])
		if dir == 'A':
			l[-1]+=1
			if r[-1] > 0: r[-1]-=1
		elif dir == 'D':
			r[-1]+=1
			if l[-1] > 0: l[-1]-=1
		elif dir == 'S':
			d[-1]+=1
			if u[-1] > 0: u[-1]-=1
		else:
			u[-1]+=1
			if d[-1] > 0: d[-1]-=1

	l = l[::-1]; r = r[::-1]; u = u[::-1]; d = d[::-1];

	x = 0; y = 0
	ml = 0; mr = 0; mu = 0; md = 0;

	ans = (l[0] + r[0] + 1) * (u[0] + d[0] + 1)
	for i in range(len(s)+1):
		mml=ml;mmr=mr;mmu=mu;mmd=md;
		for j in range(4):
			xx=x+w[j][0]
			yy=y+w[j][1]

			if xx<0: ml=max(ml,-xx)
			if xx>0: mr=max(mr,xx)
			if yy>0: mu=max(mu,yy)
			if yy<0: md=max(md,-yy)

			xx-=l[i]
			if xx<0: ml=max(ml,-xx)
			xx+=r[i]+l[i];
			if xx>0: mr=max(mr,xx)
			yy-=d[i]
			if yy<0: md=max(md,-yy)
			yy+=u[i]+d[i]
			if yy>0: mu=max(mu,yy)

			ans = min(ans, (ml+mr+1)*(mu+md+1))
			ml=mml;mr=mmr;mu=mmu;md=mmd;

		if i < len(s):
			x+=w[mp[s[i]]][0]
			y+=w[mp[s[i]]][1]
			if x<0: ml=max(ml,-x)
			if x>0: mr=max(mr,x)
			if y>0: mu=max(mu,y)
			if y<0: md=max(md,-y)

	print(ans)

import sys
from collections import defaultdict
input = sys.stdin.readline
import math


def main():
    t = int(input())
    for _ in range(t):
        s = input().rstrip()
        a1 = []
        a2 = []
        ws = {'W': 1, 'S': -1}
        ad = {'A': 1, 'D': -1}
        for c in s:
            if c in ('W', 'S'):
                a1.append(ws[c])
            else:
                a2.append(ad[c])
        pref_a1 = [0] + a1.copy()
        pref_a2 = [0] + a2.copy()
        for i in range(1, len(pref_a1)):
            pref_a1[i] += pref_a1[i-1]
        for i in range(1, len(pref_a2)):
            pref_a2[i] += pref_a2[i-1]

        def canDecrease(a):
            _min = min(a)
            _max = max(a)

            # decrease max
            _min_rindex = a.index(_min)
            for i in range(_min_rindex, len(a)):
                if a[i] == _min:
                    _min_rindex = i
            _max_index = a.index(_max)
            if _max_index > _min_rindex:
                return True

            # increase min
            _max_rindex = a.index(_max)
            for i in range(_max_rindex, len(a)):
                if a[i] == _max:
                    _max_rindex = i
            _min_index = a.index(_min)
            if _max_rindex < _min_index:
                return True

            return False

        x = max(pref_a1)-min(pref_a1)
        y = max(pref_a2)-min(pref_a2)
        res = (x+1) * (y+1)
        if x > 1 and canDecrease(pref_a1):
            res = min(res, x * (y+1))
        if y > 1 and canDecrease(pref_a2):
            res = min(res, (x+1) * y)

        print(res)


def __starting_point():
    main()


__starting_point()


for i in range(int(input())):
	s = input()
	lm, rm, um, dm = 0, 0, 0, 0
	xp, yp = 0, 0
	for ch in s:
		if ch == 'W':
			yp += 1
		elif ch == 'A':
			xp -= 1
		elif ch == 'S':
			yp -= 1
		else:
			xp += 1
		lm = min(lm, xp)
		rm = max(rm, xp)
		um = max(um, yp)
		dm = min(dm, yp)
	xp, yp = 0, 0
	lmfSet, rmfSet, umfSet, dmfSet = 0, 0, 0, 0
	if lm == 0:
		lml = 0
		lmf = 0
		lmfSet = 1
	if rm == 0:
		rml = 0
		rmf = 0
		rmfSet = 1
	if um == 0:
		uml = 0
		umf = 0
		umfSet = 1
	if dm == 0:
		dml = 0
		dmf = 0
		dmfSet = 1
	for i, ch in zip(list(range(1, len(s) + 1)), s):
		if ch == 'W':
			yp += 1
		elif ch == 'A':
			xp -= 1
		elif ch == 'S':
			yp -= 1
		else:
			xp += 1
		if xp == lm:
			lml = i
			if not lmfSet:
				lmf = i
				lmfSet = 1
		if xp == rm:
			rml = i
			if not rmfSet:
				rmf = i
				rmfSet = 1
		if yp == um:
			uml = i
			if not umfSet:
				umf = i
				umfSet = 1
		if yp == dm:
			dml = i
			if not dmfSet:
				dmf = i
				dmfSet = 1
	canx, cany = 0, 0
	if dml + 1 < umf or uml + 1 < dmf:
		cany = 1
	if lml + 1 < rmf or rml + 1 < lmf:
		canx = 1
	if canx:
		if cany:
			print(min((um - dm) * (rm - lm + 1), (um - dm + 1) * (rm - lm)))
		else:
			print((rm - lm) * (um - dm + 1))
	else:
		if cany:
			print((um - dm) * (rm - lm + 1))
		else:
			print((rm - lm + 1) * (um - dm + 1))




t=int(input())
def possible(presum):
    l=len(presum)
    lastmax=-1
    firstmin=l
    mx=max(presum)
    mn=min(presum)
    for i in range(l):
        if(mx==presum[i]):
            lastmax=max(lastmax,i)
        if(mn==presum[i]):
            firstmin=min(i,firstmin)
    if lastmax<firstmin:
        return True
    return False
for i in range(t):
    s=input()
    l1=[0]
    l2=[0]
    for i in s:
        if i=='S':
            l1.append(l1[-1]-1)
        elif i=='W':
            l1.append(l1[-1]+1)
        elif i=="D":
            l2.append(l2[-1]+1)
        else:
            l2.append(l2[-1]-1)
    length=max(l1)-min(l1)+1
    breadth=max(l2)-min(l2)+1
    ans=length*breadth
    if length>2 and possible(l1):
        ans=min(ans,(length-1)*breadth)
    for i in range(len(l1)):
        l1[i]*=-1
    if length>2 and possible(l1):
        ans=min(ans,(length-1)*breadth)
    if breadth>2 and possible(l2):
        ans=min(ans,(length)*(breadth-1))
    for i in range(len(l2)):
        l2[i]*=-1
    if breadth>2 and possible(l2):
        ans=min(ans,(length)*(breadth-1))
    print(ans)

def lim(s):
    now = 0
    up, down = 0, 0
    for i in s:
        now += i
        up = max(up, now)
        down = min(down, now)
    return up, down
def f(a):
    return a[0] - a[1] + 1
def upg(s):
    t = lim(s)
    up, down = t[0], t[1]
    arr = [1, 1]
    now = 0
    for i in range(len(s) - 1):
        if now == up - 1 and s[i + 1] == 1 and arr[0] == 1:
            arr[0] = 0
            if f(lim(s[:(i + 1)] + [-1] + s[(i + 1):])) < f(t):
                return 1
        if now == down + 1 and s[i + 1] == -1 and arr[1] == 1:
            arr[1] = 0
            if f(lim(s[:(i + 1)] + [1] + s[(i + 1):])) < f(t):
                return 1
        now += s[i + 1]
    return 0


for q in range(int(input())):
    s = input()
    s1, s2 = [0], [0]
    for i in s:
        if i == 'W': s1.append(1)
        if i == 'S': s1.append(-1)
        if i == 'A': s2.append(1)
        if i == 'D': s2.append(-1)
    u1 = upg(s1)
    u2 = upg(s2)
    res1, res2 = f(lim(s1)), f(lim(s2))
    ans = min((res1 - u1) * res2, (res2 - u2) * res1)
    print(ans)

t= int(input())

for _ in range(0,t):

    a= list(input())
    nowx=0
    nowy=0
    maxx=0
    minx=0
    maxy=0
    miny=0
    tmaxx=0
    tminx=0
    tmaxy=0
    tminy=0
    highw=0
    highs=0
    widthd=0
    widtha=0
    for i in range (0,len(a)):
        
        if a[i] == 'W':
            nowy += 1
            if nowy >= maxy:
                maxy=nowy
                tmaxy=i
                
        elif a[i] == 'S':
            nowy -= 1
            if nowy <=miny:
                miny=nowy
                tminy=i
        elif a[i] == 'D':
            nowx += 1
            if nowx >= maxx:
                maxx=nowx
                tmaxx=i
        elif a[i] == 'A':
            nowx -= 1
            if nowx <=minx:
                minx=nowx
                tminx=i

        highw= max(highw,nowy-miny)
        highs= max(highs,maxy-nowy)
        widthd=max(widthd,nowx-minx)
        widtha=max(widtha,maxx-nowx)
    y1= max(highw,highs)
    y2= max(highw!=0 or highs!=0, y1- ((highw!=highs)))
    x1= max(widthd,widtha)
    x2= max(widthd!=0 or widtha!=0, x1-((widthd!=widtha)))
    print(min((y1+1)*(x2+1),(1+y2)*(x1+1)))
    
  
    
    

   

    
    


t = int(input())
for _ in range(t):
    ss = input()
    minx=0
    fminxpos = -1
    lminxpos = -1
    maxx=0
    fmaxxpos = -1
    lmaxxpos = -1
    miny=0
    fminypos = -1
    lminypos = -1
    maxy=0
    fmaxypos = -1
    lmaxypos = -1
    x = 0
    y = 0
    for i,s in enumerate(ss):
        if s == 'W':
            y +=1
            if y > maxy:
                maxy=y
                fmaxypos=i
            if y == maxy:
                lmaxypos=i
        elif s == 'S':
            y -= 1
            if y < miny:
                miny = y
                fminypos = i
            if y == miny:
                lminypos = i
        elif s == 'D':
            lastd = i
            x += 1
            if x > maxx:
                maxx = x
                fmaxxpos = i
            if x == maxx:
                lmaxxpos = i
        elif s == 'A':
            lasta = i
            x -= 1
            if x < minx:
                minx = x
                fminxpos = i
            if x == minx:
                lminxpos = i
    xsize = maxx - minx + 1
    ysize = maxy - miny + 1
    if xsize > 2 and (fmaxxpos > lminxpos or fminxpos > lmaxxpos):
        xmin = xsize - 1
    else:
        xmin = xsize
    if ysize > 2 and (fmaxypos > lminypos or fminypos > lmaxypos):
        ymin = ysize - 1
    else:
        ymin = ysize
    print(min(xmin*ysize, xsize*ymin))

T = int(input())

for _ in range(T):
    cmd = input()

    mostL, mostR, mostB, mostT = 0, 0, 0, 0
    mostLs, mostRs, mostBs, mostTs = [0],[0],[0],[0]
    x,y=0,0
    i = 0
    for c in cmd:
        i += 1
        if c == "W":
            y += 1
            if y>mostT:
                mostT = y
                mostTs = [i]
            elif y == mostT:
                mostTs.append(i)
        elif c == "S":
            y -= 1
            if y<mostB:
                mostB = y
                mostBs = [i]
            elif y == mostB:
                mostBs.append(i)
        elif c == "A":
            x -= 1
            if x < mostL:
                mostL = x
                mostLs = [i]
            elif x == mostL:
                mostLs.append(i)
        elif c == "D":
            x += 1
            if x > mostR:
                mostR = x
                mostRs = [i]
            elif x == mostR:
                mostRs.append(i)

    LR = mostR - mostL + 1
    if LR >= 3:
        firstL, lastL = mostLs[0], mostLs[-1]
        firstR, lastR = mostRs[0], mostRs[-1]

        cross = lastR > firstL and lastL > firstR
        LR_extra = not cross
    else:
        LR_extra = False

    BT = mostT - mostB + 1
    if BT >= 3:
        firstB, lastB = mostBs[0], mostBs[-1]
        firstT, lastT = mostTs[0], mostTs[-1]

        cross = lastB > firstT and lastT > firstB
        BT_extra = not cross
    else:
        BT_extra = False

    if LR_extra and BT_extra:
        area = min((LR-1)*BT,LR*(BT-1))
    elif LR_extra:
        area = (LR-1)*BT
    elif BT_extra:
        area = LR*(BT-1)
    else:
        area = LR*BT
    print(area)

def main():
    hh, vv, r = [0], [0], []
    f = {'W': (vv, -1), 'S': (vv, 1), 'A': (hh, -1), 'D': (hh, 1)}.get
    for _ in range(int(input())):
        del vv[1:], hh[1:], r[:]
        for l, d in map(f, input()):
            l.append(l[-1] + d)
        for l in hh, vv:
            mi, ma = min(l), max(l)
            a, tmp = mi - 1, []
            for b in filter((mi, ma).__contains__, l):
                if a != b:
                    a = b
                    tmp.append(a)
            ma -= mi - 1
            r.append(ma)
            if len(tmp) < 3 <= ma:
                ma -= 1
            r.append(ma)
        print(min((r[0] * r[3], r[1] * r[2])))


def __starting_point():
    main()

__starting_point()

def main():
    h, v = hv = ([0], [0])
    f = {'W': (v, -1), 'S': (v, 1), 'A': (h, -1), 'D': (h, 1)}.get
    for _ in range(int(input())):
        del h[1:], v[1:]
        for l, d in map(f, input()):
            l.append(l[-1] + d)
        x = y = 1
        for l in hv:
            lh, a, n = (min(l), max(l)), 200001, 0
            for b in filter(lh.__contains__, l):
                if a != b:
                    a = b
                    n += 1
            le = lh[1] - lh[0] + 1
            x, y = y * le, x * (le - (n < 3 <= le))
        print(x if x < y else y)


def __starting_point():
    main()

__starting_point()

t = int(input())
for c in range(t):
    s = input()
    up_max = down_max = right_max = left_max = 0
    first_up = last_up = first_down = last_down = first_left = last_left = first_right = last_right = 0
    current_x = current_y = 0
    horizontal_count = vertical_count = 0
    for i in range(len(s)):
        if s[i] == 'W':
            current_y += 1
            vertical_count += 1
            if current_y > up_max:
                up_max = current_y
                first_up = last_up = i + 1
            elif current_y == up_max:
                last_up = i + 1
        elif s[i] == 'S':
            current_y -= 1
            vertical_count += 1
            if current_y < down_max:
                down_max = current_y
                first_down = last_down = i + 1
            elif current_y == down_max:
                last_down = i + 1
        elif s[i] == 'D':
            current_x += 1
            horizontal_count += 1
            if current_x > right_max:
                right_max = current_x
                first_right = last_right = i + 1
            elif current_x == right_max:
                last_right = i + 1
        else:
            current_x -= 1
            horizontal_count += 1
            if current_x < left_max:
                left_max = current_x
                first_left = last_left = i + 1
            elif current_x == left_max:
                last_left = i + 1

    h = up_max - down_max + 1
    w = right_max - left_max + 1
    ans = h * w
    if vertical_count > 1 and last_up < first_down:
        ans = min(ans, (h - 1) * w)
    if vertical_count > 1 and last_down < first_up:
        ans = min(ans, (h - 1) * w)
    if horizontal_count > 1 and last_right < first_left:
        ans = min(ans, h * (w - 1))
    if horizontal_count > 1 and last_left < first_right:
        ans = min(ans, h * (w - 1))

    print(ans)

q = int(input())
for _ in range(q):
    d = [x for x in list(input())]
    x, y = 0, 0
    minX, maxX, minY, maxY = 0, 0 ,0 ,0
    allowW, allowS, allowA, allowD = True, True, True, True
    for v in d:
        if v == 'W':
            y += 1
            if y > maxY:
                maxY = y
                allowS = True
                allowW = False
            elif y == maxY:
                allowW = False
        elif v == 'S':
            y -= 1
            if y < minY:
                minY = y
                allowW = True
                allowS = False
            elif y == minY:
                allowS = False
        elif v == 'A':
            x -= 1
            if x < minX:
                minX = x
                allowA = False
                allowD = True
            elif x == minX:
                allowA = False
        else:#if v == 'D':
            x += 1
            if x > maxX:
                maxX = x
                allowA = True
                allowD = False
            elif x == maxX:
                allowD = False
    val = (maxX-minX+1)*(maxY-minY+1)
    if (maxX-minX) > 1 and (allowD or allowA):
        val = min(val, (maxX-minX)*(maxY-minY+1))
    if (maxY-minY) > 1 and (allowW or allowS):
        val = min(val, (maxX-minX+1)*(maxY-minY))
    print(val)

# coding=utf-8
INF = 1e11

# move = {'W': (0, 0), 'A': (0, 0), 'S': (0, 0), 'D': (0, 0)}
move = {'W': (0, 1), 'A': (-1, 0), 'S': (0, -1), 'D': (1, 0)}


def getExtremes(positions):
    minX, minY, maxX, maxY = [positions[0][0]], [positions[0][1]], [positions[0][0]], [positions[0][1]]
    for p in positions[1:]:
        minX.append(min(minX[-1], p[0]))
        minY.append(min(minY[-1], p[1]))
        maxX.append(max(maxX[-1], p[0]))
        maxY.append(max(maxY[-1], p[1]))
    return minX, minY, maxX, maxY


t = int(input())

while t > 0:
    t -= 1
    s = input()
    x, y = 0, 0
    positions = [(0, 0)]
    for c in s:
        x, y = x + move[c][0], y + move[c][1]
        positions.append((x, y))
    # print(positions)
    # print()
    minXBeg, minYBeg, maxXBeg, maxYBeg = getExtremes(positions)
    # print(minXBeg, minYBeg, maxXBeg, maxYBeg, sep="\n")
    # print()
    positions.reverse()
    minXEnd, minYEnd, maxXEnd, maxYEnd = getExtremes(positions)
    minXEnd.reverse()
    minYEnd.reverse()
    maxXEnd.reverse()
    maxYEnd.reverse()
    # print(minXEnd, minYEnd, maxXEnd, maxYEnd, sep="\n")
    # print()
    positions.reverse()
    ans = INF
    for i in range(len(s)):
        for c in move:
            minX = min(minXBeg[i], positions[i][0] + move[c][0], minXEnd[i + 1] + move[c][0])
            maxX = max(maxXBeg[i], positions[i][0] + move[c][0], maxXEnd[i + 1] + move[c][0])
            minY = min(minYBeg[i], positions[i][1] + move[c][1], minYEnd[i + 1] + move[c][1])
            maxY = max(maxYBeg[i], positions[i][1] + move[c][1], maxYEnd[i + 1] + move[c][1])
            area = (maxX - minX + 1) * (maxY - minY + 1)
            # print(i, c, minX, maxX, minY, maxY, area)
            ans = min(ans, area)
    print(ans)


def solve():
    i = 0
    j = 0
    imax = imin = 0
    jmax = jmin = 0
    fjmin = ljmin = fjmax = ljmax = fimax = limax = fimin = limin = -1
    for ind, e in enumerate(input()):
        if e == 'W':
            i += 1
            if i > imax:
                imax = i
                fimax = ind
                limax = ind
        elif e == 'S':
            i -= 1
            if i < imin:
                imin = i
                fimin = ind
                limin = ind
        elif e == "A":
            j -= 1
            if j < jmin:
                jmin = j
                fjmin = ind
                ljmin = ind
        elif e == 'D':
            j += 1
            if j > jmax:
                jmax = j
                fjmax = ind
                ljmax = ind
        if j == jmin:
            ljmin = ind
        if j == jmax:
            ljmax = ind
        if i == imin:
            limin = ind
        if i == imax:
            limax = ind
    ans = 0
    if fjmax > ljmin + 1 or fjmin > ljmax + 1:
        ans = imax - imin + 1
    if fimax > limin + 1 or fimin > limax + 1:
        ans = max(ans, jmax - jmin + 1)
    print((imax - imin + 1) * (jmax - jmin + 1) - ans)


for _ in range(int(input())):
    solve()


import sys
input = sys.stdin.readline


Q = int(input())
Query = [list(input().rstrip()) for _ in range(Q)]

for S in Query:
    L = len(S)
    T = [(0, 0)]
    for s in S:
        x, y = T[-1]
        if s == "W":
            T.append((x, y+1))
        elif s == "S":
            T.append((x, y-1))
        elif s == "A":
            T.append((x-1, y))
        else:
            T.append((x+1, y))
    
    # up, down, left, right
    dp1 = [[0, 0, 0, 0] for _ in range(L+1)]
    for i, (x, y) in enumerate(T):
        if i == 0: continue
        dp1[i][0] = max(y, dp1[i-1][0])
        dp1[i][1] = min(y, dp1[i-1][1])
        dp1[i][2] = min(x, dp1[i-1][2])
        dp1[i][3] = max(x, dp1[i-1][3])
    

    lx, ly = T[-1]
    dp2 = [[ly, ly, lx, lx] for _ in range(L+1)]
    for i in reversed(range(L)):
        x, y = T[i]
        dp2[i][0] = max(y, dp2[i+1][0])
        dp2[i][1] = min(y, dp2[i+1][1])
        dp2[i][2] = min(x, dp2[i+1][2])
        dp2[i][3] = max(x, dp2[i+1][3])
    
    Y, X = dp1[L][0]-dp1[L][1]+1, dp1[L][3]-dp1[L][2]+1
    ans = 0
    for i in range(L):
        if dp1[i][0] < dp2[i][0] and dp1[i][1] < dp2[i][1]:
            ans = max(ans, X)
        if dp1[i][0] > dp2[i][0] and dp1[i][1] > dp2[i][1]:
            ans = max(ans, X)
        if dp1[i][2] < dp2[i][2] and dp1[i][3] < dp2[i][3]:
            ans = max(ans, Y)
        if dp1[i][2] > dp2[i][2] and dp1[i][3] > dp2[i][3]:
            ans = max(ans, Y)
    print(X*Y-ans)

def read_int():
    return int(input())


def read_ints():
    return list(map(int, input().split(' ')))


t = read_int()
INF = int(1e7)
for case_num in range(t):
    s = input()
    x = 0
    y = 0
    xlist = [0]
    ylist = [0]
    for c in s:
        if c == 'W':
            y += 1
        elif c == 'S':
            y -= 1
        elif c == 'A':
            x -= 1
        else:
            x += 1
        xlist.append(x)
        ylist.append(y)
    n = len(s)
    l = [0]
    r = [0]
    u = [0]
    d = [0]
    for i in range(1, n + 1):
        l.append(min(l[-1], xlist[i]))
        r.append(max(r[-1], xlist[i]))
        u.append(max(u[-1], ylist[i]))
        d.append(min(d[-1], ylist[i]))
    lr = [xlist[n]]
    rr = [xlist[n]]
    ur = [ylist[n]]
    dr = [ylist[n]]
    for i in range(1, n + 1):
        lr.append(min(lr[-1], xlist[n - i]))
        rr.append(max(rr[-1], xlist[n - i]))
        ur.append(max(ur[-1], ylist[n - i]))
        dr.append(min(dr[-1], ylist[n - i]))
    ans = INF * INF
    coeff = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    for k in range(4):
        for i in range(n):
            nl = min(l[i], lr[n - i] + coeff[k][0])
            nr = max(r[i], rr[n - i] + coeff[k][0])
            nu = max(u[i], ur[n - i] + coeff[k][1])
            nd = min(d[i], dr[n - i] + coeff[k][1])
            area = (nr - nl + 1) * (nu - nd + 1)
            ans = min(ans, area)
    print(ans)


import sys
input = sys.stdin.readline

for _ in range(int(input())):
    s = input()
    l, r, u, d, fl, fr, fu, fd, x, y = [0] * 10
    for i in range(len(s)):
        if s[i] == 'W':
            y += 1
            if y > u:
                u = y
                fd = 0
                fu = 1
            if y == u:
                fu = 1
        elif s[i] == 'A':
            x -= 1
            if x < l:
                l = x
                fl = 1
                fr = 0
            if x == l:
                fl = 1
        elif s[i] == 'S':
            y -= 1
            if y < d:
                d = y
                fd = 1
                fu = 0
            if y == d:
                fd = 1
        elif s[i] == 'D':
            x += 1
            if x > r:
                r = x
                fr = 1
                fl = 0
            if x == r:
                fr = 1
    #bless Ctrl+C Ctrl+V
    x, y = r - l + 1, u - d + 1
    s, k = x * y, x * y
    if x > 2 and not fl * fr:
        s = k - y
    if y > 2 and not fu * fd and k - x < s:
        s = k - x
    print(s)

import sys
def work(c,c1, s):
    maxlast, maxfirst,minlast,minfirst = 0,0,0,0
    max = 0
    min = 0
    y = 0
    for i in range(len(s)):
        if s[i] == c:
            y += 1
        elif s[i] == c1:
            y -=1

        if max < y:
            maxfirst,maxlast = i,i
            max = y
        elif max ==y :
            maxlast = i

        if y < min:
            minlast,minfirst =i,i
            min = y
        elif min == y:
            minlast = i
    flag = 0
    if (maxlast<minfirst or maxfirst>minlast) and max-min > 1:
        flag = 1
    return  max-min+1,flag

count = 0
for line in sys.stdin:
    if count == 0:
        n = int(line.strip().split(' ')[0])
        #k = int(line.strip().split(' ')[1])
        #m = int(line.strip().split(' ')[2])
        count += 1
        continue
    s = line.strip()
    flag,flag1 =0,0
    n,flag = work('W','S', s)
    m,flag1 = work('A', 'D', s)

    res = n * m
    if flag1 and flag:
        res = min(n*(m-1),m*(n-1))
    elif flag:
        res = m*(n-1)
    elif flag1:
        res = (m-1)*n
    print(res)