Session Duration Window
An analytics service computes the count of distinct active sessions inside a fixed rolling time window (e.g. the last 10 minutes). It receives an ordered stream of session start timestamps and a stream of queries (each at a timestamp); for each query, return the number of sessions whose start_time is in (query_time − w, query_time].
Problem
Given a sorted (ascending) array of session start timestamps and an integer window w, plus a sorted (ascending) array of query timestamps, return for each query q the number of starts strictly greater than q − w and at most q.
Input
Integers n (1 ≤ n ≤ 10^5) and m (1 ≤ m ≤ 10^5), and integer w (1 ≤ w ≤ 10^9). Two arrays sorted ascending: starts (each in [0, 10^9]) and queries (each in [0, 10^9]).
Output
An array of m integers — the count for each query in input order.
Constraints
- 1 ≤ n, m ≤ 100,000
- 1 ≤ w ≤ 10^9
- starts and queries are sorted ascending (queries form a monotonic time axis)
- Output preserves the query order
Examples
Example 1
Input
starts = [1, 4, 7, 10, 12], queries = [5, 10, 12], w = 3
Output
[1, 1, 2]
Query 5: window is (2, 5] → only start 4 qualifies → 1. Query 10: window is (7, 10] → only start 10 qualifies → 1. Query 12: window is (9, 12] → starts 10 and 12 qualify → 2.
Example 2
Input
starts = [2, 2, 5, 8], queries = [4, 9], w = 5
Output
[2, 2]
Query 4: window is (-1, 4] → both starts at 2 qualify → 2. Query 9: window is (4, 9] → starts 5 and 8 qualify → 2.