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)

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
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
	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.0) / 10.0
	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'
	elif x > 0:
		dir = 'E'
	elif x < 0:
		dir = 'W'
	else:
		dir = ''
	print('%.1f%s' % (math.floor(dist * 10) / 10.0, dir))


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


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:
		y += dist
	elif direc == 1:
		x -= dist
	elif direc == 2:
		y -= dist
	elif direc == 3:
		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'
	elif y == 0:
		direc = 'E'
	elif y < 0:
		direc = 'SE'
	else:
		direc = 'NE'
	print('%s%s' % (string(dist), direc))