JC15B - Folding Stick

Folding Stick

Today Satria really excited about fractals (recurrence pattern), the first fractal type he learn is the dragon curve fractal. To make the dragon curve, it can be easily simulated by folding the paper and open it 90 degrees (parellel to X axis or Y axis) like this image below:

Satria realized that the can be many ways to fold the paper, so he make an experiment. Initially there is a stick length 2N, he then place the stick parallel to x axis with one end lies on coordinate (0,0) and the other end lies on coordinate (2N,0). He then fold the stick, so the new folded stick occupy (0,0) to (2N-1,0) he keep doing that until the final folded stick occupy (0,0) to (1,0). In each foding there are two types of folding, folding UP (via possitive Y coordinate) and folding down (via negative Y coordinate). he then open all the folding with angle 90 degrees so each stick segment will be parallel ot X axis or Y axis. Now he wonder if he open all the folding with angle 90 degrees, what is the coordinate of the other end of that stick. Can you help him?

Input

The first line there is an integer N denoting number of folding and a string S the sequence of folding and the type of folding.

Output

You sould output two integers x and y which is the coordinate of the other end of that stick.

Constraint

1 ≤ N ≤ 50

Length of string S is equal to N, in other word: |S|=N.

String S containing two possible characters:

  • 'U' means folding UP (positive Y direction)
  • 'D' means folding DOWN (negative Y direction)

Sample 1

Input

1 U

Output

1 1

Sample 2

Input

1 D

Output

1 -1

Sample 3

Input

2 UD

Output

2 0

Sample 4

Input

2 DU

Output

2 0

Sample 5

Input

3 UUU

Output

-2 2

Sample 3 Explanation

Here is the image illustrating sample 3 on how the stick is folded and openned with 90 degrees angle. 

As seen in the picture above the other end of the stick after folding and openning lies on coordinate (2,0).

Sample 5 explanation

Here is the final openned stick on test case 5, the other end of the stick after folding and openning lies on coordinate (-2,2)


Added by:Tjandra Satria Gunawan
Date:2016-01-18
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Own Problem, used in Jolly Challenge #15

hide comments
2021-12-16 16:12:50 David
Just by reading the number of "U" and "D" values, there is an interesting O(1) solution!
2019-01-02 08:45:45
Nice Problem!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.