A neighborhood coffee subscription club logs every order its members place, each order tagged with the billing cycle it fell in. Membership renewal is offered only to members who prove they are actively engaged: a member qualifies for renewal only if their total order value (quantity multiplied by unit price, summed over every order they placed in that cycle) reaches at least a renewal threshold in BOTH of two specified cycles — cycle A and cycle B. Orders placed in any other cycle should be ignored for this check. Each member id always maps to exactly one member name across all of their orders. Given the full order log, the renewal threshold, and the two cycle tags, report every qualifying member.

Input format

Line 1: four space-separated tokens: n threshold cycleA cycleB — n is the number of order records, threshold is the minimum required cycle spend, and cycleA / cycleB are the two cycle tags to check (cycleA != cycleB). Next n lines: each contains five space-separated tokens: id name cycle quantity price — the member id, member name, the cycle tag this order was placed in, the quantity of items ordered, and the price per item.

Output format

Print one line per qualifying member, formatted as "id name", ordered by ascending id. A member qualifies only if their total order value in cycleA is >= threshold AND their total order value in cycleB is >= threshold. Print nothing if no member qualifies.

Constraints

• 1 <= n <= 2000
• 1 <= threshold <= 10^9
• 1 <= id <= 100000
• name and cycle are tokens of 1 to 20 characters using only letters, digits, and underscores
• cycleA != cycleB
• 1 <= quantity <= 1000
• 1 <= price <= 1000000
• A given id is always paired with the same name across every record in the input

6 100 M6 M7
1 Alice M6 5 10
1 Alice M6 5 10
1 Alice M7 2 60
2 Bob M6 1 50
2 Bob M7 3 50
3 Cara M6 10 20

1 Alice

4 1000 X Y
1 Dave X 2 10
1 Dave Y 2 10
2 Eve X 100 50
2 Eve Y 1 5

(empty)