Problem Brief

Redeemable Promotion Offers

FULLTIMEPHONE SCREEN

You are given promotion offer definitions and user redemption events. Each offer string has the format offerId,startDate,endDate,maxRedeemsPerUser. Each event string has the format userId,date,action,offerId, where action is either redeem or unredeem.

For every user that appears in the event log, determine which offers they can still redeem on cutoffDate. An offer is redeemable if the cutoff date is within the offer's date range and the user's net redeemed count for that offer is less than maxRedeemsPerUser. Return one line per user in ascending user id order as userId:offerA,offerB, with offer ids sorted ascending. If no user can redeem any offer, return ["None"].

1Example 1

Input

offers = ["O1,2015-01-01,2015-12-31,2","O2,2015-06-01,2016-01-31,1"], events = ["u1,2015-07-01,redeem,O1","u1,2015-07-02,redeem,O1","u1,2015-08-01,redeem,O2","u1,2015-09-01,unredeem,O1","u2,2015-08-01,redeem,O1"], cutoffDate = "2015-12-31"

Output

["u1:O1","u2:O1,O2"]

Explanation

User u1 has one remaining redemption for O1 but none for O2. User u2 can redeem both active offers.

2Example 2

Input

offers = ["A,2015-01-01,2015-01-31,1"], events = ["u1,2015-01-02,redeem,A"], cutoffDate = "2015-12-31"

Output

["None"]

Explanation

The only offer has expired before the cutoff date.

Constraints

Limits and guarantees your solution can rely on.

Dates use ISO YYYY-MM-DD strings and can be compared lexicographically.