You are given integers n and t, and arrays keys and times of the same length describing a stream of events in chronological order (timestamps are non-decreasing): event i has key keys[i] and timestamp times[i].

Each event is either admitted or denied, decided in order:

• Event i is admitted if fewer than n events with the same key have been admitted in the half-open time window (times[i] - t, times[i]].
• Otherwise it is denied. Denied events never count toward any window.

Keys are independent of each other. Return an array with 1 for each admitted event and 0 for each denied event, in input order.

Note that an admitted event at time times[i] - t has just expired and does not count toward the window, while one at times[i] (the same timestamp) does.

Examples

Example 1

Input: n = 1, t = 10, keys = ["u","u","u","u"], times = [1,2,11,12]
Output: [1,0,1,0]
Explanation: The event at time 1 is admitted. At time 2, the window (-8, 2] already holds one admitted event. At time 11, the window (1, 11] is empty again (the event at time 1 expired), so it is admitted. At time 12, the admitted event at 11 blocks it.