You are given a chronological log of user activity. Each entry is a (timestamp, user) pair, and the timestamps arrive in non-decreasing order.

Implement active_users(logs, window), which reports — at the moment each log entry occurs — how many distinct users were active during the last window units of time.

Input

logs = [
    (1, "A"),
    (2, "B"),
    (3, "A"),
    (7, "C"),
    (8, "A"),
]

• Each entry is a (timestamp, user) pair.
• Timestamps arrive in non-decreasing order.
• The same user may appear many times.
• window is an integer of at least 1.

Output

Return a list the same length as the input. The i-th value is the number of distinct users appearing within the recent window interval, measured from the i-th entry's timestamp.

active_users(logs, 5)
# [1, 2, 2, 2, 2]

Walking through each result:

• timestamp 1: only A → 1 user
• timestamp 2: A and B → 2 users
• timestamp 3: A, B, A were active → the distinct users are A and B → 2
• timestamp 7: the last 5 units are (2, 7], so only the entries at 3 and 7 count → A, C → 2
• timestamp 8: the last 5 units are (3, 8], so the entries at 3, 7, 8 count → A, C, A → 2

Defining the interval

With the current timestamp written as t, the interval you inspect is:

(t - window, t]

• The left end is excluded.
• The right end — the current moment t — is included.

For example with window = 5 and t = 7 the interval is (2, 7], so an entry at timestamp 2 is excluded while entries at 3, 4, 5, 6, 7 are included.

Things to watch

1. A user appearing several times inside the interval still counts once.
2. With window = 1 the interval is (t - 1, t], so only entries sharing the current timestamp can fall inside it.
3. If several entries share a timestamp, all of them belong to the current interval.
4. Empty input returns an empty list.

Implement active_users(logs, window).