Mr. X stays in a mansion whose door opens in the North. He travels every morning to meet his friend Ms. Y walking a predefined path.

To cut the distance short, one day he decides to construct a skywalk from his place to his friend’s place. Help him to find the shortest distance between the two residences.


-----Input-----

The first line contains a single positive integer T <= 100, the number of test cases. T test cases follow. The only line of each test case contains a string which is the path from X to Y. The integer value represents the distance. The character R or L represents a Right or a Left respectively.

-----Output-----

For each test case, output a single line containing the minimum distance and the direction(N,S,W,E,NE,NW,SE,SW) of Y’s residence with respect to X’s residence. The output distance should have only 1 decimal place with no approximation. Print “0.0” if X’s and Y’s residence coincide.

-----Example-----
Input:
1
2 L 2 R 2 L 1

Output:
5.0NW

Explanation
Mr. X travels 2units and then takes a Left, and then he travels 2units and takes a Right, then after travelling 2units he takes a Left and finally travels 1unit to reach Y’s residence.
(Unlike Input, Output does not have spaces between the distance and direction)

Difficulty: interview

Starter code:

Solutions:
#!/usr/bin/env python

from math import sqrt

def process(S):
 P = [0,0,'S']
 for i in S:
  if i == 'L':
   if P[-1] == 'N': P[-1] = 'W'
   elif P[-1] == 'S': P[-1] = 'E'
   elif P[-1] == 'E': P[-1] = 'N'
   elif P[-1] == 'W': P[-1] = 'S'
  elif i == 'R':
   if P[-1] == 'N': P[-1] = 'E'
   elif P[-1] == 'S': P[-1] = 'W'
   elif P[-1] == 'E': P[-1] = 'S'
   elif P[-1] == 'W': P[-1] = 'N'
  else:
   i = int(i)
   if P[-1] == 'N': P[1] -= i
   elif P[-1] == 'S': P[1] += i
   elif P[-1] == 'E': P[0] += i
   elif P[-1] == 'W': P[0] -= i
  #print i, P
 DIST = sqrt(P[0]**2+P[1]**2)

 if P[0] == 0 and P[1] == 0: DIR = ''
 elif P[0] == 0 and P[1] < 0: DIR = 'S'
 elif P[0] == 0 and P[1] > 0: DIR = 'N'
 elif P[0] < 0 and P[1] == 0: DIR = 'E'
 elif P[0] < 0 and P[1] < 0: DIR = 'SE'
 elif P[0] < 0 and P[1] > 0: DIR = 'NE'
 elif P[0] > 0 and P[1] == 0: DIR = 'W'
 elif P[0] > 0 and P[1] < 0: DIR = 'SW'
 elif P[0] > 0 and P[1] > 0: DIR = 'NW'

 DIST = int(DIST*10.)/10. # TOLD NO APPROXIMATION

 return '%.1f%s' % (DIST, DIR)

def main():
 T = int(input())
 for t in range(T):
  S = input().split()
  print(process(S))

main()



import sys,math

t = int(sys.stdin.readline())
ds = [(0,1),(1,0),(0,-1),(-1,0)]
for _ in range(t):
 x, y, d = 0, 0, 0
 path = sys.stdin.readline().split()
 for ins in path:
  if ins == 'L':
   d = (d-1)&3
  elif ins == 'R':
   d = (d+1)&3
  else:
   x,y = x+ds[d][0]*int(ins), y+ds[d][1]*int(ins)
 dist = math.sqrt(float(x**2 + y**2))
 if y > 0:
  if x > 0:
   dir = 'NE'
  elif x < 0:
   dir = 'NW'
  else:
   dir = 'N'
 elif y < 0:
  if x > 0:
   dir = 'SE'
  elif x < 0:
   dir = 'SW'
  else:
   dir = 'S'
 else:
  if x > 0:
   dir = 'E'
  elif x < 0:
   dir = 'W'
  else:
   dir = ''
 print('%.1f%s' % (math.floor(dist*10)/10.0,dir))


#Program question at: http://www.codechef.com/COZL2012/problems/RBX12R01
import math,sys
dir_ = 'UDLR'
left = 'LRDU'
right = 'RLUD'

t = int(input())
while t>0:
 t -= 1
 x=0; y=0;
 dr = ''; cur='U';
 s = input().split()
 l = len(s)
 for i in range(l):
  if i % 2 == 1:
   dr = s[i]
   if dr == 'L': cur = left[dir_.find(cur)]
   else: cur = right[dir_.find(cur)]
  else:
   steps = int(s[i])
   if cur == 'U': y += steps
   elif cur == 'D': y -= steps
   elif cur == 'L': x -= steps
   elif cur == 'R': x += steps

 dist = str(math.sqrt(x*x + y*y))
 i = dist.find('.')
 sys.stdout.write(dist[0:i+2])
 if x==0:
  sys.stdout.write( ('N' if y>0 else 'S') + '\n')
 elif y==0:
  sys.stdout.write( ('E' if x>0 else 'W') + '\n')
 elif x>0:
  sys.stdout.write( ('NE' if y>0 else 'SE') + '\n')
 elif x<0:
   sys.stdout.write( ('NW' if y>0 else 'SW') + '\n')



#Program question at: http://www.codechef.com/COZL2012/problems/RBX12R01
import math,sys
dir_ = 'UDLR'
left = 'LRDU'
right = 'RLUD'

t = int(input())
while t>0:
 t -= 1
 x=0; y=0;
 dr = ''; cur='U';
 s = input().split()
 l = len(s)
 for i in range(l):
  if i % 2 == 1:
   dr = s[i]
   if dr == 'L': cur = left[dir_.find(cur)]
   else: cur = right[dir_.find(cur)]
  else:
   steps = int(s[i])
   if cur == 'U': y += steps
   elif cur == 'D': y -= steps
   elif cur == 'L': x -= steps
   elif cur == 'R': x += steps

 dist = str(math.sqrt(x*x + y*y))
 i = dist.find('.')
 sys.stdout.write(dist[0:i+2])
 if x==0:
  sys.stdout.write( ('N' if y>0 else 'S') + '\n')
 elif y==0:
  sys.stdout.write( ('E' if x>0 else 'W') + '\n')
 elif x>0:
  sys.stdout.write( ('NE' if y>0 else 'SE') + '\n')
 elif x<0:
   sys.stdout.write( ('NW' if y>0 else 'SW') + '\n')




def my_sqrt(v):
 v*=100
 lo=0
 hi=v
 while lo+1<hi:
  mi = (lo + hi) >> 1
  if mi*mi<=v:
   lo=mi
  else:
   hi=mi
 return lo

def solve():
 dir=0
 dx=[0,-1,0,1]
 dy=[1,0,-1,0]
 x,y=0,0
 line=input()
 ss=line.split()
 n=len(ss)
 i=0
 while(i<n):
  if(ss[i]=='L'):
   dir=(dir+1)%4
  elif ss[i]=='R':
   dir=(dir+3)%4
  else:
   x+=dx[dir]*int(ss[i])
   y+=dy[dir]*int(ss[i])
  i=i+1
 if x==0 and y==0:
  print('0.0')
  return
 v = my_sqrt(x*x+y*y)
 ds=''
 if(y>0):
  ds+='N'
 elif y<0:
  ds+='S'
 if(x>0):
  ds+='E'
 elif x<0:
  ds+='W'
 print('%d.%d%s' % (v/10, v%10,ds))

T=int(input())
while(T>0):
 T=T-1
 solve()

#input must be invalid because no runtime error after handling invalid input

def parse(movestr):
 moves = []
 acc = ""
 for char in movestr:
  char = char.upper()
  if char == "R" or char == "L":
   if acc != "":
    moves.append(int(acc))
   acc = ""
   moves.append(char)
  elif char.isdigit():
   acc += char
  elif len(acc) > 0:
   moves.append(int(acc))
   acc = ""
   
 if len(acc) > 0:
  moves.append(int(acc))
 return moves


def make_move(x,y,direc,dist):
 if direc == 0:
  #north
  y += dist
 elif direc == 1:
  #west
  x -= dist
 elif direc == 2:
  #south
  y -= dist
 elif direc == 3:
  #east
  x += dist
 return x,y


def calc(moves):
 x,y = 0,0
 direc = 0
 for move in moves:
  if move == "L":
   direc = (direc+1)%4
  elif move == "R":
   direc = (direc-1)%4
  else:
   x,y = make_move(x,y,direc,move)
 return x,y


def string(dist):
 d = str(dist)
 k = d.find(".")
 return d[:k+2]

cases = int(input())
for case in range(cases):
 movestr = input().replace(" ","")
 moves = parse(movestr)
 x,y = calc(moves)
 dist = (x**2 + y**2)**0.5
 
 if x == 0:
  if y == 0:
   direc = ""
  elif y < 0:
   direc = "S"
  else:
   direc = "N"
 elif x < 0:
  if y == 0:
   direc = "W"
  elif y < 0:
   direc = "SW"
  else:
   direc = "NW"
 else:
  if y == 0:
   direc = "E"
  elif y < 0:
   direc = "SE"
  else:
   direc = "NE"
 print("%s%s" %(string(dist),direc))