Cavli

Ο Mirko βρήκε μια ξύλινη σανίδα και ~N~ καρφιά στη σοφίτα του. Ο Mirko κάρφωσε τα καρφιά στη σανίδα όσο το δυνατόν πιο γρήγορα. Η σανίδα μπορεί να απεικωνιστεί ως ένα επίπεδο συντεταγμένων και τα καρφιά ως σημεία σε αυτό. Κανένα καρφί δεν έχει την ίδια συντεταγμένη ~x~ ή ~y~.
Για να συνεχίσει να διασκεδάζει, ο Mirko έκλεψε το λαστιχάκι μαλλιών της αδερφής του, το άπλωσε σε όλα τα καρφιά και μετά το άφησε. Το λαστιχάκι, φυσικά, έσφιξε γύρω από τα καρφιά.
Στη συνέχεια, ο Mirko επαναλαμβάνει αυτά τα βήματα ενώ υπάρχουν τουλάχιστον τρία καρφιά στον πίνακα:

1. Σημειώνει την περιοχή του σχήματος που περικλείεται από το λαστιχάκι.

2. Επιλέγει το αριστερότερο, το δεξιότερο, το πιο πάνω ή το πιο κάτω καρφί της σανίδας.

3. Αφαιρεί το επιλεγμένο καρφί από τη σανίδα. Το λαστιχάκι σφίγγει ξανά γύρω από τα υπόλοιπα καρφιά.

Γράψτε ένα πρόγραμμα που να υπολογίζει τους αριθμούς που γράφτηκαν στο βήμα 1 κάθε επανάληψης, αν γνωρίζουμε το καρφί που ο Mirko επιλέγει στο βήμα 2 κάθε επανάληψης.

Είσοδος

Η πρώτη γραμμή περιέχει τον ακέραιο αριθμό ~N (3 \le N \le 300\,000)~, τον αριθμό των καρφιών.
Κάθε μία από τις ακόλουθες ~N~ γραμμές περιέχει δύο ακέραιους αριθμούς που χωρίζονται από ένα κενό, τις συντεταγμένες ενός καρφιού. Ολες οι συντεταγμένες θα είναι μεταξύ του ~1~ και του ~1\,000\,000\,000~. Κανένα καρφί δεν θα έχει την ίδια συντεταγμένη ~x~ ή ~y~.
Η επόμενη γραμμή περιέχει ~N-2~ γράμματα ~L, R, U~ ή ~D~. Τα γράμματα αντιπροσωπεύουν τα καρφιά που πήρε ο Mirko με τη σειρά:

• ~'L'~ για το αριστερότερο καρφί (μικρότερη συντεταγμένη ~x~ (τετμημένη) ),
  
• ~'R'~ για το πιο δεξιότερο καρφί (μεγαλύτερη συντεταγμένη ~x~),
  
• ~'U'~ για το πιο πάνω καρφί (μεγαλύτερη συντεταγμένη ~y~ (τεταγμένη) ),
  
• ~'D'~ για το πιο κάτω καρφί (μικρότερη συντεταγμένη ~y~).

Έξοδος

Τυπώστε ~N-2~ αριθμούς, τον καθένα σε ξεχωριστή γραμμή. Οι αριθμοί είναι κατά σειρά οι περιοχές που σημείωσε ο Mirko. Τυπώστε τους αριθμούς με ένα ψηφίο μετά την υποδιαστολή.

Βαθμολογία

Στα αρχεία ελέγχου αξίας ~50%~ των πόντων, το ~N~ θα είναι μικρότερο από ~1\,000~.

Παραδείγματα

input

5
1 4
2 2
4 1
3 5
5 3
LUR

output

9.0
6.5
2.5

input

8
1 6
2 4
3 1
4 2
5 7
6 5
7 9
8 3
URDLUU

output

34.0
24.0
16.5
14.0
9.5
5.0

Οι παρακάτω εικόνες απεικονίζουν την κατάσταση πριν από καθένα από τα 6 βήματα στο δεύτερο παράδειγμα.