Redeemable Promotion Offers

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"].

Constraints

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

Example 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.

Example 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.