Most of you have been to newly built Khulna Railway Station. Let's say there is only one ticket counter in the station. The ticket counter has a booking clerk to distribute tickets and two separate queues in front of it, one for male and other for female customers. Generally male queue is more busy, so the rule of the station is to serve 1 female customer after every 2 consecutive male customer. But the size of queues are not guaranteed for any moment. If both queues are sufficiently large then the order might be, $FMMFMMFMMF...$ or $MMFMMFMMFMM...$ based on the arrival sequence in queues.
If it's turn to serve any queue which is empty, then the other queue is served. So, if it’s turn for the female queue and is found empty, then 1 customers will be taken from male queue and after that female queue will be checked if any customer arrived or not. Same happens for an empty male queue. Checking and switching between queues takes no time. Both the queues may be empty at the same time. In that case, first customer to come will be served.
Two types of tickets can be booked in the station, AC and Non-AC. AC tickets need $x$ seconds and Non-AC tickets need $y$ seconds to be booked. Booking Clerk can only book 1 ticket at a time. If a booking started, it needs to be finished before starting another booking. One customer can book exactly one ticket. After the booking is finished he/she leaves immediately.
So, if someone starts booking an AC ticket at $t$-th second, he/she will finish booking on $(t+x-1)$-th second. Next customer can start booking at $(t+x)$-th second. Similarly a Non-AC ticket booking starting at $t$-th second will finish on $(t+y-1)$-th second and next booking can start at $(t+y)$-th second.
Male customers will stand at the male queue and female customers at the female queue. The $i$-th customer will arrive at $A_i$-th second, and can start booking from the second of his/her arrival if he/she is at the front of the respective queue and that queue is currently being served.
Now given the information of n customers including you, you have to calculated how much time you have to wait before you finish your booking. Don't be worried, we will define whether you are a male or a female customer.
Input
First line will contain the number of test cases $T$.
First line of each test case will contain $n$, $x$, $y$ and $C$.
Where $n$ is the number of customers, $x$ is time needed to book AC ticket, $y$ is time needed to book Non-AC ticket and $C$ equals M if you are a male customer or F if you are a female customer.
Next $n$ lines of test case describe a customer with $C_i$, $A_i$ and $S_i$.$C_i$ is M for male, F for female and U if $i$-th customer is you. $A_i$ is arrival time of the customer. $S_i$ is the type of ticket $i$-th customer wants to book, A for AC and N for non-AC.
Constraints
- 1 <= T <= 10
- 1 <= n <= 105
- 1 <= x <= 105
- 1 <= y <= 105
- 1 <= Ai <= 106 will be distinct
- There will be exactly
$1$customer where$C_i$is U
Output
Output a single line "Case t: D", where $t$ is the number of test case and $D$ is the amount of time you have to wait from your arrival until you finish booking.
Sample
| Input | Output |
|---|---|
3 4 3 2 M F 1 A M 2 N F 3 A U 4 N 5 4 2 F F 2 A M 1 N M 4 N U 10 N M 11 A 3 5 4 F F 1 N M 3 A U 2 A | Case 1: 4 Case 2: 2 Case 3: 13 |
