A transit operator instruments every turnstile in its network and streams each tap to a loyalty analytics pipeline. Each tap record names the rider, the calendar date, and whether it was a tap-in (IN) or a tap-out (OUT); only tap-ins matter for this report, and a rider may appear many times across their history. The operator wants a daily "new rider" report: for each date in the 90-day window ending on a given report date (inclusive), how many riders tapped in for the very first time — ever, across their complete history — on that exact date? A rider's first tap-in might have happened long before the window opened, in which case they never appear in the report at all.

Input format

• Line 1: the report date today, formatted YYYY-MM-DD.
• Line 2: a single integer n, the number of tap records.
• Each of the next n lines contains a tap record riderId date type, where riderId is an alphanumeric token, date is formatted YYYY-MM-DD, and type is either IN or OUT.

Output format

Print exactly 90 lines, one for each calendar date from today minus 89 days through today, in ascending chronological order. Each line has the form date count, where count is the number of riders whose earliest-ever IN tap (considering their complete history, not just records inside the window) falls exactly on that date. Dates with no qualifying riders still print count = 0.

Constraints

• 1 <= n <= 200000
• riderId consists of 1 to 12 letters and/or digits.
• Every date, including today, is a valid calendar date between 2000-01-01 and 2100-12-31.
• type is exactly IN or OUT.
• No record's date is later than today.
• The same rider may appear in multiple records, including multiple IN records.

2021-01-05
5
alice 2021-01-01 IN
bob 2021-01-02 IN
alice 2021-01-02 OUT
alice 2021-01-03 IN
carol 2021-01-05 IN

2020-10-08 0
2020-10-09 0
2020-10-10 0
2020-10-11 0
2020-10-12 0
2020-10-13 0
2020-10-14 0
2020-10-15 0
2020-10-16 0
2020-10-17 0
2020-10-18 0
2020-10-19 0
2020-10-20 0
2020-10-21 0
2020-10-22 0
2020-10-23 0
2020-10-24 0
2020-10-25 0
2020-10-26 0
2020-10-27 0
2020-10-28 0
2020-10-29 0
2020-10-30 0
2020-10-31 0
2020-11-01 0
2020-11-02 0
2020-11-03 0
2020-11-04 0
2020-11-05 0
2020-11-06 0
2020-11-07 0
2020-11-08 0
2020-11-09 0
2020-11-10 0
2020-11-11 0
2020-11-12 0
2020-11-13 0
2020-11-14 0
2020-11-15 0
2020-11-16 0
2020-11-17 0
2020-11-18 0
2020-11-19 0
2020-11-20 0
2020-11-21 0
2020-11-22 0
2020-11-23 0
2020-11-24 0
2020-11-25 0
2020-11-26 0
2020-11-27 0
2020-11-28 0
2020-11-29 0
2020-11-30 0
2020-12-01 0
2020-12-02 0
2020-12-03 0
2020-12-04 0
2020-12-05 0
2020-12-06 0
2020-12-07 0
2020-12-08 0
2020-12-09 0
2020-12-10 0
2020-12-11 0
2020-12-12 0
2020-12-13 0
2020-12-14 0
2020-12-15 0
2020-12-16 0
2020-12-17 0
2020-12-18 0
2020-12-19 0
2020-12-20 0
2020-12-21 0
2020-12-22 0
2020-12-23 0
2020-12-24 0
2020-12-25 0
2020-12-26 0
2020-12-27 0
2020-12-28 0
2020-12-29 0
2020-12-30 0
2020-12-31 0
2021-01-01 1
2021-01-02 1
2021-01-03 0
2021-01-04 0
2021-01-05 1

2019-06-30
3
zeke 2019-01-01 IN
yara 2019-04-02 IN
xavier 2019-06-30 IN