Endor

Στο γεμάτο δάσος φεγγάρι του Έντορ υπάρχει, αν θέλουμε να πιστέψουμε το βιβλίο των ρεκόρ Γκίνες, το μακρύτερο ραβδί σε ολόκληρο τον γαλαξία. Σε αυτό το ραβδί μήκους ~L~ μέτρων υπάρχουν ~N~ χαρούμενοι χαμαιλέοντες. Κάθε χαμαιλέοντας κινείται κατά μήκος του ραβδιού με σταθερή ταχύτητα ~1\;m/s~ σε μία από τις δύο πιθανές κατευθύνσεις (αριστερά ή δεξιά) και είναι χρωματισμένος σε ένα από τα πιθανά ~K~ χρώματα.

Είναι γνωστό ότι οι χαμαιλέοντες του Έντορ λατρεύουν τους αρχαίους νόμους των μυρμηγκιών που υπαγορεύουν ότι η βόλτα κατά μήκος του ραβδιού πρέπει να συνεχιστεί μέχρι να φτάσει το άκρο του ραβδιού (που σημαίνει να κατέβει από αυτό), και όταν συμβεί σύγκρουση με άλλον χαμαιλέοντα, πρέπει να στρίψουν 180 μοίρες και να συνεχίσουν το περπάτημα προς την αντίθετη κατεύθυνση. Επιπλέον, αφού ένας χαμαιλέοντας χρώματος ~a~ κινούμενος προς τα αριστερά συγκρούεται με έναν χαμαιλέοντα χρώματος ~b~ που κινείται προς τα δεξιά, ο χαμαιλέοντας που κινείται προς τα αριστερά πριν από τη σύγκρουση παίρνει το χρώμα του χαμαιλέοντα που κινείται προς τα δεξιά πριν από τη σύγκρουση (έτσι, χρώμα ~b~), ενώ ο χαμαιλέοντας που κινείται προς τα δεξιά πριν από τη σύγκρουση παίρνει νέο χρώμα ~(a + b) mod K~.

Εάν σας δοθούν οι αρχικές θέσεις, τα χρώματα και οι κατευθύνσεις κίνησης όλων των χαμαιλεόντων, για κάθε χρώμα καθορίστε το συνολικό ταξίδι που έκαναν οι χαμαιλέοντεςαυτπύ του χρώματος πριν κατεβείτε από το ραβδί.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τους ακέραιους αριθμούς ~N~, ~K~ και ~L\;(1 \leq N \leq 100\,000,\;1 \leq K \leq 40,\;1 \leq L \leq 1\,000\,000)~ από την εργασία. Η ~i~-οστή από τις ακόλουθες ~N~ γραμμές περιέχει τον ακέραιο αριθμό ~d_i\;(0 \leq d_i \leq L)~ που υποδηλώνει την απόσταση μεταξύ του ~i~-οστού χαμαιλέοντα και του αριστερού άκρου του ραβδιού και, στη συνέχεια, τον ακέραιο ~b_i\;(0 \leq b_i \leq K-1)~ που υποδηλώνει το χρώμα του ~i~-οστού χαμαιλέοντα και τον χαρακτήρα "~L~" (αριστερά) ή "~D~" (δεξιά) που υποδηλώνουν την κατεύθυνση κίνησης του ~i~-οστού χαμαιλέοντα. Όλοι οι ακέραιοι αριθμοί ~d_i~ θα είναι μοναδικοί και θα δίνονται με αυστηρά αύξουσα σειρά.

Έξοδος

Η έξοδος πρέπει να περιέχει ~K~ γραμμές, με την i-οστή γραμμή να περιέχει το συνολικό ταξίδι που έκαναν οι χαμαιλέοντες του ~i~ χρώματος .

Βαθμολογία

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

input

2 3 10
0 0 D
10 1 L

output

10.0
10.0
0.0

Επεξήγηση του 1ου παραδείγματος:

Οι χαμαιλέοντες συγκρούονται μετά από 5 διανυόμενα μέτρα στη μέση του ραβδιού. Μετά από αυτό, και οι δύο χαμαιλέοντες αλλάζουν την κατεύθυνση της κίνησής τους. Ο χαμαιλέοντας που κινείται προς τα δεξιά μετά από σύγκρουση χρωματίζεται με 0, ενώ ο χαμαιλέοντας που κινείται προς τα αριστερά μετά από σύγκρουση χρωματίζεται με 1.

input

4 3 7
1 0 D
3 0 D
4 1 L
6 2 D

output

10.0
4.0
1.0

input

4 4 5
1 1 D
3 3 L
4 2 D
5 0 L

output

2.5
4.0
2.5
4.0