def merge_busy(intervals):
    from heapq import heappush, heappop

    if not intervals:
        return []

    starts = {}
    coords = set()

    for start, end, prio in intervals:
        coords.add(start)
        coords.add(end)
        starts.setdefault(start, []).append((end, prio))

    coords = sorted(coords)
    heap = []
    result = []

    for i, x in enumerate(coords):
        for end, prio in starts.get(x, ()):
            heappush(heap, (-prio, end))

        while heap and heap[0][1] <= x:
            heappop(heap)

        if i + 1 < len(coords) and heap:
            y = coords[i + 1]
            prio = -heap[0][0]

            if result and result[-1][1] == x and result[-1][2] == prio:
                result[-1] = (result[-1][0], y, prio)
            else:
                result.append((x, y, prio))

    return result

import heapq
from collections import defaultdict

def merge_busy(intervals):
    if not intervals:
        return []
    events = []
    for s, e, p in intervals:
        events.append((s, 1, p))
        events.append((e, -1, p))
    events.sort(key=lambda x: (x[0], -x[1]))
    active_count = defaultdict(int)
    heap = []
    result = []
    last_time = None
    last_max = None
    i = 0
    n = len(events)
    while i < n:
        curr_t = events[i][0]
        if last_time is not None and curr_t > last_time:
            if last_max is not None:
                result.append((last_time, curr_t, last_max))
        while i < n and events[i][0] == curr_t:
            _, delta, p = events[i]
            if delta == 1:
                active_count[p] += 1
                heapq.heappush(heap, -p)
            else:
                active_count[p] -= 1
            i += 1
        while heap and active_count[-heap[0]] <= 0:
            heapq.heappop(heap)
        new_max = -heap[0] if heap else None
        last_time = curr_t
        last_max = new_max
    if not result:
        return []
    merged = [list(result[0])]
    for curr in result[1:]:
        if merged[-1][1] == curr[0] and merged[-1][2] == curr[2]:
            merged[-1][1] = curr[1]
        else:
            merged.append(list(curr))
    return [tuple(m) for m in merged]

def merge_busy(intervals):
    import heapq

    if not intervals:
        return []

    # events: (time, type, prio) with type 0 = end, 1 = start
    events = []
    for s, e, p in intervals:
        events.append((s, 1, p))
        events.append((e, 0, p))

    # end (0) before start (1) at same time
    events.sort(key=lambda x: (x[0], x[1]))

    # sorted unique time points
    times = sorted({t for t, _, _ in events})

    active_count = 0
    count = {}
    heap = []  # max-heap of priorities (stored as negative values)
    raw_segments = []

    idx = 0
    n_events = len(events)

    for i, t in enumerate(times):
        # process all events at time t
        while idx < n_events and events[idx][0] == t:
            _, typ, p = events[idx]
            if typ == 0:          # end
                count[p] -= 1
                if count[p] == 0:
                    del count[p]
                active_count -= 1
            else:                 # start
                count[p] = count.get(p, 0) + 1
                if count[p] == 1:
                    heapq.heappush(heap, -p)
                active_count += 1
            idx += 1

        # if this is the last time point, there is no next segment
        if i == len(times) - 1:
            break

        next_t = times[i + 1]
        if active_count > 0:
            # lazy removal of dead heap tops
            while heap and count.get(-heap[0], 0) == 0:
                heapq.heappop(heap)
            cur_max = -heap[0]
            raw_segments.append((t, next_t, cur_max))

    # coalesce adjacent segments with equal priority
    merged = []
    for seg in raw_segments:
        if not merged:
            merged.append(seg)
        else:
            prev = merged[-1]
            if prev[1] == seg[0] and prev[2] == seg[2]:
                merged[-1] = (prev[0], seg[1], seg[2])
            else:
                merged.append(seg)

    return merged

def merge_busy(intervals):
    from collections import Counter
    if not intervals:
        return []
    events = {}
    for s, e, p in intervals:
        events.setdefault(s, []).append((p, 1))
        events.setdefault(e, []).append((p, -1))
    points = sorted(events)
    active = Counter()
    result = []
    prev = None
    for x in points:
        if prev is not None and active:
            prio = max(active)
            if result and result[-1][1] == prev and result[-1][2] == prio:
                result[-1] = (result[-1][0], x, prio)
            else:
                result.append((prev, x, prio))
        for p, d in events[x]:
            active[p] += d
            if active[p] == 0:
                del active[p]
        prev = x
    return result

def merge_busy(intervals):
    if not intervals:
        return []

    points = sorted(set(s for s, e, p in intervals) | set(e for s, e, p in intervals))

    segments = []
    for i in range(len(points) - 1):
        a, b = points[i], points[i + 1]
        max_prio = None
        for s, e, p in intervals:
            if s <= a and e >= b:
                if max_prio is None or p > max_prio:
                    max_prio = p
        if max_prio is not None:
            segments.append((a, b, max_prio))

    merged = []
    for seg in segments:
        if merged and merged[-1][1] == seg[0] and merged[-1][2] == seg[2]:
            merged[-1] = (merged[-1][0], seg[1], merged[-1][2])
        else:
            merged.append(list(seg))

    return [tuple(seg) for seg in merged]

def merge_busy(intervals):
    if not intervals:
        return []
    from collections import Counter
    starts, ends, coords = {}, {}, set()
    for s, e, p in intervals:
        coords.add(s)
        coords.add(e)
        starts.setdefault(s, []).append(p)
        ends.setdefault(e, []).append(p)
    xs = sorted(coords)
    active = Counter()
    segments = []
    for i, x in enumerate(xs):
        for p in ends.get(x, []):
            active[p] -= 1
            if active[p] == 0:
                del active[p]
        for p in starts.get(x, []):
            active[p] += 1
        if i + 1 < len(xs) and active:
            segments.append((x, xs[i + 1], max(active)))
    result = []
    for seg in segments:
        if result and result[-1][1] == seg[0] and result[-1][2] == seg[2]:
            result[-1] = (result[-1][0], seg[1], seg[2])
        else:
            result.append(seg)
    return result

import heapq
from collections import defaultdict


def merge_busy(intervals):
    if not intervals:
        return []

    xs = set()
    starts = defaultdict(list)
    for s, e, p in intervals:
        xs.add(s)
        xs.add(e)
        starts[s].append((-p, e))

    sorted_xs = sorted(xs)
    heap = []
    res = []

    for i in range(len(sorted_xs) - 1):
        x_curr = sorted_xs[i]
        x_next = sorted_xs[i + 1]

        if x_curr in starts:
            for item in starts[x_curr]:
                heapq.heappush(heap, item)

        while heap and heap[0][1] <= x_curr:
            heapq.heappop(heap)

        if heap:
            cur_prio = -heap[0][0]
            if res and res[-1][1] == x_curr and res[-1][2] == cur_prio:
                res[-1] = (res[-1][0], x_next, cur_prio)
            else:
                res.append((x_curr, x_next, cur_prio))

    return res

def merge_busy(intervals):
    if not intervals:
        return []

    events = []
    for start, end, prio in intervals:
        if start < end:
            events.append((start, 1, prio))
            events.append((end, -1, prio))

    if not events:
        return []

    events.sort(key=lambda x: x[0])

    from heapq import heappush, heappop

    active = []
    # Using a dictionary to track counts for lazy deletion in heap
    # But since priorities can be any int, we can use a frequency map and max-heap
    from collections import defaultdict

    counts = defaultdict(int)
    # We need to efficiently get the max priority.
    # Since Python's heapq is a min-heap, we can store negative priorities.
    max_heap = []
    removed = defaultdict(int)

    def add_prio(p):
        counts[p] += 1
        heappush(max_heap, -p)

    def remove_prio(p):
        counts[p] -= 1
        removed[p] += 1
        while max_heap and removed[-max_heap[0]] > 0:
            top = -heappop(max_heap)
            removed[top] -= 1

    def get_max_prio():
        while max_heap and removed[-max_heap[0]] > 0:
            top = -heappop(max_heap)
            removed[top] -= 1
        return -max_heap[0] if max_heap else None

    res = []
    n = len(events)
    i = 0
    while i < n:
        cur_x = events[i][0]
        # Process all events at cur_x
        while i < n and events[i][0] == cur_x:
            _, typ, p = events[i]
            if typ == 1:
                add_prio(p)
            else:
                remove_prio(p)
            i += 1

        if i < n:
            next_x = events[i][0]
            if cur_x < next_x:
                prio = get_max_prio()
                if prio is not None:
                    res.append((cur_x, next_x, prio))

    if not res:
        return []

    # Coalesce adjacent segments with the same priority
    coalesced = [res[0]]
    for start, end, prio in res[1:]:
        last_start, last_end, last_prio = coalesced[-1]
        if last_end == start and last_prio == prio:
            coalesced[-1] = (last_start, end, prio)
        else:
            coalesced.append((start, end, prio))

    return coalesced

def merge_busy(intervals):
    import heapq
    from collections import defaultdict

    starts = defaultdict(list)
    ends = defaultdict(list)
    for s, e, p in intervals:
        starts[s].append(p)
        ends[e].append(p)

    points = sorted(set(starts) | set(ends))
    active = defaultdict(int)   # prio -> number of intervals currently covering
    heap = []                   # max-heap of prios, lazily cleaned
    out = []

    for i in range(len(points) - 1):
        x, nxt = points[i], points[i + 1]

        for p in ends.get(x, ()):
            active[p] -= 1
        for p in starts.get(x, ()):
            if active[p] == 0:
                heapq.heappush(heap, -p)
            active[p] += 1

        while heap and active[-heap[0]] == 0:
            heapq.heappop(heap)
        if not heap:
            continue

        top = -heap[0]
        if out and out[-1][1] == x and out[-1][2] == top:
            out[-1] = (out[-1][0], nxt, top)
        else:
            out.append((x, nxt, top))

    return out

def merge_busy(intervals):
    if not intervals:
        return []

    events = []
    for s, e, p in intervals:
        events.append((s, 0, p))
        events.append((e, 1, p))
    events.sort()

    counts = {}
    result = []
    i = 0
    n = len(events)

    while i < n:
        coord = events[i][0]
        j = i
        while j < n and events[j][0] == coord:
            if events[j][1] == 1:
                p = events[j][2]
                counts[p] -= 1
                if counts[p] == 0:
                    del counts[p]
            j += 1
        j = i
        while j < n and events[j][0] == coord:
            if events[j][1] == 0:
                p = events[j][2]
                counts[p] = counts.get(p, 0) + 1
            j += 1
        i = j

        if i < n:
            next_coord = events[i][0]
            if counts:
                m = max(counts)
                if result and result[-1][2] == m and result[-1][1] == coord:
                    result[-1] = (result[-1][0], next_coord, m)
                else:
                    result.append((coord, next_coord, m))

    return result

def merge_busy(intervals):
    import heapq

    events = {}
    for index, (start, end, prio) in enumerate(intervals):
        events.setdefault(start, [[], []])[1].append((prio, index))
        events.setdefault(end, [[], []])[0].append(index)

    active = set()
    heap = []
    result = []
    previous = None

    for point in sorted(events):
        if previous is not None and previous < point:
            while heap and heap[0][1] not in active:
                heapq.heappop(heap)
            if heap:
                prio = -heap[0][0]
                if result and result[-1][1] == previous and result[-1][2] == prio:
                    result[-1] = (result[-1][0], point, prio)
                else:
                    result.append((previous, point, prio))

        endings, starts = events[point]
        for index in endings:
            active.discard(index)
        for prio, index in starts:
            active.add(index)
            heapq.heappush(heap, (-prio, index))

        previous = point

    return result

def merge_busy(intervals):
    events = {}

    for start, end, prio in intervals:
        events.setdefault(start, [[], []])[0].append(prio)
        events.setdefault(end, [[], []])[1].append(prio)

    if not events:
        return []

    active = {}
    result = []
    points = sorted(events)

    for i, point in enumerate(points):
        if i > 0 and active:
            start = points[i - 1]
            end = point
            prio = max(active)
            if result and result[-1][1] == start and result[-1][2] == prio:
                result[-1] = (result[-1][0], end, prio)
            else:
                result.append((start, end, prio))

        starts, ends = events[point]

        for prio in ends:
            active[prio] -= 1
            if active[prio] == 0:
                del active[prio]

        for prio in starts:
            active[prio] = active.get(prio, 0) + 1

    return result

def merge_busy(intervals):
    events = {}
    for start, end, prio in intervals:
        events.setdefault(start, []).append((1, prio))
        events.setdefault(end, []).append((-1, prio))

    if not events:
        return []

    active = {}
    result = []
    previous = None

    for point in sorted(events):
        if previous is not None and previous < point and active:
            prio = max(active)
            if result and result[-1][1] == previous and result[-1][2] == prio:
                result[-1] = (result[-1][0], point, prio)
            else:
                result.append((previous, point, prio))

        for change, prio in events[point]:
            active[prio] = active.get(prio, 0) + change
            if active[prio] == 0:
                del active[prio]

        previous = point

    return result

class TokenBucket:
    def __init__(self, capacity: float, refill_rate: float) -> None:
        self.capacity = float(capacity)
        self.refill_rate = float(refill_rate)
        self._tokens = float(capacity)
        self._last_now = None

    def allow(self, n: float = 1.0, now: float = 0.0) -> bool:
        now = float(now)

        if self._last_now is None:
            self._last_now = now
        elif now > self._last_now:
            elapsed = now - self._last_now
            self._tokens = min(self.capacity, self._tokens + elapsed * self.refill_rate)
            self._last_now = now

        if self._tokens >= n:
            self._tokens -= n
            return True

        return False

class TokenBucket:
    def __init__(self, capacity: float, refill_rate: float):
        self.capacity = capacity
        self.refill_rate = refill_rate
        self.tokens = capacity  # starts FULL
        self.last_time = None

    def allow(self, n: float = 1.0, now: float = 0.0) -> bool:
        if self.last_time is not None:
            elapsed = max(0.0, now - self.last_time)
            self.tokens = min(self.capacity, self.tokens + elapsed * self.refill_rate)
        else:
            # First call: no refill, establish baseline
            pass

        if self.tokens >= n:
            self.tokens -= n
            self.last_time = now
            return True
        else:
            self.last_time = now
            return False

class TokenBucket:
    def __init__(self, capacity: float, refill_rate: float):
        self.capacity = capacity
        self.refill_rate = refill_rate
        self.tokens = capacity          # starts FULL
        self.last_time = None           # no baseline yet

    def allow(self, n: float = 1.0, now: float = 0.0) -> bool:
        if self.last_time is None:
            # First call: establish baseline, no refill
            self.last_time = now
        else:
            elapsed = now - self.last_time
            if elapsed < 0:
                elapsed = 0.0           # don't go backwards
            # Continuous refill, capped at capacity
            self.tokens = min(self.capacity,
                              self.tokens + elapsed * self.refill_rate)
            self.last_time = now

        if self.tokens >= n:
            self.tokens -= n
            return True
        return False

class TokenBucket:
    def __init__(self, capacity: float, refill_rate: float):
        self.capacity = capacity
        self.refill_rate = refill_rate
        self.tokens = capacity
        self._last = None

    def allow(self, n: float = 1.0, now: float = 0.0) -> bool:
        if self._last is None:
            self._last = now
        else:
            elapsed = now - self._last
            if elapsed > 0:
                self.tokens = min(self.capacity, self.tokens + elapsed * self.refill_rate)
                self._last = now
        if self.tokens >= n:
            self.tokens -= n
            return True
        return False

class TokenBucket:
    def __init__(self, capacity: float, refill_rate: float):
        self.capacity = capacity
        self.refill_rate = refill_rate
        self.tokens = capacity
        self._last = None

    def allow(self, n: float = 1.0, now: float = 0.0) -> bool:
        if self._last is None:
            self._last = now
        elapsed = now - self._last
        if elapsed > 0:
            self.tokens = min(self.capacity, self.tokens + elapsed * self.refill_rate)
        self._last = now

        if self.tokens >= n:
            self.tokens -= n
            return True
        return False

class TokenBucket:
    def __init__(self, capacity: float, refill_rate: float):
        self.capacity = capacity
        self.refill_rate = refill_rate
        self.tokens = capacity
        self.last = None

    def allow(self, n: float = 1.0, now: float = 0.0) -> bool:
        if self.last is None:
            self.last = now
        elapsed = now - self.last
        if elapsed > 0:
            self.tokens = min(self.capacity, self.tokens + elapsed * self.refill_rate)
        self.last = now
        if self.tokens >= n:
            self.tokens -= n
            return True
        return False

class TokenBucket:

    def __init__(self, capacity: float, refill_rate: float):
        self.capacity = float(capacity)
        self.refill_rate = float(refill_rate)
        self.tokens = float(capacity)
        self.last_update = None

    def allow(self, n: float = 1.0, now: float = 0.0) -> bool:
        if self.last_update is None:
            self.last_update = float(now)
        elif now > self.last_update:
            elapsed = now - self.last_update
            self.tokens = min(
                self.capacity, self.tokens + elapsed * self.refill_rate
            )
            self.last_update = float(now)

        if self.tokens >= n:
            self.tokens -= n
            return True
        return False

class TokenBucket:

    def __init__(self, capacity: float, refill_rate: float):
        self.capacity = float(capacity)
        self.refill_rate = float(refill_rate)
        self.tokens = float(capacity)
        self.last_time = None

    def allow(self, n: float = 1.0, now: float = 0.0) -> bool:
        if self.last_time is None:
            self.last_time = now
        else:
            elapsed = now - self.last_time
            if elapsed > 0:
                self.tokens = min(
                    self.capacity, self.tokens + elapsed * self.refill_rate
                )
            self.last_time = max(self.last_time, now)

        if self.tokens >= n:
            self.tokens -= n
            return True
        return False

class TokenBucket:
    """Continuous-refill token bucket driven by caller-supplied timestamps.

    No real clock is ever read; `now` is provided by the caller on every call.
    The first `allow` call establishes the clock baseline, and the clock is
    treated as monotonic: a `now` earlier than the last seen timestamp
    contributes zero elapsed time and does not move the baseline backwards.
    """

    def __init__(self, capacity: float, refill_rate: float):
        self.capacity = float(capacity)
        self.refill_rate = float(refill_rate)
        self.tokens = float(capacity)
        self._last: float | None = None

    def allow(self, n: float = 1.0, now: float = 0.0) -> bool:
        now = float(now)
        if self._last is None:
            self._last = now
        elif now > self._last:
            self.tokens = min(
                self.capacity, self.tokens + (now - self._last) * self.refill_rate
            )
            self._last = now

        if self.tokens >= n:
            self.tokens -= n
            return True
        return False

class TokenBucket:
    def __init__(self, capacity: float, refill_rate: float):
        self.capacity = capacity
        self.refill_rate = refill_rate
        self._tokens = capacity
        self._last = None

    def allow(self, n: float = 1.0, now: float = 0.0) -> bool:
        if self._last is None:
            self._last = now
        else:
            elapsed = now - self._last
            if elapsed > 0:
                self._tokens = min(self.capacity, self._tokens + elapsed * self.refill_rate)
            self._last = now
        if self._tokens >= n:
            self._tokens -= n
            return True
        return False

class TokenBucket:
    def __init__(self, capacity: float, refill_rate: float):
        self.capacity = capacity
        self.refill_rate = refill_rate
        self.tokens = capacity
        self._last_now = None

    def allow(self, n: float = 1.0, now: float = 0.0) -> bool:
        if self._last_now is None:
            self._last_now = now
        else:
            elapsed = max(0.0, now - self._last_now)
            self.tokens = min(
                self.capacity,
                self.tokens + elapsed * self.refill_rate,
            )
            self._last_now = now

        if self.tokens >= n:
            self.tokens -= n
            return True
        return False

class TokenBucket:
    def __init__(self, capacity: float, refill_rate: float):
        self.capacity = capacity
        self.refill_rate = refill_rate
        self.tokens = capacity
        self._last_now = None

    def allow(self, n: float = 1.0, now: float = 0.0) -> bool:
        if self._last_now is None:
            self._last_now = now
        else:
            elapsed = max(0.0, now - self._last_now)
            self.tokens = min(
                self.capacity,
                self.tokens + elapsed * self.refill_rate,
            )
            self._last_now = now

        if self.tokens >= n:
            self.tokens -= n
            return True

        return False

class TokenBucket:
    def __init__(self, capacity: float, refill_rate: float):
        self.capacity = capacity
        self.refill_rate = refill_rate
        self.tokens = capacity
        self._last_now = None

    def allow(self, n: float = 1.0, now: float = 0.0) -> bool:
        if self._last_now is not None:
            elapsed = max(0.0, now - self._last_now)
            self.tokens = min(
                self.capacity,
                self.tokens + elapsed * self.refill_rate,
            )

        self._last_now = now

        if self.tokens >= n:
            self.tokens -= n
            return True
        return False

def parse_statement(text):
    import re
    from datetime import date

    CURRENCY = '$\u20b9'
    MONTHS = {
        'Jan': 1, 'Feb': 2, 'Mar': 3, 'Apr': 4,
        'May': 5, 'Jun': 6, 'Jul': 7, 'Aug': 8,
        'Sep': 9, 'Oct': 10, 'Nov': 11, 'Dec': 12
    }

    num_re = re.compile(r'^[0-9]+(?:,[0-9]+)*(?:\.[0-9]+)?$')
    dr_re = re.compile(r'^(.*?)\s+DR$')
    dmy_re = re.compile(r'^([0-9]{1,2})/([0-9]{1,2})/([0-9]{4})$')
    ymd_re = re.compile(r'^([0-9]{4})-([0-9]{1,2})-([0-9]{1,2})$')
    mon_re = re.compile(r'^([0-9]{1,2}) ([A-Za-z]{3}) ([0-9]{4})$')

    def parse_date(value):
        value = ' '.join(value.split())

        m = dmy_re.fullmatch(value)
        if m:
            day, month, year = map(int, m.groups())
            try:
                return date(year, month, day).isoformat()
            except ValueError:
                return None

        m = ymd_re.fullmatch(value)
        if m:
            year, month, day = map(int, m.groups())
            try:
                return date(year, month, day).isoformat()
            except ValueError:
                return None

        m = mon_re.fullmatch(value)
        if m:
            day = int(m.group(1))
            month = MONTHS.get(m.group(2).title())
            year = int(m.group(3))
            if month is None:
                return None
            try:
                return date(year, month, day).isoformat()
            except ValueError:
                return None

        return None

    def strip_currency(value):
        value = value.strip()
        if value and value[0] in CURRENCY:
            value = value[1:].lstrip()
        return value

    def parse_number(value):
        value = strip_currency(value)
        if not num_re.fullmatch(value):
            return None
        try:
            return float(value.replace(',', ''))
        except (ValueError, OverflowError):
            return None

    def parse_amount(value):
        value = value.strip()
        if not value:
            return None

        paren_candidate = strip_currency(value)
        if paren_candidate.startswith('(') and paren_candidate.endswith(')'):
            number = parse_number(paren_candidate[1:-1])
            if number is None:
                return None
            return -number if number != 0.0 else 0.0

        m = dr_re.fullmatch(value)
        if m:
            base = m.group(1).strip()
            base_candidate = strip_currency(base)
            if base_candidate.startswith('(') and base_candidate.endswith(')'):
                return None
            number = parse_number(base)
            if number is None:
                return None
            return -number if number != 0.0 else 0.0

        return parse_number(value)

    records = []
    for index, raw_line in enumerate(text.splitlines()):
        line = raw_line.strip()
        if not line:
            continue

        parts = line.split(',', 2)
        if len(parts) != 3:
            continue

        parsed_date = parse_date(parts[0])
        if parsed_date is None:
            continue

        description = parts[1].strip()
        amount = parse_amount(parts[2])
        if amount is None:
            continue

        records.append((parsed_date, index, description, amount))

    records.sort(key=lambda item: (item[0], item[1]))
    return [
        {'date': item[0], 'description': item[2], 'amount': item[3]}
        for item in records
    ]

from datetime import datetime

def parse_statement(text):
    def parse_date(dstr):
        dstr = dstr.strip()
        formats = ['%Y-%m-%d', '%d/%m/%Y', '%d %b %Y']
        for fmt in formats:
            try:
                dt = datetime.strptime(dstr, fmt)
                return dt.strftime('%Y-%m-%d')
            except ValueError:
                continue
        return None

    def parse_amount(amt_str):
        s = amt_str.strip().upper()
        negative = False
        if s.endswith(' DR'):
            negative = True
            s = s[:-3].strip()
        elif s.startswith('(') and s.endswith(')'):
            negative = True
            s = s[1:-1].strip()
        s = s.replace('₹', '').replace('$', '').strip()
        s = s.replace(',', '')
        try:
            val = float(s)
            return -val if negative else val
        except ValueError:
            return None

    entries = []
    for idx, line in enumerate(text.splitlines()):
        line = line.strip()
        if not line:
            continue
        parts = [p.strip() for p in line.split(',', 2)]
        if len(parts) != 3:
            continue
        date_str, desc, amt_str = parts
        desc = desc.strip()
        date_iso = parse_date(date_str)
        if not date_iso:
            continue
        amount = parse_amount(amt_str)
        if amount is None:
            continue
        try:
            date_obj = datetime.strptime(date_iso, '%Y-%m-%d')
        except ValueError:
            continue
        entries.append((date_obj, idx, {"date": date_iso, "description": desc, "amount": amount}))

    entries.sort(key=lambda x: (x[0], x[1]))
    return [entry[2] for entry in entries]

def parse_statement(text):
    import re
    from datetime import date

    MONTH_MAP = {
        'Jan': 1, 'Feb': 2, 'Mar': 3, 'Apr': 4,
        'May': 5, 'Jun': 6, 'Jul': 7, 'Aug': 8,
        'Sep': 9, 'Oct': 10, 'Nov': 11, 'Dec': 12
    }

    def parse_date(d):
        d = d.strip()
        # DD/MM/YYYY
        if re.fullmatch(r'\d{2}/\d{2}/\d{4}', d):
            day, month, year = map(int, d.split('/'))
            try:
                return date(year, month, day).isoformat()
            except ValueError:
                return None
        # YYYY-MM-DD
        if re.fullmatch(r'\d{4}-\d{2}-\d{2}', d):
            year, month, day = map(int, d.split('-'))
            try:
                return date(year, month, day).isoformat()
            except ValueError:
                return None
        # D Mon YYYY
        parts = d.split()
        if len(parts) == 3:
            day_str, mon_str, year_str = parts
            mon = MONTH_MAP.get(mon_str.title())
            if mon is not None:
                try:
                    day = int(day_str)
                    year = int(year_str)
                    return date(year, mon, day).isoformat()
                except ValueError:
                    return None
        return None

    def parse_amount(a):
        a = a.strip()
        if not a:
            return None
        negative = False
        # parentheses -> negative
        if a.startswith('(') and a.endswith(')'):
            negative = True
            a = a[1:-1].strip()
        # " DR" suffix -> negative
        if a.rstrip().endswith(' DR'):
            negative = True
            a = a.rstrip()[:-3].strip()
        # remove currency symbols and commas
        a = a.replace('₹', '').replace('$', '').replace(',', '').strip()
        try:
            val = float(a)
        except ValueError:
            return None
        return -val if negative else val

    results = []
    for line in text.splitlines():
        line = line.strip()
        if not line:
            continue
        first_comma = line.find(',')
        if first_comma == -1:
            continue
        second_comma = line.find(',', first_comma + 1)
        if second_comma == -1:
            continue

        date_raw = line[:first_comma].strip()
        desc = line[first_comma + 1:second_comma].strip()
        amount_raw = line[second_comma + 1:].strip()

        iso_date = parse_date(date_raw)
        if iso_date is None:
            continue
        amount = parse_amount(amount_raw)
        if amount is None:
            continue

        results.append({'date': iso_date, 'description': desc, 'amount': amount})

    results.sort(key=lambda x: x['date'])
    return results

def parse_statement(text):
    import re
    months = {m: i + 1 for i, m in enumerate(
        ["Jan", "Feb", "Mar", "Apr", "May", "Jun",
         "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"])}

    def parse_date(s):
        s = s.strip()
        m = re.fullmatch(r"(\d{2})/(\d{2})/(\d{4})", s)
        if m:
            d, mo, y = int(m[1]), int(m[2]), int(m[3])
        else:
            m = re.fullmatch(r"(\d{4})-(\d{2})-(\d{2})", s)
            if m:
                y, mo, d = int(m[1]), int(m[2]), int(m[3])
            else:
                m = re.fullmatch(r"(\d{1,2}) ([A-Za-z]{3}) (\d{4})", s)
                if not m or m[2] not in months:
                    return None
                d, mo, y = int(m[1]), months[m[2]], int(m[3])
        if not (1 <= mo <= 12 and 1 <= d <= 31):
            return None
        return f"{y:04d}-{mo:02d}-{d:02d}"

    def parse_amount(s):
        s = s.strip()
        neg = False
        if s.endswith(" DR"):
            neg = True
            s = s[:-3].strip()
        if s.startswith("(") and s.endswith(")"):
            neg = True
            s = s[1:-1].strip()
        if s[:1] in ("₹", "$"):
            s = s[1:].strip()
        if not re.fullmatch(r"\d{1,3}(,\d{3})*(\.\d+)?|\d+(\.\d+)?", s):
            return None
        val = float(s.replace(",", ""))
        return -val if neg else val

    rows = []
    for line in text.splitlines():
        if not line.strip():
            continue
        parts = line.split(",", 2)
        if len(parts) != 3:
            continue
        date = parse_date(parts[0])
        if date is None:
            continue
        desc = parts[1].strip()
        amount = parse_amount(parts[2])
        if amount is None:
            continue
        rows.append({"date": date, "description": desc, "amount": amount})
    rows.sort(key=lambda r: r["date"])
    return rows

import re
from datetime import datetime

def parse_statement(text):
    month_map = {
        "jan": 1, "feb": 2, "mar": 3, "apr": 4, "may": 5, "jun": 6,
        "jul": 7, "aug": 8, "sep": 9, "oct": 10, "nov": 11, "dec": 12
    }

    def parse_date(s):
        s = s.strip()
        m = re.fullmatch(r"(\d{2})/(\d{2})/(\d{4})", s)
        if m:
            d, mo, y = int(m.group(1)), int(m.group(2)), int(m.group(3))
            try:
                return datetime(y, mo, d).strftime("%Y-%m-%d")
            except ValueError:
                return None
        m = re.fullmatch(r"(\d{4})-(\d{2})-(\d{2})", s)
        if m:
            y, mo, d = int(m.group(1)), int(m.group(2)), int(m.group(3))
            try:
                return datetime(y, mo, d).strftime("%Y-%m-%d")
            except ValueError:
                return None
        m = re.fullmatch(r"(\d{1,2})\s+([A-Za-z]{3})\s+(\d{4})", s)
        if m:
            d = int(m.group(1))
            mo_str = m.group(2).lower()
            y = int(m.group(3))
            mo = month_map.get(mo_str)
            if mo is None:
                return None
            try:
                return datetime(y, mo, d).strftime("%Y-%m-%d")
            except ValueError:
                return None
        return None

    def parse_amount(s):
        s = s.strip()
        negative = False

        m = re.fullmatch(r"\((.*)\)", s)
        if m:
            negative = True
            s = m.group(1).strip()

        if s.upper().endswith("DR"):
            negative = True
            s = s[:-2].strip()

        s = s.strip()
        if s.startswith("₹") or s.startswith("$"):
            s = s[1:].strip()

        s = s.replace(",", "")

        if not re.fullmatch(r"\d+(\.\d+)?", s):
            return None

        try:
            val = float(s)
        except ValueError:
            return None

        return -val if negative else val

    results = []
    for line in text.splitlines():
        line = line.strip()
        if not line:
            continue

        parts = line.split(",")
        if len(parts) != 3:
            continue

        date_str, desc_str, amount_str = parts

        date_iso = parse_date(date_str)
        if date_iso is None:
            continue

        desc = desc_str.strip()
        if not desc:
            continue

        amount = parse_amount(amount_str)
        if amount is None:
            continue

        results.append({"date": date_iso, "description": desc, "amount": amount})

    results.sort(key=lambda x: x["date"])
    return results

def parse_statement(text):
    import re

    months = {
        "jan": 1, "feb": 2, "mar": 3, "apr": 4, "may": 5, "jun": 6,
        "jul": 7, "aug": 8, "sep": 9, "oct": 10, "nov": 11, "dec": 12,
    }

    def parse_date(s):
        s = s.strip()
        m = re.fullmatch(r"(\d{1,2})/(\d{1,2})/(\d{4})", s)
        if m:
            d, mo, y = int(m.group(1)), int(m.group(2)), int(m.group(3))
        else:
            m = re.fullmatch(r"(\d{4})-(\d{1,2})-(\d{1,2})", s)
            if m:
                y, mo, d = int(m.group(1)), int(m.group(2)), int(m.group(3))
            else:
                m = re.fullmatch(r"(\d{1,2})\s+([A-Za-z]{3})\s+(\d{4})", s)
                if not m:
                    return None
                d, mon_s, y = int(m.group(1)), m.group(2).lower(), int(m.group(3))
                if mon_s not in months:
                    return None
                mo = months[mon_s]
        if not (1 <= mo <= 12 and 1 <= d <= 31):
            return None
        return "%04d-%02d-%02d" % (y, mo, d)

    def parse_amount(s):
        s = s.strip()
        negative = False
        if s.startswith("(") and s.endswith(")"):
            negative = True
            s = s[1:-1].strip()
        elif s.endswith(" DR"):
            negative = True
            s = s[:-3].strip()
        if s and s[0] in "₹$":
            s = s[1:].strip()
        s = s.replace(",", "")
        if not re.fullmatch(r"\d+(\.\d+)?", s):
            return None
        val = float(s)
        return -val if negative else val

    results = []
    for line in text.splitlines():
        if not line.strip():
            continue
        parts = line.split(",")
        if len(parts) != 3:
            continue
        date = parse_date(parts[0])
        if date is None:
            continue
        desc = parts[1].strip()
        amount = parse_amount(parts[2])
        if amount is None:
            continue
        results.append({"date": date, "description": desc, "amount": amount})

    return sorted(results, key=lambda r: r["date"])

import datetime
import re


def parse_statement(text):
    results = []
    months = {
        "Jan": 1,
        "Feb": 2,
        "Mar": 3,
        "Apr": 4,
        "May": 5,
        "Jun": 6,
        "Jul": 7,
        "Aug": 8,
        "Sep": 9,
        "Oct": 10,
        "Nov": 11,
        "Dec": 12,
    }

    if not isinstance(text, str):
        return []

    for line in text.splitlines():
        line = line.strip()
        if not line:
            continue

        parts = line.split(",")
        if len(parts) != 3:
            continue

        date_raw, desc_raw, amount_raw = parts

        desc = desc_raw.strip()

        # Parse Date
        d_str = date_raw.strip()
        iso_date = None

        try:
            # YYYY-MM-DD
            m1 = re.match(r"^(\d{4})-(\d{1,2})-(\d{1,2})$", d_str)
            if m1:
                y, m, d = map(int, m1.groups())
                datetime.date(y, m, d)
                iso_date = f"{y:04d}-{m:02d}-{d:02d}"

            # DD/MM/YYYY
            if not iso_date:
                m2 = re.match(r"^(\d{1,2})/(\d{1,2})/(\d{4})$", d_str)
                if m2:
                    d, m, y = map(int, m2.groups())
                    datetime.date(y, m, d)
                    iso_date = f"{y:04d}-{m:02d}-{d:02d}"

            # D Mon YYYY
            if not iso_date:
                m3 = re.match(r"^(\d{1,2})\s+([A-Za-z]{3})\s+(\d{4})$", d_str)
                if m3:
                    d, mon_str, y = m3.group(1), m3.group(2).capitalize(), m3.group(3)
                    if mon_str in months:
                        y, m, d = int(y), months[mon_str], int(d)
                        datetime.date(y, m, d)
                        iso_date = f"{y:04d}-{m:02d}-{d:02d}"

            if not iso_date:
                continue
        except Exception:
            continue

        # Parse Amount
        try:
            amt_str = amount_raw.strip()
            is_neg = False

            if amt_str.endswith(" DR"):
                is_neg = True
                amt_str = amt_str[:-3].strip()
            elif amt_str.endswith("DR"):
                is_neg = True
                amt_str = amt_str[:-2].strip()
            elif amt_str.startswith("(") and amt_str.endswith(")"):
                is_neg = True
                amt_str = amt_str[1:-1].strip()

            amt_str = (
                amt_str.replace("₹", "").replace("$", "").replace(",", "").strip()
            )
            val = float(amt_str)
            if is_neg:
                val = -abs(val)

            results.append({"date": iso_date, "description": desc, "amount": val})
        except Exception:
            continue

    results.sort(key=lambda x: x["date"])
    return results

from datetime import datetime


def parse_statement(text):
    months = {
        "Jan": 1,
        "Feb": 2,
        "Mar": 3,
        "Apr": 4,
        "May": 5,
        "Jun": 6,
        "Jul": 7,
        "Aug": 8,
        "Sep": 9,
        "Oct": 10,
        "Nov": 11,
        "Dec": 12,
    }

    results = []

    for line in text.splitlines():
        if not line.strip():
            continue

        parts = line.split(",")
        if len(parts) != 3:
            continue

        date_str, desc_str, amt_str = parts[0].strip(), parts[1].strip(), parts[2].strip()

        # Parse date
        parsed_date = None
        # Try DD/MM/YYYY
        try:
            dt = datetime.strptime(date_str, "%d/%m/%Y")
            parsed_date = dt.strftime("%Y-%m-%d")
        except ValueError:
            pass

        # Try YYYY-MM-DD
        if not parsed_date:
            try:
                dt = datetime.strptime(date_str, "%Y-%m-%d")
                parsed_date = dt.strftime("%Y-%m-%d")
            except ValueError:
                pass

        # Try D Mon YYYY
        if not parsed_date:
            try:
                d_parts = date_str.split()
                if len(d_parts) == 3 and d_parts[1] in months:
                    day = int(d_parts[0])
                    month = months[d_parts[1]]
                    year = int(d_parts[2])
                    dt = datetime(year, month, day)
                    parsed_date = dt.strftime("%Y-%m-%d")
            except (ValueError, KeyError, IndexError):
                pass

        if not parsed_date:
            continue

        # Parse amount
        is_negative = False
        clean_amt = amt_str

        if clean_amt.startswith("(") and clean_amt.endswith(")"):
            is_negative = True
            clean_amt = clean_amt[1:-1].strip()
        elif clean_amt.endswith(" DR") or clean_amt.endswith(" dr"):
            is_negative = True
            clean_amt = clean_amt[:-3].strip()

        clean_amt = clean_amt.replace("₹", "").replace("$", "").replace(",", "").strip()

        try:
            amount = float(clean_amt)
            if is_negative:
                amount = -amount
        except ValueError:
            continue

        results.append(
            {"date": parsed_date, "description": desc_str, "amount": amount}
        )

    return sorted(results, key=lambda x: x["date"])

import re
from datetime import date

_MONTHS = {m: i for i, m in enumerate(
    ["jan", "feb", "mar", "apr", "may", "jun",
     "jul", "aug", "sep", "oct", "nov", "dec"], start=1)}

_DMY = re.compile(r"(\d{1,2})/(\d{1,2})/(\d{4})")
_ISO = re.compile(r"(\d{4})-(\d{1,2})-(\d{1,2})")
_TXT = re.compile(r"(\d{1,2})\s+([A-Za-z]{3})\s+(\d{4})")
_DR = re.compile(r"(.*?)\s+DR", re.IGNORECASE)
_NUM = re.compile(r"(?:\d{1,3}(?:,\d{3})+|\d+)(?:\.\d+)?")


def parse_statement(text):
    """Parse a messy `date,description,amount` statement into sorted dicts.

    Unparseable lines are skipped. Debits — parenthesised or ` DR`-suffixed —
    become negative amounts. Result is sorted by ISO date, ties in input order.
    """

    def parse_date(raw):
        raw = raw.strip()
        m = _DMY.fullmatch(raw)
        if m:
            day, month, year = int(m[1]), int(m[2]), int(m[3])
        elif (m := _ISO.fullmatch(raw)):
            year, month, day = int(m[1]), int(m[2]), int(m[3])
        elif (m := _TXT.fullmatch(raw)):
            day, year = int(m[1]), int(m[3])
            month = _MONTHS.get(m[2].lower())
            if month is None:
                return None
        else:
            return None
        try:
            return date(year, month, day).isoformat()
        except ValueError:
            return None

    def parse_amount(raw):
        s = raw.strip()
        negative = False
        if (m := _DR.fullmatch(s)):
            negative = True
            s = m[1].strip()
        if s.startswith("(") and s.endswith(")"):
            negative = True
            s = s[1:-1].strip()
        if s[:1] in ("\u20b9", "$"):
            s = s[1:].strip()
        if not _NUM.fullmatch(s):
            return None
        value = float(s.replace(",", ""))
        return -value if negative else value

    rows = []
    for line in text.splitlines():
        if not line.strip():
            continue
        # The amount may carry thousands commas, so only the first two commas
        # are field separators; everything after them belongs to the amount.
        parts = line.split(",")
        if len(parts) < 3:
            continue
        iso_date = parse_date(parts[0])
        if iso_date is None:
            continue
        amount = parse_amount(",".join(parts[2:]))
        if amount is None:
            continue
        rows.append({
            "date": iso_date,
            "description": parts[1].strip(),
            "amount": amount,
        })

    return sorted(rows, key=lambda row: row["date"])

def parse_statement(text):
    import re
    from datetime import datetime

    MONTHS = {
        "jan": 1, "feb": 2, "mar": 3, "apr": 4, "may": 5, "jun": 6,
        "jul": 7, "aug": 8, "sep": 9, "oct": 10, "nov": 11, "dec": 12,
    }

    def valid_date(y, mo, d):
        try:
            return datetime(y, mo, d).strftime("%Y-%m-%d")
        except ValueError:
            return None

    def parse_date(s):
        m = re.match(r"^(\d{4})-(\d{1,2})-(\d{1,2})$", s)
        if m:
            y, mo, d = map(int, m.groups())
            return valid_date(y, mo, d)
        m = re.match(r"^(\d{1,2})/(\d{1,2})/(\d{4})$", s)
        if m:
            d, mo, y = map(int, m.groups())
            return valid_date(y, mo, d)
        m = re.match(r"^(\d{1,2}) ([A-Za-z]{3}) (\d{4})$", s)
        if m:
            d, mon, y = m.groups()
            mo = MONTHS.get(mon.lower())
            return valid_date(int(y), mo, int(d)) if mo else None
        return None

    def parse_amount(s):
        s = s.strip()
        negative = False
        if s.startswith("(") and s.endswith(")"):
            negative = True
            s = s[1:-1].strip()
        elif s.endswith(" DR"):
            negative = True
            s = s[:-3].strip()
        for cur in ("\u20b9", "$"):
            if s.startswith(cur):
                s = s[1:].strip()
                break
        s = s.replace(",", "").strip()
        try:
            value = float(s)
        except ValueError:
            return None
        return -value if negative else value

    rows = []
    for line in text.splitlines():
        line = line.strip()
        if not line:
            continue
        parts = line.split(",")
        if len(parts) < 3:
            continue
        date = parse_date(parts[0].strip())
        if date is None:
            continue
        description = parts[1].strip()
        amount = parse_amount(",".join(parts[2:]))
        if amount is None:
            continue
        rows.append({"date": date, "description": description, "amount": amount})

    rows.sort(key=lambda r: r["date"])
    return rows

def parse_statement(text):
    import re
    from datetime import datetime

    date_formats = ("%d/%m/%Y", "%Y-%m-%d", "%d %b %Y")
    amount_pattern = re.compile(r"(?:\d+|\d{1,3}(?:,\d{3})+)(?:\.\d+)?")

    records = []

    for line in text.splitlines():
        if not line.strip():
            continue

        parts = line.split(",", 2)
        if len(parts) != 3:
            continue

        date_text, description, amount_text = (part.strip() for part in parts)

        parsed_date = None
        for date_format in date_formats:
            try:
                parsed_date = datetime.strptime(date_text, date_format).date()
                break
            except ValueError:
                pass

        if parsed_date is None:
            continue

        amount_text = amount_text.strip()
        if amount_text[:1] in ("₹", "$"):
            amount_text = amount_text[1:].strip()

        negative = False
        if amount_text.startswith("(") and amount_text.endswith(")"):
            negative = True
            amount_text = amount_text[1:-1].strip()
        elif amount_text.endswith(" DR"):
            negative = True
            amount_text = amount_text[:-3].strip()

        if not amount_pattern.fullmatch(amount_text):
            continue

        amount = float(amount_text.replace(",", ""))
        if negative:
            amount = -amount

        records.append({
            "date": parsed_date.isoformat(),
            "description": description,
            "amount": amount,
        })

    records.sort(key=lambda record: record["date"])
    return records

def parse_statement(text):
    import re
    from datetime import datetime

    date_pattern = r"(?:\d{2}/\d{2}/\d{4}|\d{4}-\d{2}-\d{2}|\d{1,2} [A-Za-z]{3} \d{4})"
    amount_pattern = r"(?:₹|\$)?\s*(?:(?:\((?P<paren>[^\(\)]+)\))|(?P<plain>[^()] +))"
    number_pattern = r"(?:\d{1,3}(?:,\d{3})+|\d+)(?:\.\d+)?"

    results = []

    for index, line in enumerate(text.splitlines()):
        if not line.strip():
            continue

        match = re.match(
            rf"^\s*(?P<date>{date_pattern})\s*,(?P<description>[^,]*),\s*"
            rf"(?P<amount>(?:₹|\$)?\s*(?:\({number_pattern}\)|{number_pattern}(?:\s+DR)?))\s*$",
            line,
        )
        if not match:
            continue

        date_text = match.group("date")
        try:
            if "/" in date_text:
                date = datetime.strptime(date_text, "%d/%m/%Y").date()
            elif "-" in date_text:
                date = datetime.strptime(date_text, "%Y-%m-%d").date()
            else:
                date = datetime.strptime(date_text, "%d %b %Y").date()
        except ValueError:
            continue

        amount_text = match.group("amount").strip()
        amount_text = re.sub(r"^(?:₹|\$)\s*", "", amount_text)

        negative = False
        if amount_text.startswith("(") and amount_text.endswith(")"):
            negative = True
            amount_text = amount_text[1:-1]
        elif amount_text.endswith(" DR"):
            negative = True
            amount_text = amount_text[:-3].rstrip()

        if not re.fullmatch(number_pattern, amount_text):
            continue

        amount = float(amount_text.replace(",", ""))
        if negative:
            amount = -amount

        results.append({
            "date": date.isoformat(),
            "description": match.group("description").strip(),
            "amount": amount,
            "_index": index,
        })

    results.sort(key=lambda item: item["date"])
    return [
        {key: value for key, value in item.items() if key != "_index"}
        for item in results
    ]

def parse_statement(text):
    from datetime import datetime
    import re

    records = []
    date_formats = ("%d/%m/%Y", "%Y-%m-%d", "%d %b %Y")

    for line in text.splitlines():
        if not line.strip():
            continue

        parts = line.split(",")
        if len(parts) != 3:
            continue

        date_text, description, amount_text = (part.strip() for part in parts)
        if not description:
            continue

        parsed_date = None
        for fmt in date_formats:
            try:
                parsed_date = datetime.strptime(date_text, fmt).date()
                break
            except ValueError:
                pass
        if parsed_date is None:
            continue

        negative = False
        if amount_text.endswith(" DR"):
            negative = True
            amount_text = amount_text[:-3].strip()
        elif amount_text.startswith("(") and amount_text.endswith(")"):
            negative = True
            amount_text = amount_text[1:-1].strip()

        amount_text = re.sub(r"^[₹$]\s*", "", amount_text)
        if not re.fullmatch(r"\d{1,3}(?:,\d{3})*(?:\.\d+)?|\d+(?:\.\d+)?", amount_text):
            continue

        amount = float(amount_text.replace(",", ""))
        records.append({
            "date": parsed_date.isoformat(),
            "description": description,
            "amount": -amount if negative else amount,
        })

    return sorted(records, key=lambda record: record["date"])

def rotation_index(a):
    if not a:
        return -1

    lo, hi = 0, len(a) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] > a[hi]:
            lo = mid + 1
        else:
            hi = mid
    return lo

def rotation_index(a):
    if not a:
        return -1
    lo, hi = 0, len(a) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] > a[hi]:
            lo = mid + 1
        else:
            hi = mid
    return lo

def rotation_index(a):
    if not a:
        return -1
    lo, hi = 0, len(a) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] > a[hi]:
            lo = mid + 1
        else:
            hi = mid
    return lo

def rotation_index(a):
    if not a:
        return -1
    lo, hi = 0, len(a) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] > a[hi]:
            lo = mid + 1
        else:
            hi = mid
    return lo

def rotation_index(a):
    if not a:
        return -1
    lo, hi = 0, len(a) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] > a[hi]:
            lo = mid + 1
        else:
            hi = mid
    return lo

def rotation_index(a):
    if not a:
        return -1
    lo, hi = 0, len(a) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] > a[hi]:
            lo = mid + 1
        else:
            hi = mid
    return lo

def rotation_index(a):
    if not a:
        return -1
    lo, hi = 0, len(a) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] > a[hi]:
            lo = mid + 1
        else:
            hi = mid
    return lo

def rotation_index(a):
    if not a:
        return -1
    lo, hi = 0, len(a) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] > a[hi]:
            lo = mid + 1
        else:
            hi = mid
    return lo

def rotation_index(a):
    if not a:
        return -1
    lo, hi = 0, len(a) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] > a[hi]:
            lo = mid + 1
        else:
            hi = mid
    return lo

def rotation_index(a):
    if not a:
        return -1
    lo, hi = 0, len(a) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] > a[hi]:
            lo = mid + 1
        else:
            hi = mid
    return lo

def rotation_index(a):
    if not a:
        return -1

    lo, hi = 0, len(a) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] > a[hi]:
            lo = mid + 1
        else:
            hi = mid
    return lo

def rotation_index(a):
    if not a:
        return -1

    lo, hi = 0, len(a) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] > a[hi]:
            lo = mid + 1
        else:
            hi = mid

    return lo

def rotation_index(a):
    if not a:
        return -1

    lo, hi = 0, len(a) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] > a[hi]:
            lo = mid + 1
        else:
            hi = mid
    return lo

SELECT
  c.city,
  SUM(o.amount) AS total
FROM orders AS o
JOIN customers AS c
  ON c.id = o.customer_id
WHERE o.created_at BETWEEN '2026-01-01' AND '2026-03-31'
  AND o.customer_id IS NOT NULL
  AND c.city IS NOT NULL
GROUP BY c.city
ORDER BY total DESC, c.city ASC
LIMIT 3;

SELECT c.city, SUM(o.amount) AS total
FROM orders o
JOIN customers c ON o.customer_id = c.id
WHERE o.created_at BETWEEN '2026-01-01' AND '2026-03-31'
  AND o.customer_id IS NOT NULL
  AND c.city IS NOT NULL
GROUP BY c.city
ORDER BY total DESC, c.city ASC
LIMIT 3;

SELECT c.city, SUM(o.amount) AS total
FROM orders o
JOIN customers c ON o.customer_id = c.id
WHERE o.created_at >= '2026-01-01' AND o.created_at <= '2026-03-31'
  AND c.city IS NOT NULL
GROUP BY c.city
ORDER BY total DESC, c.city ASC
LIMIT 3;

SELECT c.city AS city, SUM(o.amount) AS total
FROM orders o
JOIN customers c ON c.id = o.customer_id
WHERE o.created_at BETWEEN '2026-01-01' AND '2026-03-31'
  AND c.city IS NOT NULL
GROUP BY c.city
ORDER BY total DESC, city ASC
LIMIT 3;

SELECT c.city AS city, SUM(o.amount) AS total
FROM orders o
JOIN customers c ON c.id = o.customer_id
WHERE o.customer_id IS NOT NULL
  AND c.city IS NOT NULL
  AND o.created_at BETWEEN '2026-01-01' AND '2026-03-31'
GROUP BY c.city
ORDER BY total DESC, city ASC
LIMIT 3;

SELECT c.city AS city, SUM(o.amount) AS total
FROM orders o
JOIN customers c ON c.id = o.customer_id
WHERE o.customer_id IS NOT NULL
  AND c.city IS NOT NULL
  AND o.created_at >= '2026-01-01'
  AND o.created_at <= '2026-03-31'
GROUP BY c.city
ORDER BY total DESC, city ASC
LIMIT 3;

SELECT c.city, SUM(o.amount) AS total
FROM orders o
JOIN customers c ON o.customer_id = c.id
WHERE o.created_at BETWEEN '2026-01-01' AND '2026-03-31'
  AND c.city IS NOT NULL
GROUP BY c.city
ORDER BY total DESC, c.city ASC
LIMIT 3;

SELECT c.city, SUM(o.amount) AS total
FROM orders o
JOIN customers c ON o.customer_id = c.id
WHERE o.created_at >= '2026-01-01' 
  AND o.created_at <= '2026-03-31'
  AND o.customer_id IS NOT NULL 
  AND c.city IS NOT NULL
GROUP BY c.city
ORDER BY total DESC, c.city ASC
LIMIT 3;

SELECT c.city AS city, SUM(o.amount) AS total
FROM orders o
JOIN customers c ON c.id = o.customer_id
WHERE o.customer_id IS NOT NULL
  AND c.city IS NOT NULL
  AND o.created_at >= '2026-01-01'
  AND o.created_at < '2026-04-01'
GROUP BY c.city
ORDER BY total DESC, city ASC
LIMIT 3;

SELECT c.city AS city, SUM(o.amount) AS total
FROM orders o
JOIN customers c ON c.id = o.customer_id
WHERE o.created_at >= '2026-01-01'
  AND o.created_at <= '2026-03-31'
  AND o.customer_id IS NOT NULL
  AND c.city IS NOT NULL
GROUP BY c.city
ORDER BY total DESC, city ASC
LIMIT 3;

SELECT c.city, SUM(o.amount) AS total
FROM orders AS o
JOIN customers AS c ON c.id = o.customer_id
WHERE o.created_at >= '2026-01-01'
  AND o.created_at < '2026-04-01'
  AND c.city IS NOT NULL
GROUP BY c.city
ORDER BY total DESC, c.city ASC
LIMIT 3;

SELECT c.city, SUM(o.amount) AS total
FROM orders AS o
JOIN customers AS c ON c.id = o.customer_id
WHERE o.created_at >= '2026-01-01'
  AND o.created_at <= '2026-03-31'
  AND c.city IS NOT NULL
GROUP BY c.city
ORDER BY total DESC, c.city ASC
LIMIT 3;

SELECT c.city, SUM(o.amount) AS total
FROM orders AS o
JOIN customers AS c ON c.id = o.customer_id
WHERE o.created_at >= '2026-01-01'
  AND o.created_at <= '2026-03-31'
  AND c.city IS NOT NULL
GROUP BY c.city
ORDER BY total DESC, c.city ASC
LIMIT 3;

def merge_busy2(intervals, cancels):
    import heapq
    from collections import defaultdict

    starts = defaultdict(list)
    ends = defaultdict(list)
    cancel_delta = defaultdict(int)
    coords = set()

    for s, e, p in intervals:
        starts[s].append(p)
        ends[e].append(p)
        coords.add(s)
        coords.add(e)

    for s, e in cancels:
        cancel_delta[s] += 1
        cancel_delta[e] -= 1
        coords.add(s)
        coords.add(e)

    if not coords:
        return []

    active = defaultdict(int)
    heap = []
    cancel_active = 0
    result = []

    xs = sorted(coords)

    for i, x in enumerate(xs):
        for p in starts.get(x, ()):
            active[p] += 1
            heapq.heappush(heap, -p)

        for p in ends.get(x, ()):
            active[p] -= 1

        cancel_active += cancel_delta.get(x, 0)

        while heap and active.get(-heap[0], 0) <= 0:
            heapq.heappop(heap)

        if i + 1 < len(xs):
            y = xs[i + 1]
            if cancel_active == 0 and heap:
                p = -heap[0]
                if result and result[-1][1] == x and result[-1][2] == p:
                    result[-1] = (result[-1][0], y, p)
                else:
                    result.append((x, y, p))

    return result

def merge_busy2(intervals, cancels):
    from collections import Counter
    import heapq

    if not intervals:
        return []

    events = []
    for s, e, p in intervals:
        events.append((s, 1, p))
        events.append((e, 0, p))
    events.sort()

    active = Counter()
    maxheap = []
    current_max = None
    segments = []
    prev_t = None

    for t, typ, p in events:
        if prev_t is not None and t > prev_t and current_max is not None:
            if segments and segments[-1][1] == prev_t and segments[-1][2] == current_max:
                segments[-1] = (segments[-1][0], t, current_max)
            else:
                segments.append((prev_t, t, current_max))
        if typ == 1:
            active[p] += 1
            heapq.heappush(maxheap, -p)
        else:
            active[p] -= 1
            if active[p] == 0:
                del active[p]
        while maxheap and active[-maxheap[0]] == 0:
            heapq.heappop(maxheap)
        current_max = -maxheap[0] if maxheap else None
        prev_t = t

    if not cancels:
        return segments

    cans = sorted(cancels)
    cancel_merged = []
    for s, e in cans:
        if not cancel_merged or cancel_merged[-1][1] < s:
            cancel_merged.append((s, e))
        else:
            cancel_merged[-1] = (cancel_merged[-1][0], max(cancel_merged[-1][1], e))

    result = []
    i = 0
    ncan = len(cancel_merged)
    for s, e, p in segments:
        curr = s
        while i < ncan and cancel_merged[i][1] <= curr:
            i += 1
        j = i
        while j < ncan and cancel_merged[j][0] < e:
            cs, ce = cancel_merged[j]
            if cs > curr:
                if curr < cs:
                    if result and result[-1][1] == curr and result[-1][2] == p:
                        result[-1] = (result[-1][0], cs, p)
                    else:
                        result.append((curr, cs, p))
                curr = max(curr, ce)
                if curr >= e:
                    break
            else:
                curr = max(curr, ce)
                if curr >= e:
                    break
            j += 1
        if curr < e:
            if result and result[-1][1] == curr and result[-1][2] == p:
                result[-1] = (result[-1][0], e, p)
            else:
                result.append((curr, e, p))
        while i < ncan and cancel_merged[i][1] <= e:
            i += 1

    return result

import heapq

def merge_busy2(intervals, cancels):
    # Step 1: Build events from intervals
    events = []
    for s, e, p in intervals:
        events.append((s, 1, p))   # start
        events.append((e, -1, p))  # end
    # Sort by coordinate; for same coordinate, ends (-1) before starts (1)
    events.sort(key=lambda x: (x[0], x[1]))

    active = {}
    heap = []
    current_start = None
    current_prio = 0
    segments = []

    idx = 0
    n = len(events)
    while idx < n:
        x = events[idx][0]
        # process all events at this coordinate
        while idx < n and events[idx][0] == x:
            _, typ, p = events[idx]
            if typ == 1:    # start
                active[p] = active.get(p, 0) + 1
                heapq.heappush(heap, -p)
            else:           # end
                active[p] = active.get(p, 0) - 1
            idx += 1

        # remove stale max entries
        while heap and active.get(-heap[0], 0) == 0:
            heapq.heappop(heap)
        max_p = -heap[0] if heap else 0

        if max_p != current_prio:
            if current_prio > 0 and current_start < x:
                segments.append((current_start, x, current_prio))
            current_start = x
            current_prio = max_p

    # Coalesce adjacent segments with equal priority
    if not segments:
        return []

    merged_segs = []
    for seg in segments:
        if not merged_segs:
            merged_segs.append(seg)
        else:
            prev_s, prev_e, prev_p = merged_segs[-1]
            cur_s, cur_e, cur_p = seg
            if prev_p == cur_p and prev_e == cur_s:
                merged_segs[-1] = (prev_s, cur_e, prev_p)
            else:
                merged_segs.append(seg)
    segments = merged_segs

    # Step 2: Merge overlapping/touching cancels
    if not cancels:
        return segments

    cancels_sorted = sorted(cancels, key=lambda c: c[0])
    merged_c = []
    for s, e in cancels_sorted:
        if not merged_c or merged_c[-1][1] < s:
            merged_c.append([s, e])
        else:
            merged_c[-1][1] = max(merged_c[-1][1], e)

    # Step 3: Subtract merged cancels from resolved segments
    result = []
    i = 0
    m = len(merged_c)
    for s, e, p in segments:
        # Skip cancels that end before or exactly at the segment start
        while i < m and merged_c[i][1] <= s:
            i += 1
        k = i
        while k < m and merged_c[k][0] < e:
            cs, ce = merged_c[k]
            if cs > s:
                result.append((s, cs, p))
            s = max(s, ce)
            if s >= e:
                break
            k += 1
        if s < e:
            result.append((s, e, p))

    return result

def merge_busy2(intervals, cancels):
    from collections import Counter
    if not intervals:
        return []
    events = {}
    for s, e, p in intervals:
        events.setdefault(s, []).append(("i", p, 1))
        events.setdefault(e, []).append(("i", p, -1))
    for s, e in cancels:
        events.setdefault(s, []).append(("c", None, 1))
        events.setdefault(e, []).append(("c", None, -1))
    points = sorted(events)
    active = Counter()
    cancel_depth = 0
    result = []
    prev = None
    for x in points:
        if prev is not None and active and cancel_depth == 0:
            prio = max(active)
            if result and result[-1][1] == prev and result[-1][2] == prio:
                result[-1] = (result[-1][0], x, prio)
            else:
                result.append((prev, x, prio))
        for kind, p, d in events[x]:
            if kind == "i":
                active[p] += d
                if active[p] == 0:
                    del active[p]
            else:
                cancel_depth += d
        prev = x
    return result

def merge_busy2(intervals, cancels):
    if not intervals:
        return []

    coords = set()
    for s, e, _ in intervals:
        coords.add(s)
        coords.add(e)
    for s, e in cancels:
        coords.add(s)
        coords.add(e)

    pts = sorted(coords)

    segments = []
    for i in range(len(pts) - 1):
        a, b = pts[i], pts[i + 1]
        if a >= b:
            continue

        covering_prios = [p for (s, e, p) in intervals if s <= a and e >= b]
        if not covering_prios:
            continue

        cancelled = any(cs <= a and ce >= b for (cs, ce) in cancels)
        if cancelled:
            continue

        prio = max(covering_prios)
        segments.append([a, b, prio])

    merged = []
    for seg in segments:
        if merged and merged[-1][1] == seg[0] and merged[-1][2] == seg[2]:
            merged[-1][1] = seg[1]
        else:
            merged.append(seg)

    return [tuple(seg) for seg in merged]

def merge_busy2(intervals, cancels):
    if not intervals:
        return []
    from collections import Counter
    coords = set()
    istarts, iends = {}, {}
    cstarts, cends = {}, {}
    for s, e, p in intervals:
        coords.add(s)
        coords.add(e)
        istarts.setdefault(s, []).append(p)
        iends.setdefault(e, []).append(p)
    for s, e in cancels:
        coords.add(s)
        coords.add(e)
        cstarts[s] = cstarts.get(s, 0) + 1
        cends[e] = cends.get(e, 0) + 1
    xs = sorted(coords)
    active = Counter()
    cactive = 0
    segments = []
    for i, x in enumerate(xs):
        for p in iends.get(x, []):
            active[p] -= 1
            if active[p] == 0:
                del active[p]
        cactive -= cends.get(x, 0)
        for p in istarts.get(x, []):
            active[p] += 1
        cactive += cstarts.get(x, 0)
        if i + 1 < len(xs) and active and cactive == 0:
            segments.append((x, xs[i + 1], max(active)))
    result = []
    for seg in segments:
        if result and result[-1][1] == seg[0] and result[-1][2] == seg[2]:
            result[-1] = (result[-1][0], seg[1], seg[2])
        else:
            result.append(seg)
    return result

from collections import defaultdict
import heapq

def merge_busy2(intervals, cancels):
    if not intervals:
        return []

    events = defaultdict(list)
    for s, e, p in intervals:
        events[s].append(('int_start', p))
        events[e].append(('int_end', p))
    for s, e in cancels:
        events[s].append(('cancel_start',))
        events[e].append(('cancel_end',))

    sorted_x = sorted(events.keys())

    active_cancels = 0
    active_prios = defaultdict(int)
    heap = []

    pieces = []

    for i in range(len(sorted_x)):
        x = sorted_x[i]
        for event in events[x]:
            kind = event[0]
            if kind == 'int_start':
                p = event[1]
                if active_prios[p] == 0:
                    heapq.heappush(heap, -p)
                active_prios[p] += 1
            elif kind == 'int_end':
                p = event[1]
                active_prios[p] -= 1
            elif kind == 'cancel_start':
                active_cancels += 1
            elif kind == 'cancel_end':
                active_cancels -= 1

        while heap and active_prios[-heap[0]] == 0:
            heapq.heappop(heap)

        if i < len(sorted_x) - 1:
            next_x = sorted_x[i + 1]
            if active_cancels == 0 and heap:
                max_p = -heap[0]
                pieces.append((x, next_x, max_p))

    res = []
    for s, e, p in pieces:
        if res and res[-1][1] == s and res[-1][2] == p:
            res[-1] = (res[-1][0], e, p)
        else:
            res.append((s, e, p))

    return res

def merge_busy2(intervals, cancels):
    if not intervals:
        return []

    events = []
    for start, end, prio in intervals:
        events.append((start, 1, prio))
        events.append((end, -1, prio))

    for start, end in cancels:
        events.append((start, 0, None))
        events.append((end, 0, None))

    events.sort(key=lambda x: (x[0], x[1], x[2] if x[2] is not None else 0))

    active_intervals = {}

    def add_prio(p):
        active_intervals[p] = active_intervals.get(p, 0) + 1

    def remove_prio(p):
        active_intervals[p] -= 1
        if active_intervals[p] == 0:
            del active_intervals[p]

    def get_max_prio():
        if not active_intervals:
            return None
        return max(active_intervals.keys())

    cancel_depth = 0
    res = []
    prev_x = None

    i = 0
    n = len(events)
    while i < n:
        x = events[i][0]

        while i < n and events[i][0] == x:
            _, t, p = events[i]
            if t == 1:
                add_prio(p)
            elif t == -1:
                remove_prio(p)
            else:
                pass
            i += 1

        next_x = events[i][0] if i < n else None

        if next_x is not None and next_x > x:
            current_cancels = 0
            for cs, ce in cancels:
                if cs < next_x and ce > x:
                    current_cancels += 1

            if current_cancels == 0:
                p = get_max_prio()
                if p is not None:
                    res.append((x, next_x, p))

    if not res:
        return []

    coalesced = [res[0]]
    for start, end, prio in res[1:]:
        p_start, p_end, p_prio = coalesced[-1]
        if p_end == start and p_prio == prio:
            coalesced[-1] = (p_start, end, prio)
        else:
            coalesced.append((start, end, prio))

    return coalesced

def merge_busy2(intervals, cancels):
    """Resolve overlapping prioritized intervals (max prio wins), subtract all
    cancel ranges, and return the minimal sorted list of (start, end, prio)."""
    import heapq
    from collections import defaultdict

    if not intervals:
        return []

    starts = defaultdict(list)
    ends = defaultdict(list)
    cancel_delta = defaultdict(int)
    points = set()

    for s, e, p in intervals:
        starts[s].append(p)
        ends[e].append(p)
        points.add(s)
        points.add(e)

    for s, e in cancels:
        cancel_delta[s] += 1
        cancel_delta[e] -= 1
        points.add(s)
        points.add(e)

    points = sorted(points)

    active = defaultdict(int)   # prio -> number of live intervals with that prio
    heap = []                   # lazily-cleaned max-heap of candidate prios
    covered = 0                 # number of cancels covering the current cell
    result = []

    for i in range(len(points) - 1):
        x, y = points[i], points[i + 1]

        for p in ends[x]:
            active[p] -= 1
        for p in starts[x]:
            active[p] += 1
            heapq.heappush(heap, -p)
        covered += cancel_delta[x]

        while heap and active[-heap[0]] <= 0:
            heapq.heappop(heap)

        if covered > 0 or not heap:
            continue

        prio = -heap[0]
        if result and result[-1][1] == x and result[-1][2] == prio:
            result[-1] = (result[-1][0], y, prio)
        else:
            result.append((x, y, prio))

    return result

import heapq
from collections import Counter

def merge_busy2(intervals, cancels):
    if not intervals:
        return []
    coords = set()
    for s, e, _p in intervals:
        coords.add(s)
        coords.add(e)
    for s, e in cancels:
        coords.add(s)
        coords.add(e)
    coords = sorted(coords)

    merged = []
    for s, e in sorted(cancels):
        if merged and s <= merged[-1][1]:
            if e > merged[-1][1]:
                merged[-1] = (merged[-1][0], e)
        else:
            merged.append((s, e))

    adds = {c: [] for c in coords}
    removes = {c: [] for c in coords}
    for s, e, p in intervals:
        adds[s].append(p)
        removes[e].append(p)

    count = Counter()
    heap = []
    result = []
    for i, c in enumerate(coords):
        for p in removes[c]:
            count[p] -= 1
        for p in adds[c]:
            count[p] += 1
            heapq.heappush(heap, -p)
        while heap and count[-heap[0]] <= 0:
            heapq.heappop(heap)
        if i + 1 >= len(coords):
            break
        nxt = coords[i + 1]
        prio = -heap[0] if heap else None
        cancelled = False
        for sc, ec in merged:
            if c >= ec:
                continue
            if c >= sc and nxt <= ec:
                cancelled = True
            break
        if cancelled or prio is None:
            continue
        if result and result[-1][1] == c and result[-1][2] == prio:
            result[-1] = (result[-1][0], nxt, prio)
        else:
            result.append((c, nxt, prio))
    return result

def merge_busy2(intervals, cancels):
    import heapq

    events = {}
    for index, (start, end, prio) in enumerate(intervals):
        events.setdefault(start, []).append(("add", index, prio))
        events.setdefault(end, []).append(("remove", index, prio))

    for start, end in cancels:
        events.setdefault(start, []).append(("cancel", 1, 0))
        events.setdefault(end, []).append(("cancel", -1, 0))

    if not events:
        return []

    active = set()
    heap = []
    cancel_count = 0
    result = []
    points = sorted(events)

    for i, point in enumerate(points[:-1]):
        for kind, value, prio in events[point]:
            if kind == "add":
                active.add(value)
                heapq.heappush(heap, (-prio, value))
            elif kind == "remove":
                active.discard(value)
            else:
                cancel_count += value

        while heap and heap[0][1] not in active:
            heapq.heappop(heap)

        next_point = points[i + 1]
        if heap and cancel_count == 0 and point < next_point:
            prio = -heap[0][0]
            if result and result[-1][1] == point and result[-1][2] == prio:
                result[-1] = (result[-1][0], next_point, prio)
            else:
                result.append((point, next_point, prio))

    return result

def merge_busy2(intervals, cancels):
    import heapq

    events = {}
    active = [True] * len(intervals)
    heap = []

    for i, (start, end, prio) in enumerate(intervals):
        events.setdefault(start, [[], [], 0])[0].append((i, prio))
        events.setdefault(end, [[], [], 0])[1].append(i)

    for start, end in cancels:
        events.setdefault(start, [[], [], 0])[2] += 1
        events.setdefault(end, [[], [], 0])[2] -= 1

    points = sorted(events)
    result = []
    cancel_count = 0

    for index, x in enumerate(points):
        starts, ends, cancel_delta = events[x]

        for i in ends:
            active[i] = False

        for i, prio in starts:
            heapq.heappush(heap, (-prio, i))

        cancel_count += cancel_delta

        if index + 1 == len(points):
            break

        next_x = points[index + 1]
        while heap and not active[heap[0][1]]:
            heapq.heappop(heap)

        if heap and cancel_count == 0:
            prio = -heap[0][0]
            if result and result[-1][1] == x and result[-1][2] == prio:
                result[-1] = (result[-1][0], next_x, prio)
            else:
                result.append((x, next_x, prio))

    return result

def merge_busy2(intervals, cancels):
    events = {}

    for start, end, prio in intervals:
        events.setdefault(start, []).append((1, prio))
        events.setdefault(end, []).append((-1, prio))

    resolved = []
    active = {}
    previous = None

    for point in sorted(events):
        if previous is not None and previous < point and active:
            prio = max(active)
            if resolved and resolved[-1][1] == previous and resolved[-1][2] == prio:
                resolved[-1] = (resolved[-1][0], point, prio)
            else:
                resolved.append((previous, point, prio))

        for kind, prio in events[point]:
            if kind == 1:
                active[prio] = active.get(prio, 0) + 1
            else:
                active[prio] -= 1
                if active[prio] == 0:
                    del active[prio]

        previous = point

    cancel_events = {}
    for start, end in cancels:
        cancel_events[start] = cancel_events.get(start, 0) + 1
        cancel_events[end] = cancel_events.get(end, 0) - 1

    merged_cancels = []
    depth = 0
    previous = None

    for point in sorted(cancel_events):
        if previous is not None and previous < point and depth:
            merged_cancels.append((previous, point))
        depth += cancel_events[point]
        previous = point

    result = []
    cancel_index = 0

    for start, end, prio in resolved:
        while cancel_index < len(merged_cancels) and merged_cancels[cancel_index][1] <= start:
            cancel_index += 1

        position = start
        index = cancel_index

        while index < len(merged_cancels) and merged_cancels[index][0] < end:
            cancel_start, cancel_end = merged_cancels[index]

            if position < cancel_start:
                segment_end = min(cancel_start, end)
                if result and result[-1][1] == position and result[-1][2] == prio:
                    result[-1] = (result[-1][0], segment_end, prio)
                else:
                    result.append((position, segment_end, prio))

            position = max(position, cancel_end)
            if position >= end:
                break
            index += 1

        if position < end:
            if result and result[-1][1] == position and result[-1][2] == prio:
                result[-1] = (result[-1][0], end, prio)
            else:
                result.append((position, end, prio))

    return result

class RateTree:
    def __init__(self, spec):
        self._capacity = {}
        self._rate = {}
        self._parent = {}
        self._tokens = {}
        self._last = {}

        for name, (capacity, refill_rate, parent) in spec.items():
            self._capacity[name] = float(capacity)
            self._rate[name] = float(refill_rate)
            self._parent[name] = parent
            self._tokens[name] = float(capacity)
            self._last[name] = None

    def allow(self, name: str, n: float = 1.0, now: float = 0.0) -> bool:
        if not (n >= 0.0):
            return False

        path = []
        node = name
        while node is not None:
            path.append(node)
            node = self._parent[node]

        for node in path:
            last = self._last[node]
            if last is None:
                self._last[node] = now
            elif now > last:
                tokens = self._tokens[node] + (now - last) * self._rate[node]
                capacity = self._capacity[node]
                if tokens > capacity:
                    tokens = capacity
                self._tokens[node] = tokens
                self._last[node] = now

        for node in path:
            if self._tokens[node] < n:
                return False

        for node in path:
            self._tokens[node] -= n

        return True

class RateTree:
    def __init__(self, spec):
        self._nodes = {}
        for name, (capacity, refill_rate, parent) in spec.items():
            self._nodes[name] = {
                'capacity': float(capacity),
                'rate': float(refill_rate),
                'parent': parent,
                'tokens': float(capacity),
                'last': 0.0,
            }

    def allow(self, name, n=1.0, now=0.0):
        if name not in self._nodes:
            return False
        path = []
        cur = name
        while cur is not None:
            path.append(cur)
            cur = self._nodes[cur]['parent']
        for nm in path:
            node = self._nodes[nm]
            elapsed = max(0.0, now - node['last'])
            node['tokens'] = min(node['capacity'], node['tokens'] + elapsed * node['rate'])
            if now > node['last']:
                node['last'] = now
        if n > 0.0 and any(self._nodes[nm]['tokens'] < n for nm in path):
            return False
        if n > 0.0:
            for nm in path:
                self._nodes[nm]['tokens'] -= n
        return True

class RateTree:
    """
    A hierarchical token bucket with continuous refill.
    """
    def __init__(self, spec: dict):
        """
        Initialize the RateTree.

        :param spec: dict mapping node name (str) to (capacity, refill_rate, parent).
                     capacity and refill_rate are floats, parent is a string or None.
                     Exactly one node must have parent None (the root).
        """
        self._nodes = {}
        for name, (capacity, refill_rate, parent) in spec.items():
            if capacity < 0 or refill_rate < 0:
                raise ValueError("capacity and refill_rate must be non-negative")
            self._nodes[name] = {
                'capacity': float(capacity),
                'refill_rate': float(refill_rate),
                'parent': parent,
                'tokens': float(capacity),   # start full
                'last_time': 0.0
            }

        # Validate exactly one root
        roots = [n for n, nd in self._nodes.items() if nd['parent'] is None]
        if len(roots) != 1:
            raise ValueError("Exactly one node must have parent None (the root)")

        # Validate all parents exist
        for name, nd in self._nodes.items():
            p = nd['parent']
            if p is not None and p not in self._nodes:
                raise ValueError(f"Parent '{p}' of node '{name}' not found in spec")

    def allow(self, name: str, n: float = 1.0, now: float = 0.0) -> bool:
        """
        Request n tokens from the named bucket and all its ancestors.

        :param name: the node to consume from
        :param n: number of tokens to consume (default 1.0)
        :param now: current time as a float (caller-supplied)
        :return: True if all involved buckets had at least n tokens, False otherwise
        """
        if name not in self._nodes:
            raise KeyError(f"Node '{name}' not found")

        # Build the chain from the target node up to the root
        chain = []
        cur = name
        while cur is not None:
            chain.append(cur)
            cur = self._nodes[cur]['parent']

        # Compute new token counts after continuous refill for each node in chain
        new_tokens = {}
        for node in chain:
            nd = self._nodes[node]
            elapsed = now - nd['last_time']
            if elapsed < 0:
                elapsed = 0.0
            tokens = nd['tokens'] + elapsed * nd['refill_rate']
            if tokens > nd['capacity']:
                tokens = nd['capacity']
            new_tokens[node] = tokens

        # Check if every node in the chain has enough tokens
        if all(t >= n for t in new_tokens.values()):
            # Success: debit all nodes and update their timestamps
            for node in chain:
                nd = self._nodes[node]
                nd['tokens'] = new_tokens[node] - n
                nd['last_time'] = now
            return True
        else:
            # Failure: only update state with refill, no debit
            for node in chain:
                nd = self._nodes[node]
                nd['tokens'] = new_tokens[node]
                nd['last_time'] = now
            return False

class RateTree:
    def __init__(self, spec):
        self.parent = {}
        self.capacity = {}
        self.rate = {}
        self.tokens = {}
        self.last = {}
        for name, (cap, rate, parent) in spec.items():
            self.parent[name] = parent
            self.capacity[name] = cap
            self.rate[name] = rate
            self.tokens[name] = cap
            self.last[name] = None

    def _refill(self, name, now):
        last = self.last[name]
        if last is None:
            self.last[name] = now
        else:
            elapsed = now - last
            if elapsed > 0:
                self.tokens[name] = min(
                    self.capacity[name],
                    self.tokens[name] + elapsed * self.rate[name],
                )
                self.last[name] = now

    def allow(self, name: str, n: float = 1.0, now: float = 0.0) -> bool:
        chain = []
        node = name
        while node is not None:
            chain.append(node)
            node = self.parent[node]
        for node in chain:
            self._refill(node, now)
        if all(self.tokens[node] >= n for node in chain):
            for node in chain:
                self.tokens[node] -= n
            return True
        return False

class RateTree(object):
    def __init__(self, spec):
        self.spec = dict(spec)
        self.tokens = {}
        self.last_time = {}
        for name, (capacity, refill_rate, parent) in self.spec.items():
            self.tokens[name] = capacity
            self.last_time[name] = 0.0

    def _refill(self, name, now):
        capacity, refill_rate, parent = self.spec[name]
        last = self.last_time[name]
        elapsed = now - last
        if elapsed > 0:
            self.tokens[name] = min(capacity, self.tokens[name] + elapsed * refill_rate)
        self.last_time[name] = now

    def _chain(self, name):
        chain = []
        cur = name
        while cur is not None:
            chain.append(cur)
            parent = self.spec[cur][2]
            cur = parent
        return chain

    def allow(self, name, n=1.0, now=0.0):
        chain = self._chain(name)

        for node in chain:
            self._refill(node, now)

        for node in chain:
            if self.tokens[node] < n:
                return False

        for node in chain:
            self.tokens[node] -= n

        return True

class RateTree:
    def __init__(self, spec):
        self.spec = spec
        self.capacity = {}
        self.rate = {}
        self.parent = {}
        self.tokens = {}
        self.last = {}
        for name, (cap, rate, parent) in spec.items():
            self.capacity[name] = cap
            self.rate[name] = rate
            self.parent[name] = parent
            self.tokens[name] = cap
            self.last[name] = None

    def _refill(self, name, now):
        if self.last[name] is None:
            self.last[name] = now
            return
        elapsed = now - self.last[name]
        if elapsed > 0:
            self.tokens[name] = min(
                self.capacity[name],
                self.tokens[name] + elapsed * self.rate[name],
            )
        self.last[name] = now

    def allow(self, name: str, n: float = 1.0, now: float = 0.0) -> bool:
        chain = []
        cur = name
        while cur is not None:
            chain.append(cur)
            cur = self.parent[cur]
        for node in chain:
            self._refill(node, now)
        if all(self.tokens[node] >= n for node in chain):
            for node in chain:
                self.tokens[node] -= n
            return True
        return False

class RateTree:

    class _Node:

        def __init__(self, capacity: float, refill_rate: float, parent: str | None):
            self.capacity = float(capacity)
            self.refill_rate = float(refill_rate)
            self.parent = parent
            self.tokens = float(capacity)
            self.last_update = 0.0

    def __init__(self, spec: dict[str, tuple[float, float, str | None]]):
        self.nodes = {
            name: self._Node(cap, rate, parent)
            for name, (cap, rate, parent) in spec.items()
        }

    def allow(self, name: str, n: float = 1.0, now: float = 0.0) -> bool:
        chain = []
        curr = name
        while curr is not None:
            chain.append(self.nodes[curr])
            curr = self.nodes[curr].parent

        for node in chain:
            if now > node.last_update:
                elapsed = now - node.last_update
                node.tokens = min(
                    node.capacity, node.tokens + elapsed * node.refill_rate
                )
                node.last_update = now

        if all(node.tokens >= n for node in chain):
            for node in chain:
                node.tokens -= n
            return True
        return False

class RateTree:
    class _Node:
        __slots__ = ('name', 'capacity', 'refill_rate', 'parent_name', 'tokens', 'last_time')

        def __init__(self, name: str, capacity: float, refill_rate: float, parent_name: str | None):
            self.name = name
            self.capacity = capacity
            self.refill_rate = refill_rate
            self.parent_name = parent_name
            self.tokens = capacity
            self.last_time = 0.0

        def update(self, now: float) -> None:
            if now > self.last_time:
                elapsed = now - self.last_time
                self.tokens = min(self.capacity, self.tokens + elapsed * self.refill_rate)
                self.last_time = now

    def __init__(self, spec: dict[str, tuple[float, float, str | None]]):
        self.nodes: dict[str, RateTree._Node] = {}
        for name, (capacity, refill_rate, parent) in spec.items():
            self.nodes[name] = self._Node(name, capacity, refill_rate, parent)

    def allow(self, name: str, n: float = 1.0, now: float = 0.0) -> bool:
        path = []
        curr_name: str | None = name
        while curr_name is not None:
            node = self.nodes[curr_name]
            path.append(node)
            curr_name = node.parent_name

        for node in path:
            node.update(now)

        for node in path:
            if node.tokens < n:
                return False

        for node in path:
            node.tokens -= n

        return True

class RateTree:
    """Hierarchical token-bucket limiter: a request debits a node and all its ancestors."""

    def __init__(self, spec):
        self._capacity = {}
        self._rate = {}
        self._tokens = {}
        self._last = {}
        parent = {}

        for name, (capacity, refill_rate, par) in spec.items():
            self._capacity[name] = float(capacity)
            self._rate[name] = float(refill_rate)
            self._tokens[name] = float(capacity)  # every bucket starts full
            self._last[name] = None               # no time seen yet
            parent[name] = par

        roots = [n for n, p in parent.items() if p is None]
        if len(roots) != 1:
            raise ValueError("spec must have exactly one root (parent None)")
        for name, p in parent.items():
            if p is not None and p not in spec:
                raise ValueError("unknown parent %r for node %r" % (p, name))

        # Precompute each node's path to the root; also detects cycles.
        self._paths = {}
        for name in spec:
            path = []
            seen = set()
            cur = name
            while cur is not None:
                if cur in seen:
                    raise ValueError("cycle in spec at node %r" % (cur,))
                seen.add(cur)
                path.append(cur)
                cur = parent[cur]
            self._paths[name] = path

    def _refill(self, name, now):
        """Advance one node's bucket to `now`; time never runs backwards."""
        last = self._last[name]
        if last is None:
            elapsed = 0.0
        else:
            elapsed = now - last
            if elapsed < 0.0:
                elapsed = 0.0
        if elapsed > 0.0:
            tokens = self._tokens[name] + elapsed * self._rate[name]
            cap = self._capacity[name]
            self._tokens[name] = cap if tokens > cap else tokens
        if last is None or now > last:
            self._last[name] = now

    def allow(self, name, n=1.0, now=0.0):
        if name not in self._paths:
            raise KeyError(name)
        n = float(n)
        now = float(now)
        path = self._paths[name]

        # Refill every node on the path: they are all touched by this call.
        for node in path:
            self._refill(node, now)

        # All-or-nothing: check the whole chain before debiting anything.
        for node in path:
            if self._tokens[node] < n:
                return False
        for node in path:
            self._tokens[node] -= n
        return True

class RateTree:
    def __init__(self, spec):
        self.spec = spec
        self.tokens = {}
        self.last = {}
        for name, (capacity, refill_rate, parent) in spec.items():
            self.tokens[name] = capacity
            self.last[name] = 0.0

    def _refill(self, name, now):
        capacity, refill_rate = self.spec[name][0], self.spec[name][1]
        elapsed = now - self.last[name]
        if elapsed > 0:
            self.tokens[name] = min(capacity, self.tokens[name] + elapsed * refill_rate)
            self.last[name] = now

    def allow(self, name, n=1.0, now=0.0):
        chain = []
        cur = name
        while cur is not None:
            chain.append(cur)
            cur = self.spec[cur][2]
        for node in chain:
            self._refill(node, now)
        for node in chain:
            if self.tokens[node] < n:
                return False
        for node in chain:
            self.tokens[node] -= n
        return True

class RateTree:
    def __init__(self, spec):
        self._nodes = {
            name: {
                "capacity": float(capacity),
                "rate": float(refill_rate),
                "parent": parent,
                "tokens": float(capacity),
                "last": 0.0,
            }
            for name, (capacity, refill_rate, parent) in spec.items()
        }

    def allow(self, name: str, n: float = 1.0, now: float = 0.0) -> bool:
        path = []
        current = name

        while current is not None:
            node = self._nodes[current]
            path.append(node)
            current = node["parent"]

        for node in path:
            elapsed = max(0.0, now - node["last"])
            node["tokens"] = min(
                node["capacity"],
                node["tokens"] + elapsed * node["rate"],
            )
            node["last"] = max(node["last"], now)

        if any(node["tokens"] < n for node in path):
            return False

        for node in path:
            node["tokens"] -= n

        return True

class RateTree:
    def __init__(self, spec):
        self._capacity = {name: values[0] for name, values in spec.items()}
        self._refill_rate = {name: values[1] for name, values in spec.items()}
        self._parent = {name: values[2] for name, values in spec.items()}
        self._tokens = dict(self._capacity)
        self._last_seen = {name: 0.0 for name in spec}

    def allow(self, name: str, n: float = 1.0, now: float = 0.0) -> bool:
        path = []
        current = name

        while current is not None:
            path.append(current)
            current = self._parent[current]

        for node in path:
            last = self._last_seen[node]
            elapsed = now - last

            if elapsed > 0:
                self._tokens[node] = min(
                    self._capacity[node],
                    self._tokens[node] + elapsed * self._refill_rate[node],
                )
                self._last_seen[node] = now

        if any(self._tokens[node] < n for node in path):
            return False

        for node in path:
            self._tokens[node] -= n

        return True

class RateTree:
    def __init__(self, spec):
        self._nodes = {}
        for name, (capacity, refill_rate, parent) in spec.items():
            self._nodes[name] = {
                "capacity": float(capacity),
                "refill_rate": float(refill_rate),
                "parent": parent,
                "tokens": float(capacity),
                "last_seen": 0.0,
            }

    def allow(self, name: str, n: float = 1.0, now: float = 0.0) -> bool:
        n = float(n)
        now = float(now)

        path = []
        current = name
        while current is not None:
            path.append(current)
            current = self._nodes[current]["parent"]

        for node_name in path:
            node = self._nodes[node_name]
            elapsed = max(0.0, now - node["last_seen"])
            node["tokens"] = min(
                node["capacity"],
                node["tokens"] + elapsed * node["refill_rate"],
            )
            node["last_seen"] = max(node["last_seen"], now)

        if any(self._nodes[node_name]["tokens"] < n for node_name in path):
            return False

        for node_name in path:
            self._nodes[node_name]["tokens"] -= n

        return True

def parse_ledger(text):
    import re
    from datetime import date

    if not isinstance(text, str):
        return []

    MONTHS = {
        'Jan': 1, 'Feb': 2, 'Mar': 3, 'Apr': 4,
        'May': 5, 'Jun': 6, 'Jul': 7, 'Aug': 8,
        'Sep': 9, 'Oct': 10, 'Nov': 11, 'Dec': 12,
    }
    MONTH_ABBR = '|'.join(MONTHS.keys())

    currency_re = re.compile(r',\s*(INR|USD|EUR)\s*$')
    date_res = [
        re.compile(r'^\s*([0-9]{2}/[0-9]{2}/[0-9]{4})\s*,'),
        re.compile(r'^\s*([0-9]{4}-[0-9]{2}-[0-9]{2})\s*,'),
        re.compile(r'^\s*([0-9]{1,2}\s+(?:' + MONTH_ABBR + r')\s+[0-9]{4})\s*,'),
        re.compile(r'^\s*((?:' + MONTH_ABBR + r')\s+[0-9]{1,2}\s*,\s*[0-9]{4})\s*,'),
    ]
    quoted_desc_re = re.compile(r'^\s*"((?:[^"]|"")*)"\s*,')
    number_re = re.compile(
        r'^(?:[0-9]+(?:\.[0-9]+)?'
        r'|[0-9]{1,3}(?:,[0-9]{2,3})*,[0-9]{3}(?:\.[0-9]+)?'
        r'|\.[0-9]+)$'
    )
    rates = {'INR': 1.0, 'USD': 83.5, 'EUR': 90.25}
    symbols = {'₹', '$', '€'}
    INF = float('inf')

    def normalize_date(raw):
        raw = raw.strip()
        m = re.fullmatch(r'([0-9]{2})/([0-9]{2})/([0-9]{4})', raw)
        if m:
            d, mo, y = (int(x) for x in m.groups())
        else:
            m = re.fullmatch(r'([0-9]{4})-([0-9]{2})-([0-9]{2})', raw)
            if m:
                y, mo, d = (int(x) for x in m.groups())
            else:
                m = re.fullmatch(r'([0-9]{1,2})\s+(' + MONTH_ABBR + r')\s+([0-9]{4})', raw)
                if m:
                    d = int(m.group(1))
                    mo = MONTHS[m.group(2)]
                    y = int(m.group(3))
                else:
                    m = re.fullmatch(r'(' + MONTH_ABBR + r')\s+([0-9]{1,2})\s*,\s*([0-9]{4})', raw)
                    if not m:
                        return None
                    mo = MONTHS[m.group(1)]
                    d = int(m.group(2))
                    y = int(m.group(3))
        try:
            dt = date(y, mo, d)
        except ValueError:
            return None
        return f'{dt.year:04d}-{dt.month:02d}-{dt.day:02d}'

    def parse_amount(s):
        s = s.strip()
        if not s:
            return None

        negative = False
        if s.endswith('DR'):
            negative = True
            s = s[:-2].rstrip()

        symbol_seen = False
        if s and s[0] in symbols:
            symbol_seen = True
            s = s[1:].lstrip()

        if s.startswith('('):
            negative = True
            if not s.endswith(')'):
                return None
            s = s[1:-1].strip()
            if s and s[0] in symbols:
                if symbol_seen:
                    return None
                symbol_seen = True
                s = s[1:].lstrip()
        elif s.endswith(')'):
            return None

        if not number_re.fullmatch(s):
            return None

        try:
            value = float(s.replace(',', ''))
        except (ValueError, OverflowError):
            return None

        if not (-INF < value < INF):
            return None

        if negative:
            value = -value
        if value == 0:
            value = 0.0
        return value

    rows = []
    seen = set()

    for line in text.splitlines():
        line = line.strip()
        if not line:
            continue

        cur_m = currency_re.search(line)
        if not cur_m:
            continue

        currency = cur_m.group(1)
        prefix = line[:cur_m.start()]

        date_m = None
        for rx in date_res:
            date_m = rx.match(prefix)
            if date_m:
                break
        if not date_m:
            continue

        iso_date = normalize_date(date_m.group(1))
        if iso_date is None:
            continue

        rest = prefix[date_m.end():]

        if rest.lstrip().startswith('"'):
            desc_m = quoted_desc_re.match(rest)
            if not desc_m:
                continue
            description = desc_m.group(1).replace('""', '"').strip()
            amount_str = rest[desc_m.end():]
        else:
            parts = rest.split(',', 1)
            if len(parts) < 2:
                continue
            description = parts[0].strip()
            amount_str = parts[1]

        amount = parse_amount(amount_str)
        if amount is None:
            continue

        converted = amount * rates[currency]
        if not (-INF < converted < INF):
            continue

        amount_inr = round(converted, 2)
        if not (-INF < amount_inr < INF):
            continue
        if amount_inr == 0:
            amount_inr = 0.0

        key = (iso_date, description, amount_inr)
        if key in seen:
            continue

        seen.add(key)
        rows.append({
            'date': iso_date,
            'description': description,
            'amount_inr': amount_inr,
        })

    rows.sort(key=lambda r: (r['date'], -abs(r['amount_inr'])))
    return rows

def parse_ledger(text):
    import re
    from datetime import datetime

    month_map = {
        'Jan': 1, 'Feb': 2, 'Mar': 3, 'Apr': 4, 'May': 5, 'Jun': 6,
        'Jul': 7, 'Aug': 8, 'Sep': 9, 'Oct': 10, 'Nov': 11, 'Dec': 12
    }
    rates = {'INR': 1.0, 'USD': 83.5, 'EUR': 90.25}
    date_res = [
        re.compile(r'^(\d{1,2})/(\d{1,2})/(\d{4})\s*,'),
        re.compile(r'^(\d{4})-(\d{2})-(\d{2})\s*,'),
        re.compile(r'^(\d{1,2})\s+(Jan|Feb|Mar|Apr|May|Jun|Jul|Aug|Sep|Oct|Nov|Dec)\s+(\d{4})\s*,', re.I),
        re.compile(r'^(Jan|Feb|Mar|Apr|May|Jun|Jul|Aug|Sep|Oct|Nov|Dec)\s+(\d{1,2}),\s*(\d{4})\s*,', re.I),
    ]
    rows = []
    seen = set()
    order = 0
    for raw in text.splitlines():
        line = raw.strip()
        if not line:
            continue
        for idx, dre in enumerate(date_res):
            m = dre.match(line)
            if not m:
                continue
            try:
                if idx == 0:
                    d, mo, y = int(m.group(1)), int(m.group(2)), int(m.group(3))
                    iso = datetime(y, mo, d).strftime('%Y-%m-%d')
                elif idx == 1:
                    y, mo, d = int(m.group(1)), int(m.group(2)), int(m.group(3))
                    iso = datetime(y, mo, d).strftime('%Y-%m-%d')
                elif idx == 2:
                    d = int(m.group(1))
                    mon = m.group(2).capitalize()
                    y = int(m.group(3))
                    if mon not in month_map:
                        continue
                    iso = datetime(y, month_map[mon], d).strftime('%Y-%m-%d')
                else:
                    mon = m.group(1).capitalize()
                    d = int(m.group(2))
                    y = int(m.group(3))
                    if mon not in month_map:
                        continue
                    iso = datetime(y, month_map[mon], d).strftime('%Y-%m-%d')
            except ValueError:
                continue
            rest = line[m.end():]
            if rest.startswith('"'):
                j = 1
                chars = []
                while j < len(rest):
                    if rest[j] == '"':
                        if j + 1 < len(rest) and rest[j + 1] == '"':
                            chars.append('"')
                            j += 2
                        else:
                            j += 1
                            break
                    else:
                        chars.append(rest[j])
                        j += 1
                else:
                    continue
                desc = ''.join(chars).strip()
                while j < len(rest) and rest[j].isspace():
                    j += 1
                if j >= len(rest) or rest[j] != ',':
                    continue
                after = rest[j + 1:]
            else:
                cpos = rest.find(',')
                if cpos < 0:
                    continue
                desc = rest[:cpos].strip()
                after = rest[cpos + 1:]
            rparts = after.rsplit(',', 1)
            if len(rparts) != 2:
                continue
            amount_part, currency = rparts[0].strip(), rparts[1].strip()
            if currency not in rates:
                continue
            ap = amount_part
            sign = 1.0
            if ap.startswith('(') and ap.endswith(')'):
                sign = -1.0
                ap = ap[1:-1].strip()
            if ap.upper().endswith(' DR'):
                sign = -1.0
                ap = ap[:-3].strip()
            if ap and ap[0] in '₹$€':
                ap = ap[1:].strip()
            ap = ap.replace(',', '')
            if not ap:
                continue
            try:
                val = float(ap) * sign
            except ValueError:
                continue
            amount_inr = round(val * rates[currency], 2)
            key = (iso, desc, amount_inr)
            if key in seen:
                break
            seen.add(key)
            rows.append((iso, desc, amount_inr, order))
            order += 1
            break
    rows.sort(key=lambda r: (r[0], -abs(r[2]), r[3]))
    return [{'date': r[0], 'description': r[1], 'amount_inr': r[2]} for r in rows]

import re

def parse_ledger(text):
    # Month name to number mapping
    MONTH_MAP = {
        'Jan': 1, 'Feb': 2, 'Mar': 3, 'Apr': 4,
        'May': 5, 'Jun': 6, 'Jul': 7, 'Aug': 8,
        'Sep': 9, 'Oct': 10, 'Nov': 11, 'Dec': 12
    }
    RATES = {'INR': 1.0, 'USD': 83.5, 'EUR': 90.25}
    CURRENCIES = {'INR', 'USD', 'EUR'}
    SYMBOLS = '₹$€'

    def parse_date(s):
        s = s.strip()
        # YYYY-MM-DD
        if re.match(r'^\d{4}-\d{2}-\d{2}$', s):
            return s
        # DD/MM/YYYY
        m = re.match(r'^(\d{1,2})/(\d{1,2})/(\d{4})$', s)
        if m:
            d, mo, y = int(m.group(1)), int(m.group(2)), int(m.group(3))
            return f"{y:04d}-{mo:02d}-{d:02d}"
        # D Mon YYYY
        m = re.match(r'^(\d{1,2}) (Jan|Feb|Mar|Apr|May|Jun|Jul|Aug|Sep|Oct|Nov|Dec) (\d{4})$', s)
        if m:
            d = int(m.group(1))
            mo = MONTH_MAP[m.group(2)]
            y = int(m.group(3))
            return f"{y:04d}-{mo:02d}-{d:02d}"
        # Mon D, YYYY (possibly after earlier split that gave whole date field)
        m = re.match(r'^(Jan|Feb|Mar|Apr|May|Jun|Jul|Aug|Sep|Oct|Nov|Dec) (\d{1,2}), (\d{4})$', s)
        if m:
            mo = MONTH_MAP[m.group(1)]
            d = int(m.group(2))
            y = int(m.group(3))
            return f"{y:04d}-{mo:02d}-{d:02d}"
        return None

    def parse_rest(s):
        """Parse description, amount, currency from the rest of the line after the date separator."""
        s = s.strip()
        if not s:
            return None
        if s.startswith('"'):
            # quoted description
            i = 1
            desc_chars = []
            while i < len(s):
                if s[i] == '"':
                    if i + 1 < len(s) and s[i + 1] == '"':
                        desc_chars.append('"')
                        i += 2
                    else:
                        # end of quoted field
                        i += 1
                        break
                else:
                    desc_chars.append(s[i])
                    i += 1
            else:
                # no closing quote
                return None
            if i >= len(s) or s[i] != ',':
                return None
            rest = s[i + 1:]
            description = ''.join(desc_chars).strip()
        else:
            # unquoted description
            comma_idx = s.find(',')
            if comma_idx == -1:
                return None
            description = s[:comma_idx].strip()
            rest = s[comma_idx + 1:]
        # Now rest should be amount,currency
        # Find last comma to split amount and currency
        last_comma = rest.rfind(',')
        if last_comma == -1:
            return None
        amount_str = rest[:last_comma].strip()
        currency_str = rest[last_comma + 1:].strip()
        return description, amount_str, currency_str

    def parse_amount(amount_str, currency_str):
        """Parse numeric value from amount_str, return (value, currency) or None."""
        if currency_str not in CURRENCIES:
            return None
        s = amount_str.strip()
        if not s:
            return None
        negative = False
        # DR suffix
        if s.endswith(' DR'):
            negative = True
            s = s[:-3].strip()
        # parentheses
        if s.startswith('(') and s.endswith(')'):
            negative = True
            s = s[1:-1].strip()
        # remove leading currency symbol (if present)
        if s and s[0] in SYMBOLS:
            s = s[1:].strip()
        # remove thousands commas
        s = s.replace(',', '')
        try:
            value = float(s)
        except ValueError:
            return None
        if negative:
            value = -value
        return value

    # Pattern for date format "Mon D, YYYY," at the start of a line (with trailing comma that is the field separator)
    mon_d_yyyy_pattern = re.compile(
        r'^((?:Jan|Feb|Mar|Apr|May|Jun|Jul|Aug|Sep|Oct|Nov|Dec) \d{1,2}, \d{4}),'
    )

    seen = set()
    rows = []

    for raw_line in text.splitlines():
        line = raw_line.strip()
        if not line:
            continue

        # --- extract date and the rest of the line ---
        m = mon_d_yyyy_pattern.match(line)
        if m:
            date_str = m.group(1)
            rest = line[m.end():]
        else:
            parts = line.split(',', 1)
            if len(parts) != 2:
                continue
            date_str, rest = parts

        date_iso = parse_date(date_str)
        if date_iso is None:
            continue

        parsed = parse_rest(rest)
        if parsed is None:
            continue
        description, amount_str, currency_str = parsed

        value = parse_amount(amount_str, currency_str)
        if value is None:
            continue

        amount_inr = round(value * RATES[currency_str], 2)

        key = (date_iso, description, amount_inr)
        if key in seen:
            continue
        seen.add(key)
        rows.append({
            'date': date_iso,
            'description': description,
            'amount_inr': amount_inr
        })

    # sort: date ascending, then absolute amount_inr descending
    rows.sort(key=lambda r: (r['date'], -abs(r['amount_inr'])))
    return rows

def parse_ledger(text):
    import re
    months = {m: i + 1 for i, m in enumerate(
        ["Jan", "Feb", "Mar", "Apr", "May", "Jun",
         "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"])}
    rates = {"INR": 1, "USD": 83.5, "EUR": 90.25}

    def tokenize(line):
        tokens = []
        i, N = 0, len(line)
        done = False
        while not done:
            j = i
            while j < N and line[j] == " ":
                j += 1
            if j < N and line[j] == '"':
                j += 1
                buf = []
                closed = False
                while j < N:
                    if line[j] == '"':
                        if j + 1 < N and line[j + 1] == '"':
                            buf.append('"')
                            j += 2
                        else:
                            j += 1
                            closed = True
                            break
                    else:
                        buf.append(line[j])
                        j += 1
                if not closed:
                    return None
                while j < N and line[j] != ",":
                    if line[j] != " ":
                        return None
                    j += 1
                tokens.append(("".join(buf), True))
                if j < N:
                    i = j + 1
                else:
                    done = True
            else:
                k = line.find(",", i)
                if k == -1:
                    tokens.append((line[i:], False))
                    done = True
                else:
                    tokens.append((line[i:k], False))
                    i = k + 1
        return tokens

    def parse_date(s):
        s = s.strip()
        m = re.fullmatch(r"(\d{2})/(\d{2})/(\d{4})", s)
        if m:
            d, mo, y = int(m[1]), int(m[2]), int(m[3])
        else:
            m = re.fullmatch(r"(\d{4})-(\d{2})-(\d{2})", s)
            if m:
                y, mo, d = int(m[1]), int(m[2]), int(m[3])
            else:
                m = re.fullmatch(r"(\d{1,2}) ([A-Za-z]{3}) (\d{4})", s)
                if m and m[2] in months:
                    d, mo, y = int(m[1]), months[m[2]], int(m[3])
                else:
                    m = re.fullmatch(r"([A-Za-z]{3}) (\d{1,2}), ?(\d{4})", s)
                    if not m or m[1] not in months:
                        return None
                    mo, d, y = months[m[1]], int(m[2]), int(m[3])
        if not (1 <= mo <= 12 and 1 <= d <= 31):
            return None
        return f"{y:04d}-{mo:02d}-{d:02d}"

    def parse_amount(s):
        s = s.strip()
        neg = False
        if s.endswith(" DR"):
            neg = True
            s = s[:-3].strip()
        if s.startswith("(") and s.endswith(")"):
            neg = True
            s = s[1:-1].strip()
        if s[:1] in ("₹", "$", "€"):
            s = s[1:].strip()
        if not re.fullmatch(r"\d{1,3}(,\d{3})*(\.\d+)?|\d+(\.\d+)?", s):
            return None
        val = float(s.replace(",", ""))
        return -val if neg else val

    rows = []
    seen = set()
    for line in text.splitlines():
        if not line.strip():
            continue
        tokens = tokenize(line)
        if tokens is None or len(tokens) < 4:
            continue
        cur = tokens[-1][0].strip()
        if tokens[-1][1] or cur not in rates:
            continue
        if tokens[0][1]:
            continue
        date = parse_date(tokens[0][0])
        di = 1
        if date is None:
            if len(tokens) >= 5 and not tokens[1][1]:
                date = parse_date(tokens[0][0] + "," + tokens[1][0])
                di = 2
            if date is None:
                continue
        if len(tokens) - 1 - (di + 1) < 1:
            continue
        desc = tokens[di][0].strip()
        amount_tokens = tokens[di + 1:-1]
        if any(q for _, q in amount_tokens):
            continue
        val = parse_amount(",".join(v for v, _ in amount_tokens))
        if val is None:
            continue
        amount_inr = round(val * rates[cur], 2)
        key = (date, desc, amount_inr)
        if key in seen:
            continue
        seen.add(key)
        rows.append({"date": date, "description": desc, "amount_inr": amount_inr})
    rows.sort(key=lambda r: (r["date"], -abs(r["amount_inr"])))
    return rows

import re
from datetime import date

def parse_ledger(text):
    months = {
        'Jan': 1, 'Feb': 2, 'Mar': 3, 'Apr': 4, 'May': 5, 'Jun': 6,
        'Jul': 7, 'Aug': 8, 'Sep': 9, 'Oct': 10, 'Nov': 11, 'Dec': 12
    }
    rates = {'INR': 1.0, 'USD': 83.5, 'EUR': 90.25}

    re_slash = re.compile(r'^(\d{1,2})/(\d{1,2})/(\d{4})')
    re_iso = re.compile(r'^(\d{4})-(\d{2})-(\d{2})')
    re_mon_day_comma = re.compile(r'^([A-Za-z]{3}) (\d{1,2}), (\d{4})')
    re_day_mon = re.compile(r'^(\d{1,2}) ([A-Za-z]{3}) (\d{4})')

    def norm_month(abbr):
        key = abbr[:1].upper() + abbr[1:].lower()
        return months.get(key)

    def parse_date(line):
        m = re_slash.match(line)
        if m:
            d, mo, y = int(m.group(1)), int(m.group(2)), int(m.group(3))
            try:
                iso = date(y, mo, d).isoformat()
            except ValueError:
                return None
            return iso, m.end()

        m = re_iso.match(line)
        if m:
            y, mo, d = int(m.group(1)), int(m.group(2)), int(m.group(3))
            try:
                iso = date(y, mo, d).isoformat()
            except ValueError:
                return None
            return iso, m.end()

        m = re_mon_day_comma.match(line)
        if m:
            mo = norm_month(m.group(1))
            d, y = int(m.group(2)), int(m.group(3))
            if mo is None:
                return None
            try:
                iso = date(y, mo, d).isoformat()
            except ValueError:
                return None
            return iso, m.end()

        m = re_day_mon.match(line)
        if m:
            d = int(m.group(1))
            mo = norm_month(m.group(2))
            y = int(m.group(3))
            if mo is None:
                return None
            try:
                iso = date(y, mo, d).isoformat()
            except ValueError:
                return None
            return iso, m.end()

        return None

    def parse_quoted(s, start):
        i = start + 1
        n = len(s)
        out = []
        while i < n:
            c = s[i]
            if c == '"':
                if i + 1 < n and s[i + 1] == '"':
                    out.append('"')
                    i += 2
                    continue
                else:
                    return ''.join(out), i + 1
            else:
                out.append(c)
                i += 1
        return None, None

    def parse_amount(s):
        s = s.strip()
        if not s:
            raise ValueError("empty amount")
        if s[0] in '₹$€':
            s = s[1:].strip()
        negative = False
        if s.startswith('(') and s.endswith(')'):
            negative = True
            s = s[1:-1].strip()
            if s and s[0] in '₹$€':
                s = s[1:].strip()
        if s.endswith(' DR'):
            negative = True
            s = s[:-3].strip()
        elif s.endswith('DR'):
            negative = True
            s = s[:-2].strip()
        s = s.replace(',', '')
        val = float(s)
        if negative:
            val = -val
        return val

    results = []
    seen = set()

    for raw_line in text.splitlines():
        if not raw_line.strip():
            continue
        try:
            line = raw_line.strip()

            dr = parse_date(line)
            if dr is None:
                continue
            iso_date, consumed = dr

            if consumed >= len(line) or line[consumed] != ',':
                continue
            remainder = line[consumed + 1:]

            if remainder.startswith('"'):
                desc, pos = parse_quoted(remainder, 0)
                if desc is None:
                    continue
                if pos >= len(remainder) or remainder[pos] != ',':
                    continue
                rest2 = remainder[pos + 1:]
            else:
                idx = remainder.find(',')
                if idx == -1:
                    continue
                desc = remainder[:idx]
                rest2 = remainder[idx + 1:]

            description = desc.strip()

            last_comma = rest2.rfind(',')
            if last_comma == -1:
                continue
            amount_str = rest2[:last_comma]
            currency_str = rest2[last_comma + 1:].strip()

            if currency_str not in rates:
                continue

            amount = parse_amount(amount_str)
            amount_inr = round(amount * rates[currency_str], 2)

            key = (iso_date, description, amount_inr)
            if key in seen:
                continue
            seen.add(key)

            results.append({
                "date": iso_date,
                "description": description,
                "amount_inr": amount_inr
            })
        except Exception:
            continue

    results.sort(key=lambda r: (r["date"], -abs(r["amount_inr"])))
    return results

def parse_ledger(text):
    import re

    months = {
        "jan": 1, "feb": 2, "mar": 3, "apr": 4, "may": 5, "jun": 6,
        "jul": 7, "aug": 8, "sep": 9, "oct": 10, "nov": 11, "dec": 12,
    }
    rates = {"INR": 1.0, "USD": 83.5, "EUR": 90.25}

    date_re = re.compile(
        r"\s*("
        r"\d{1,2}/\d{1,2}/\d{4}"
        r"|\d{4}-\d{1,2}-\d{1,2}"
        r"|\d{1,2}\s+[A-Za-z]{3}\s+\d{4}"
        r"|[A-Za-z]{3}\s+\d{1,2},\s*\d{4}"
        r")\s*,"
    )

    def parse_date(s):
        s = s.strip()
        m = re.fullmatch(r"(\d{1,2})/(\d{1,2})/(\d{4})", s)
        if m:
            d, mo, y = int(m.group(1)), int(m.group(2)), int(m.group(3))
        else:
            m = re.fullmatch(r"(\d{4})-(\d{1,2})-(\d{1,2})", s)
            if m:
                y, mo, d = int(m.group(1)), int(m.group(2)), int(m.group(3))
            else:
                m = re.fullmatch(r"(\d{1,2})\s+([A-Za-z]{3})\s+(\d{4})", s)
                if m:
                    d, mon, y = int(m.group(1)), m.group(2).lower(), int(m.group(3))
                    if mon not in months:
                        return None
                    mo = months[mon]
                else:
                    m = re.fullmatch(r"([A-Za-z]{3})\s+(\d{1,2}),\s*(\d{4})", s)
                    if not m:
                        return None
                    mon, d, y = m.group(1).lower(), int(m.group(2)), int(m.group(3))
                    if mon not in months:
                        return None
                    mo = months[mon]
        if not (1 <= mo <= 12 and 1 <= d <= 31):
            return None
        return "%04d-%02d-%02d" % (y, mo, d)

    def parse_amount(s):
        s = s.strip()
        negative = False
        if s.startswith("(") and s.endswith(")"):
            negative = True
            s = s[1:-1].strip()
        elif s.endswith("DR"):
            negative = True
            s = s[:-2].strip()
        if s and s[0] in "₹$€":
            s = s[1:].strip()
        s = s.replace(",", "")
        if not re.fullmatch(r"\d+(\.\d+)?", s):
            return None
        val = float(s)
        return -val if negative else val

    rows = []
    seen = set()
    for line in text.splitlines():
        if not line.strip():
            continue
        m = date_re.match(line)
        if not m:
            continue
        date = parse_date(m.group(1))
        if date is None:
            continue
        rest = line[m.end():]

        k = 0
        while k < len(rest) and rest[k] in " \t":
            k += 1
        if k < len(rest) and rest[k] == '"':
            k += 1
            buf = []
            closed = False
            while k < len(rest):
                c = rest[k]
                if c == '"':
                    if k + 1 < len(rest) and rest[k + 1] == '"':
                        buf.append('"')
                        k += 2
                    else:
                        k += 1
                        closed = True
                        break
                else:
                    buf.append(c)
                    k += 1
            if not closed:
                continue
            j = rest.find(",", k)
            if j == -1 or rest[k:j].strip() != "":
                continue
            desc = "".join(buf).strip()
            rest2 = rest[j + 1:]
        else:
            j = rest.find(",")
            if j == -1:
                continue
            desc = rest[:j].strip()
            rest2 = rest[j + 1:]

        if "," not in rest2:
            continue
        amount_str, currency = rest2.rsplit(",", 1)
        currency = currency.strip()
        if currency not in rates:
            continue
        val = parse_amount(amount_str)
        if val is None:
            continue
        amount_inr = round(val * rates[currency], 2)

        key = (date, desc, amount_inr)
        if key in seen:
            continue
        seen.add(key)
        rows.append({"date": date, "description": desc, "amount_inr": amount_inr})

    return sorted(rows, key=lambda r: (r["date"], -abs(r["amount_inr"])))

import datetime
import re


def parse_ledger(text):
    if not isinstance(text, str):
        return []

    months = {
        "jan": 1,
        "feb": 2,
        "mar": 3,
        "apr": 4,
        "may": 5,
        "jun": 6,
        "jul": 7,
        "aug": 8,
        "sep": 9,
        "oct": 10,
        "nov": 11,
        "dec": 12,
    }

    rates = {"INR": 1.0, "USD": 83.5, "EUR": 90.25}

    # Date regexes matching start of line up to the separator comma
    pat_a = re.compile(
        r"^(?P<mon>[A-Za-z]{3})\s+(?P<day>\d{1,2}),\s*(?P<year>\d{4})\s*,"
    )
    pat_b = re.compile(
        r"^(?P<day>\d{1,2})\s+(?P<mon>[A-Za-z]{3})\s+(?P<year>\d{4})\s*,"
    )
    pat_c = re.compile(
        r"^(?P<day>\d{1,2})/(?P<month>\d{1,2})/(?P<year>\d{4})\s*,"
    )
    pat_d = re.compile(
        r"^(?P<year>\d{4})-(?P<month>\d{1,2})-(?P<day>\d{1,2})\s*,"
    )

    rows = []
    seen = set()

    for line in text.splitlines():
        line = line.strip()
        if not line:
            continue

        dt_match = None
        match_type = None
        for p_type, pat in [
            ("A", pat_a),
            ("B", pat_b),
            ("C", pat_c),
            ("D", pat_d),
        ]:
            m = pat.match(line)
            if m:
                dt_match = m
                match_type = p_type
                break

        if not dt_match:
            continue

        try:
            if match_type in ("A", "B"):
                m_str = dt_match.group("mon").lower()
                if m_str not in months:
                    continue
                month = months[m_str]
                day = int(dt_match.group("day"))
                year = int(dt_match.group("year"))
            else:
                month = int(dt_match.group("month"))
                day = int(dt_match.group("day"))
                year = int(dt_match.group("year"))

            dt = datetime.date(year, month, day)
            date_str = dt.strftime("%Y-%m-%d")
        except ValueError:
            continue

        rem = line[dt_match.end() :].strip()

        curr_match = re.search(r",\s*(INR|USD|EUR)\s*$", rem)
        if not curr_match:
            continue

        currency = curr_match.group(1)
        desc_and_amt = rem[: curr_match.start()].strip()
        if not desc_and_amt:
            continue

        if desc_and_amt.startswith('"'):
            i = 1
            desc_chars = []
            closed = False
            while i < len(desc_and_amt):
                if desc_and_amt[i] == '"':
                    if (
                        i + 1 < len(desc_and_amt)
                        and desc_and_amt[i + 1] == '"'
                    ):
                        desc_chars.append('"')
                        i += 2
                    else:
                        closed = True
                        i += 1
                        break
                else:
                    desc_chars.append(desc_and_amt[i])
                    i += 1
            if not closed:
                continue
            desc = "".join(desc_chars).strip()
            rest = desc_and_amt[i:].lstrip()
            if not rest.startswith(","):
                continue
            amt_str = rest[1:].strip()
        else:
            if "," not in desc_and_amt:
                continue
            desc_part, amt_str = desc_and_amt.split(",", 1)
            desc = desc_part.strip()
            amt_str = amt_str.strip()

        try:
            s = amt_str
            if not s:
                continue
            is_neg = False
            if "(" in s and ")" in s:
                is_neg = True
                s = s.replace("(", "").replace(")", "")
            if re.search(r"\bDR\b", s, re.IGNORECASE):
                is_neg = True
                s = re.sub(r"\bDR\b", "", s, flags=re.IGNORECASE)
            if "-" in s:
                is_neg = True
                s = s.replace("-", "")
            s = re.sub(r"[₹$€,]", "", s).strip()
            if not s:
                continue
            val = float(s)
            if is_neg:
                val = -val
        except ValueError:
            continue

        amount_inr = round(val * rates[currency], 2) + 0.0

        dedup_key = (date_str, desc, amount_inr)
        if dedup_key in seen:
            continue
        seen.add(dedup_key)

        rows.append(
            {"date": date_str, "description": desc, "amount_inr": amount_inr}
        )

    rows.sort(key=lambda r: (r["date"], -abs(r["amount_inr"])))
    return rows

import csv
from datetime import datetime
import io
import re


def parse_ledger(text):
    MONTHS = {
        "Jan": 1,
        "Feb": 2,
        "Mar": 3,
        "Apr": 4,
        "May": 5,
        "Jun": 6,
        "Jul": 7,
        "Aug": 8,
        "Sep": 9,
        "Oct": 10,
        "Nov": 11,
        "Dec": 12,
    }
    RATES = {"INR": 1.0, "USD": 83.5, "EUR": 90.25}

    results = []
    seen = set()

    for row in csv.reader(io.StringIO(text)):
        if not row or not any(row):
            continue
        if len(row) != 4:
            continue

        date_str, desc_str, amt_str, curr_str = [c.strip() for c in row]
        desc_str = desc_str.strip()

        # Currency
        currency = curr_str.upper()
        if currency not in RATES:
            continue

        # Date normalization
        norm_date = None
        # 1. DD/MM/YYYY
        m = re.match(r"^(\d{1,2})/(\d{1,2})/(\d{4})$", date_str)
        if m:
            d, mo, y = int(m.group(1)), int(m.group(2)), int(m.group(3))
            try:
                norm_date = datetime(y, mo, d).strftime("%Y-%m-%d")
            except ValueError:
                pass

        # 2. YYYY-MM-DD
        if not norm_date:
            m = re.match(r"^(\d{4})-(\d{1,2})-(\d{1,2})$", date_str)
            if m:
                y, mo, d = int(m.group(1)), int(m.group(2)), int(m.group(3))
                try:
                    norm_date = datetime(y, mo, d).strftime("%Y-%m-%d")
                except ValueError:
                    pass

        # 3. D Mon YYYY (e.g. 3 Jan 2026)
        if not norm_date:
            m = re.match(r"^(\d{1,2})\s+([A-Za-z]{3})\s+(\d{4})$", date_str)
            if m:
                d, mon_str, y = int(m.group(1)), m.group(2).capitalize(), int(m.group(3))
                if mon_str in MONTHS:
                    try:
                        norm_date = datetime(y, MONTHS[mon_str], d).strftime("%Y-%m-%d")
                    except ValueError:
                        pass

        # 4. Mon D, YYYY (e.g. Jan 3, 2026)
        if not norm_date:
            m = re.match(r"^([A-Za-z]{3})\s+(\d{1,2}),\s+(\d{4})$", date_str)
            if m:
                mon_str, d, y = m.group(1).capitalize(), int(m.group(2)), int(m.group(3))
                if mon_str in MONTHS:
                    try:
                        norm_date = datetime(y, MONTHS[mon_str], d).strftime("%Y-%m-%d")
                    except ValueError:
                        pass

        if not norm_date:
            continue

        # Amount parsing
        a_clean = amt_str.replace(" ", "")
        is_negative = False
        if a_clean.startswith("(") and a_clean.endswith(")"):
            is_negative = True
            a_clean = a_clean[1:-1]
        elif a_clean.endswith("DR") or a_clean.endswith("dr"):
            is_negative = True
            a_clean = a_clean[:-2]

        # Strip symbols
        for sym in ["₹", "$", "€"]:
            a_clean = a_clean.replace(sym, "")

        a_clean = a_clean.replace(",", "")

        try:
            val = float(a_clean)
        except ValueError:
            continue

        if is_negative:
            val = -val

        amount_inr = round(val * RATES[currency], 2)

        key = (norm_date, desc_str, amount_inr)
        if key in seen:
            continue
        seen.add(key)

        results.append(
            {"date": norm_date, "description": desc_str, "amount_inr": amount_inr}
        )

    results.sort(key=lambda x: (x["date"], -abs(x["amount_inr"])))
    return results

def parse_ledger(text):
    import re
    from datetime import date as _date

    MONTHS = {m: i for i, m in enumerate(
        ["Jan", "Feb", "Mar", "Apr", "May", "Jun",
         "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"], 1)}
    RATES = {"INR": 1.0, "USD": 83.5, "EUR": 90.25}
    SYMBOLS = ("\u20b9", "$", "\u20ac")  # rupee, dollar, euro
    _mon = "|".join(MONTHS)

    # (pattern, kind); each is anchored at the start of the line
    DATE_PATTERNS = [
        (re.compile(r"\s*(\d{1,2})/(\d{1,2})/(\d{4})"), "dmy"),
        (re.compile(r"\s*(\d{4})-(\d{1,2})-(\d{1,2})"), "ymd"),
        (re.compile(r"\s*(\d{1,2})\s+(%s)\s+(\d{4})" % _mon), "dmy_name"),
        (re.compile(r"\s*(%s)\s+(\d{1,2}),\s*(\d{4})" % _mon), "mdy_name"),
    ]
    AMOUNT_RE = re.compile(r"\d{1,3}(?:,\d{3})*(?:\.\d+)?|\d+(?:\.\d+)?")

    def parse_date(line):
        """Return (iso_date, index_just_after_the_field_separator) or None."""
        for pat, kind in DATE_PATTERNS:
            m = pat.match(line)
            if not m:
                continue
            j = m.end()
            while j < len(line) and line[j] in " \t":
                j += 1
            if j >= len(line) or line[j] != ",":
                continue  # date must be followed by a field separator
            a, b, c = m.groups()
            if kind == "dmy":
                y, mo, d = int(c), int(b), int(a)
            elif kind == "ymd":
                y, mo, d = int(a), int(b), int(c)
            elif kind == "dmy_name":
                y, mo, d = int(c), MONTHS[b], int(a)
            else:  # mdy_name
                y, mo, d = int(c), MONTHS[a], int(b)
            try:
                return _date(y, mo, d).isoformat(), j + 1
            except ValueError:
                return None
        return None

    def parse_description(line, i):
        """Return (description, index_just_after_the_field_separator) or None."""
        j = i
        while j < len(line) and line[j] in " \t":
            j += 1
        if j < len(line) and line[j] == '"':
            out = []
            j += 1
            closed = False
            while j < len(line):
                ch = line[j]
                if ch == '"':
                    if j + 1 < len(line) and line[j + 1] == '"':
                        out.append('"')
                        j += 2
                        continue
                    j += 1
                    closed = True
                    break
                out.append(ch)
                j += 1
            if not closed:
                return None
            while j < len(line) and line[j] in " \t":
                j += 1
            if j >= len(line) or line[j] != ",":
                return None
            return "".join(out).strip(), j + 1
        k = line.find(",", i)
        if k == -1:
            return None
        return line[i:k].strip(), k + 1

    def parse_amount(s):
        s = s.strip()
        neg = False
        if s.endswith(" DR"):
            neg = True
            s = s[:-3].strip()
        for _ in range(2):  # handles "(<sym>N)" and "<sym>(N)"
            if len(s) >= 2 and s.startswith("(") and s.endswith(")"):
                neg = True
                s = s[1:-1].strip()
            if s[:1] in SYMBOLS:
                s = s[1:].strip()
        if not s or not AMOUNT_RE.fullmatch(s):
            return None
        val = float(s.replace(",", ""))
        return -val if neg else val

    rows = []
    seen = set()
    for line in text.splitlines():
        if not line.strip():
            continue
        got = parse_date(line)
        if got is None:
            continue
        iso, i = got
        got = parse_description(line, i)
        if got is None:
            continue
        desc, i = got
        rest = line[i:]
        if "," not in rest:
            continue
        amt_str, cur = rest.rsplit(",", 1)
        cur = cur.strip()
        if cur not in RATES:
            continue
        amt = parse_amount(amt_str)
        if amt is None:
            continue
        amount_inr = round(amt * RATES[cur], 2)
        key = (iso, desc, amount_inr)
        if key in seen:
            continue
        seen.add(key)
        rows.append({"date": iso, "description": desc, "amount_inr": amount_inr})

    return sorted(rows, key=lambda r: (r["date"], -abs(r["amount_inr"])))

import re

_MONTHS = {name: i + 1 for i, name in enumerate([
    "Jan", "Feb", "Mar", "Apr", "May", "Jun",
    "Jul", "Aug", "Sep", "Oct", "Nov", "Dec",
])}

_RATES = {"INR": 1.0, "USD": 83.5, "EUR": 90.25}

_LINE = re.compile(
    r'''^\s*
        (?P<date>
            (?P<d1>\d{1,2})/(?P<m1>\d{1,2})/(?P<y1>\d{4})
          | (?P<y2>\d{4})-(?P<m2>\d{2})-(?P<d2>\d{2})
          | (?P<d3>\d{1,2})\s+(?P<mn3>[A-Za-z]{3})\s+(?P<y3>\d{4})
          | (?P<mn4>[A-Za-z]{3})\s+(?P<d4>\d{1,2}),\s*(?P<y4>\d{4})
        )
        \s*,\s*
        (?P<desc>
            (?P<q>"(?:[^"]|"")*")
          | (?P<u>[^",]*)
        )
        \s*,\s*
        (?P<amount>
            \(?\s*[$€₹]?\s*\d+(?:,\d{3})*(?:\.\d+)?\s*\)?\s*(?:DR)?
        )
        \s*,\s*
        (?P<currency>INR|USD|EUR)
        \s*$''',
    re.VERBOSE,
)


def _parse_date(m):
    if m.group("d1") is not None:
        return f"{int(m.group('y1')):04d}-{int(m.group('m1')):02d}-{int(m.group('d1')):02d}"
    if m.group("y2") is not None:
        return f"{int(m.group('y2')):04d}-{int(m.group('m2')):02d}-{int(m.group('d2')):02d}"
    if m.group("mn3") is not None:
        month = _MONTHS.get(m.group("mn3").title())
        if month is None:
            return None
        return f"{int(m.group('y3')):04d}-{month:02d}-{int(m.group('d3')):02d}"
    if m.group("mn4") is not None:
        month = _MONTHS.get(m.group("mn4").title())
        if month is None:
            return None
        return f"{int(m.group('y4')):04d}-{month:02d}-{int(m.group('d4')):02d}"
    return None


def _parse_amount(s):
    raw = s.strip()
    negative = False
    if raw.endswith("DR"):
        raw = raw[:-2].strip()
        negative = True
    if raw.startswith("("):
        if not raw.endswith(")"):
            return None
        raw = raw[1:-1].strip()
        negative = True
    elif raw.endswith(")"):
        return None
    for sym in ("₹", "$", "€"):
        if raw.startswith(sym):
            raw = raw[1:].strip()
            break
    try:
        value = float(raw.replace(",", ""))
    except ValueError:
        return None
    return -value if negative else value


def parse_ledger(text):
    rows = []
    seen = set()
    for line in text.splitlines():
        if not line.strip():
            continue
        m = _LINE.match(line)
        if m is None:
            continue
        date = _parse_date(m)
        if date is None:
            continue
        if m.group("q") is not None:
            description = m.group("q")[1:-1].replace('""', '"')
        else:
            description = m.group("u")
        description = description.strip()
        amount = _parse_amount(m.group("amount"))
        if amount is None:
            continue
        amount_inr = round(amount * _RATES[m.group("currency")], 2)
        key = (date, description, amount_inr)
        if key in seen:
            continue
        seen.add(key)
        rows.append({"date": date, "description": description, "amount_inr": amount_inr})
    rows.sort(key=lambda r: (r["date"], -abs(r["amount_inr"])))
    return rows

def parse_ledger(text):
    import re
    from datetime import datetime

    rates = {"INR": 1, "USD": 83.5, "EUR": 90.25}
    date_pattern = re.compile(
        r"^\s*(?P<date>"
        r"\d{2}/\d{2}/\d{4}|"
        r"\d{4}-\d{2}-\d{2}|"
        r"\d{1,2} (?:Jan|Feb|Mar|Apr|May|Jun|Jul|Aug|Sep|Oct|Nov|Dec) \d{4}|"
        r"(?:Jan|Feb|Mar|Apr|May|Jun|Jul|Aug|Sep|Oct|Nov|Dec) \d{1,2}, \d{4}"
        r")\s*,(?P<rest>.*)$"
    )
    amount_pattern = re.compile(
        r"^\s*(?P<paren>\()?\s*[₹$€]?\s*"
        r"(?P<number>(?:\d+|\d{1,3}(?:,\d{3})+)(?:\.\d+)?)"
        r"\s*(?(paren)\))\s*(?P<dr>DR)?\s*$"
    )

    def normalize_date(value):
        formats = (
            "%d/%m/%Y",
            "%Y-%m-%d",
            "%d %b %Y",
            "%b %d, %Y",
        )
        for fmt in formats:
            try:
                return datetime.strptime(value, fmt).date().isoformat()
            except ValueError:
                pass
        return None

    rows = []
    seen = set()

    for line in text.splitlines():
        if not line.strip():
            continue

        match = date_pattern.fullmatch(line)
        if not match:
            continue

        date = normalize_date(match.group("date"))
        if date is None:
            continue

        rest = match.group("rest").lstrip()
        if rest.startswith('"'):
            index = 1
            description_chars = []
            valid = False

            while index < len(rest):
                if rest[index] == '"':
                    if index + 1 < len(rest) and rest[index + 1] == '"':
                        description_chars.append('"')
                        index += 2
                    else:
                        index += 1
                        valid = True
                        break
                else:
                    description_chars.append(rest[index])
                    index += 1

            if not valid:
                continue

            tail = rest[index:]
            separator = re.match(r"^\s*,(.*)$", tail)
            if not separator:
                continue

            description = "".join(description_chars).strip()
            amount_and_currency = separator.group(1)
        else:
            parts = rest.split(",", 1)
            if len(parts) != 2:
                continue
            description = parts[0].strip()
            amount_and_currency = parts[1]

        amount_parts = amount_and_currency.rsplit(",", 1)
        if len(amount_parts) != 2:
            continue

        amount_text, currency = amount_parts
        currency = currency.strip()
        if currency not in rates:
            continue

        amount_match = amount_pattern.fullmatch(amount_text)
        if not amount_match:
            continue

        amount = float(amount_match.group("number").replace(",", ""))
        if amount_match.group("paren") or amount_match.group("dr"):
            amount = -amount

        amount_inr = round(amount * rates[currency], 2)
        key = (date, description, amount_inr)
        if key in seen:
            continue

        seen.add(key)
        rows.append({
            "date": date,
            "description": description,
            "amount_inr": amount_inr,
        })

    rows.sort(key=lambda row: (row["date"], -abs(row["amount_inr"])))
    return rows

def parse_ledger(text):
    import csv
    import io
    import re
    from datetime import date

    month_map = {
        "Jan": 1, "Feb": 2, "Mar": 3, "Apr": 4,
        "May": 5, "Jun": 6, "Jul": 7, "Aug": 8,
        "Sep": 9, "Oct": 10, "Nov": 11, "Dec": 12,
    }
    rates = {"INR": 1, "USD": 83.5, "EUR": 90.25}

    def parse_date(value):
        value = value.strip()
        match = re.fullmatch(r"(\d{2})/(\d{2})/(\d{4})", value)
        if match:
            day, month, year = map(int, match.groups())
        else:
            match = re.fullmatch(r"(\d{4})-(\d{2})-(\d{2})", value)
            if match:
                year, month, day = map(int, match.groups())
            else:
                match = re.fullmatch(r"(\d{1,2}) ([A-Z][a-z]{2}) (\d{4})", value)
                if match:
                    day, mon, year = match.groups()
                    month = month_map.get(mon)
                    day, year = int(day), int(year)
                else:
                    match = re.fullmatch(r"([A-Z][a-z]{2}) (\d{1,2}), (\d{4})", value)
                    if not match:
                        return None
                    mon, day, year = match.groups()
                    month = month_map.get(mon)
                    day, year = int(day), int(year)

        try:
            return date(year, month, day).isoformat()
        except (TypeError, ValueError):
            return None

    def parse_amount(value, currency):
        value = value.strip()
        value = re.sub(r"^[₹$€]\s*", "", value)

        negative = False
        if value.startswith("(") and value.endswith(")"):
            negative = True
            value = value[1:-1].strip()
        elif re.search(r"\s+DR$", value):
            negative = True
            value = value[:-3].strip()

        if not re.fullmatch(r"(?:\d+|\d{1,3}(?:,\d{3})+)(?:\.\d+)?", value):
            return None

        amount = float(value.replace(",", ""))
        if negative:
            amount = -amount
        return round(amount * rates[currency], 2)

    rows = []
    seen = set()

    for line in text.splitlines():
        if not line.strip():
            continue

        try:
            fields = next(csv.reader(io.StringIO(line), strict=True))
        except (csv.Error, StopIteration):
            continue

        if len(fields) == 5:
            candidate_date = f"{fields[0].strip()}, {fields[1].strip()}"
            if parse_date(candidate_date) is not None:
                fields = [candidate_date] + fields[2:]

        if len(fields) != 4:
            continue

        date_value, description, amount, currency = fields
        date_value = parse_date(date_value)
        currency = currency.strip()

        if date_value is None or currency not in rates:
            continue

        amount_inr = parse_amount(amount, currency)
        if amount_inr is None:
            continue

        row = (date_value, description.strip(), amount_inr)
        if row in seen:
            continue

        seen.add(row)
        rows.append({
            "date": row[0],
            "description": row[1],
            "amount_inr": row[2],
        })

    rows.sort(key=lambda row: (row["date"], -abs(row["amount_inr"])))
    return rows

def parse_ledger(text):
    import csv
    import io
    import re
    from datetime import datetime

    rates = {"INR": 1, "USD": 83.5, "EUR": 90.25}
    months = "Jan|Feb|Mar|Apr|May|Jun|Jul|Aug|Sep|Oct|Nov|Dec"
    date_patterns = [
        (re.compile(r"^\s*(\d{2}/\d{2}/\d{4})\s*,(.*)$"), "%d/%m/%Y"),
        (re.compile(r"^\s*(\d{4}-\d{2}-\d{2})\s*,(.*)$"), "%Y-%m-%d"),
        (re.compile(rf"^\s*(\d{{1,2}}\s+(?:{months})\s+\d{{4}})\s*,(.*)$"), "%d %b %Y"),
        (re.compile(rf"^\s*((?:{months})\s+\d{{1,2}},\s*\d{{4}})\s*,(.*)$"), "%b %d, %Y"),
    ]

    rows = []
    seen = set()

    for line in text.splitlines():
        if not line.strip():
            continue

        for pattern, fmt in date_patterns:
            match = pattern.match(line)
            if match:
                break
        else:
            continue

        try:
            date = datetime.strptime(match.group(1).strip(), fmt).strftime("%Y-%m-%d")
            fields = next(csv.reader(io.StringIO(match.group(2)), skipinitialspace=True, strict=True))
            if len(fields) != 3:
                continue

            description, amount, currency = fields
            description = description.strip()
            currency = currency.strip()
            if currency not in rates:
                continue

            amount = amount.strip()
            negative = False
            if amount.upper().endswith(" DR"):
                negative = True
                amount = amount[:-3].strip()

            if amount.startswith("(") and amount.endswith(")"):
                negative = True
                amount = amount[1:-1].strip()

            amount = amount.lstrip("₹$€").replace(",", "").strip()
            value = float(amount)
            if negative:
                value = -value

            amount_inr = round(value * rates[currency], 2)
            key = (date, description, amount_inr)
            if key not in seen:
                seen.add(key)
                rows.append({"date": date, "description": description, "amount_inr": amount_inr})
        except (ValueError, csv.Error, StopIteration):
            continue

    return sorted(rows, key=lambda row: (row["date"], -abs(row["amount_inr"])))

class LRUCache:
    def __init__(self, capacity, ttl):
        self.capacity = capacity
        self.ttl = ttl
        self._data = {}     # key -> (value, stored_time)
        self._order = []    # least-recently-used first

    def _expired(self, key, now):
        return now - self._data[key][1] > self.ttl

    def _clean_order(self):
        seen = set()
        kept = []
        for key in self._order:
            if key in self._data and key not in seen:
                seen.add(key)
                kept.append(key)
        self._order[:] = kept

    def _purge(self, now):
        expired = [key for key in self._data if self._expired(key, now)]
        for key in expired:
            del self._data[key]
        self._clean_order()

    def _touch(self, key):
        self._order[:] = [k for k in self._order if k != key]
        self._order.append(key)

    def put(self, key, value, now):
        if self.capacity <= 0:
            return

        if key in self._data:
            self._data[key] = (value, now)
            self._touch(key)
            return

        if len(self._data) >= self.capacity:
            self._purge(now)

        if len(self._data) >= self.capacity:
            while self._order:
                victim = self._order.pop(0)
                if victim in self._data:
                    del self._data[victim]
                    break
            else:
                if self._data:
                    self._data.pop(next(iter(self._data)))
            self._clean_order()

        self._data[key] = (value, now)
        self._order.append(key)

    def get(self, key, now):
        if key not in self._data:
            return None
        if self._expired(key, now):
            return None

        value = self._data[key][0]
        self._touch(key)
        return value

    def size(self, now):
        return sum(1 for key in self._data if not self._expired(key, now))

class LRUCache:
    def __init__(self, capacity, ttl):
        self.capacity = capacity
        self.ttl = ttl
        self._data = {}  # key -> (value, stored_time)
        self._order = []  # least-recently-used first

    def _expired(self, key, now):
        return now - self._data[key][1] > self.ttl

    def _purge(self, now):
        new_order = []
        for k in self._order:
            if k in self._data and not self._expired(k, now):
                new_order.append(k)
            elif k in self._data:
                del self._data[k]
        self._order = new_order

    def put(self, key, value, now):
        if key in self._data:
            self._data[key] = (value, now)
            if key in self._order:
                self._order.remove(key)
            self._order.append(key)
            return
        if len(self._data) >= self.capacity:
            self._purge(now)
        if len(self._data) >= self.capacity:
            if self._order:
                victim = self._order.pop(0)
                if victim in self._data:
                    del self._data[victim]
        self._data[key] = (value, now)
        self._order.append(key)

    def get(self, key, now):
        if key not in self._data:
            return None
        if self._expired(key, now):
            return None
        if key in self._order:
            self._order.remove(key)
        self._order.append(key)
        return self._data[key][0]

    def size(self, now):
        self._purge(now)
        return len(self._data)

class LRUCache:
    def __init__(self, capacity, ttl):
        self.capacity = capacity
        self.ttl = ttl
        self._data = {}     # key -> (value, stored_time)
        self._order = []    # least-recently-used first (index 0 is LRU)

    def _expired(self, key, now):
        _, stored_time = self._data[key]
        return now - stored_time > self.ttl   # strict greater

    def _purge(self, now):
        # remove all expired entries while preserving order of the rest
        kept = []
        for k in self._order:
            if k in self._data and not self._expired(k, now):
                kept.append(k)
            else:
                if k in self._data:
                    del self._data[k]
        self._order = kept

    def put(self, key, value, now):
        if key in self._data:
            # update existing key
            self._data[key] = (value, now)
            # make it most-recently-used
            self._order.remove(key)
            self._order.append(key)
            return

        # new key – may need to free space
        if len(self._data) >= self.capacity:
            self._purge(now)

        if len(self._data) >= self.capacity:
            # still full – evict least-recently-used (first in list)
            victim = self._order.pop(0)
            del self._data[victim]

        self._data[key] = (value, now)
        self._order.append(key)

    def get(self, key, now):
        if key not in self._data:
            return None
        if self._expired(key, now):
            return None

        # make it most-recently-used
        self._order.remove(key)
        self._order.append(key)
        return self._data[key][0]

    def size(self, now):
        # count only non-expired entries
        count = 0
        for k in self._data:
            if not self._expired(k, now):
                count += 1
        return count

class LRUCache:
    def __init__(self, capacity, ttl):
        self.capacity = capacity
        self.ttl = ttl
        self._data = {}     # key -> (value, stored_time)
        self._order = []    # least-recently-used first

    def _expired(self, key, now):
        return now - self._data[key][1] > self.ttl

    def _purge(self, now):
        for k in list(self._order):
            if k in self._data and self._expired(k, now):
                del self._data[k]
                self._order.remove(k)

    def put(self, key, value, now):
        if key in self._data:
            self._data[key] = (value, now)
            self._order.remove(key)
            self._order.append(key)
            return
        if len(self._data) >= self.capacity:
            self._purge(now)
        if len(self._data) >= self.capacity:
            victim = self._order.pop(0)
            del self._data[victim]
        self._data[key] = (value, now)
        self._order.append(key)

    def get(self, key, now):
        if key not in self._data:
            return None
        if self._expired(key, now):
            del self._data[key]
            self._order.remove(key)
            return None
        self._order.remove(key)
        self._order.append(key)
        return self._data[key][0]

    def size(self, now):
        return sum(1 for k in self._data if not self._expired(k, now))

class LRUCache:
    def __init__(self, capacity, ttl):
        self.capacity = capacity
        self.ttl = ttl
        self._data = {}     # key -> (value, stored_time)
        self._order = []    # least-recently-used first

    def _expired(self, key, now):
        return now - self._data[key][1] > self.ttl

    def _purge(self, now):
        for k in list(self._order):
            if k in self._data and self._expired(k, now):
                del self._data[k]
                self._order.remove(k)

    def _touch(self, key):
        self._order.remove(key)
        self._order.append(key)

    def put(self, key, value, now):
        if key in self._data:
            self._data[key] = (value, now)
            self._touch(key)
            return
        if len(self._data) >= self.capacity:
            self._purge(now)
        if len(self._data) >= self.capacity:
            victim = self._order.pop(0)
            del self._data[victim]
        self._data[key] = (value, now)
        self._order.append(key)

    def get(self, key, now):
        if key not in self._data:
            return None
        if self._expired(key, now):
            del self._data[key]
            self._order.remove(key)
            return None
        self._touch(key)
        return self._data[key][0]

    def size(self, now):
        return sum(1 for k in self._data if not self._expired(k, now))

class LRUCache:
    def __init__(self, capacity, ttl):
        self.capacity = capacity
        self.ttl = ttl
        self._data = {}     # key -> (value, stored_time)
        self._order = []    # least-recently-used first

    def _expired(self, key, now):
        return now - self._data[key][1] > self.ttl

    def _touch(self, key):
        self._order.remove(key)
        self._order.append(key)

    def _purge(self, now):
        for k in list(self._order):
            if k in self._data and self._expired(k, now):
                del self._data[k]
                self._order.remove(k)

    def put(self, key, value, now):
        if key in self._data:
            self._data[key] = (value, now)
            self._touch(key)
            return
        if len(self._data) >= self.capacity:
            self._purge(now)
        if len(self._data) >= self.capacity:
            victim = self._order.pop(0)
            del self._data[victim]
        self._data[key] = (value, now)
        self._order.append(key)

    def get(self, key, now):
        if key not in self._data:
            return None
        if self._expired(key, now):
            del self._data[key]
            self._order.remove(key)
            return None
        self._touch(key)
        return self._data[key][0]

    def size(self, now):
        return sum(1 for k in self._data if not self._expired(k, now))

from collections import OrderedDict


class LRUCache:
    def __init__(self, capacity, ttl):
        self.capacity = capacity
        self.ttl = ttl
        self._data = OrderedDict()  # key -> (value, stored_time)

    def _is_expired(self, stored_time, now):
        return now - stored_time > self.ttl

    def put(self, key, value, now):
        if key not in self._data:
            if len(self._data) >= self.capacity:
                expired_keys = [
                    k for k, (_, t) in self._data.items() if self._is_expired(t, now)
                ]
                for k in expired_keys:
                    del self._data[k]

                if len(self._data) >= self.capacity:
                    self._data.popitem(last=False)

        self._data[key] = (value, now)
        self._data.move_to_end(key)

    def get(self, key, now):
        if key not in self._data:
            return None
        value, stored_time = self._data[key]
        if self._is_expired(stored_time, now):
            del self._data[key]
            return None
        self._data.move_to_end(key)
        return value

    def size(self, now):
        return sum(
            1 for _, stored_time in self._data.values() if not self._is_expired(stored_time, now)
        )

class LRUCache:
    def __init__(self, capacity, ttl):
        self.capacity = capacity
        self.ttl = ttl
        self._data = {}     # key -> (value, stored_time)
        self._order = []    # least-recently-used first

    def _expired(self, key, now):
        return now - self._data[key][1] > self.ttl

    def _purge(self, now):
        expired_keys = [k for k in self._order if now - self._data[k][1] > self.ttl]
        for k in expired_keys:
            del self._data[k]
            self._order.remove(k)

    def put(self, key, value, now):
        if key in self._data:
            self._data[key] = (value, now)
            self._order.remove(key)
            self._order.append(key)
            return

        self._purge(now)
        
        if len(self._data) >= self.capacity:
            while self._order and self._order[0] not in self._data:
                self._order.pop(0)
            if self._order:
                victim = self._order.pop(0)
                if victim in self._data:
                    del self._data[victim]

        self._data[key] = (value, now)
        self._order.append(key)

    def get(self, key, now):
        if key not in self._data:
            return None
        if self._expired(key, now):
            del self._data[key]
            if key in self._order:
                self._order.remove(key)
            return None
        self._order.remove(key)
        self._order.append(key)
        return self._data[key][0]

    def size(self, now):
        self._purge(now)
        return len(self._data)

class LRUCache:
    def __init__(self, capacity, ttl):
        self.capacity = capacity
        self.ttl = ttl
        self._data = {}     # key -> (value, stored_time)
        self._order = []    # least-recently-used first

    def _expired(self, key, now):
        return now - self._data[key][1] > self.ttl

    def _touch(self, key):
        if key in self._order:
            self._order.remove(key)
        self._order.append(key)

    def _drop(self, key):
        self._data.pop(key, None)
        if key in self._order:
            self._order.remove(key)

    def _purge(self, now):
        for k in list(self._order):
            if k in self._data and self._expired(k, now):
                self._drop(k)

    def put(self, key, value, now):
        if key in self._data:
            self._data[key] = (value, now)
            self._touch(key)
            return
        if len(self._data) >= self.capacity:
            self._purge(now)
        while len(self._data) >= self.capacity and self._order:
            self._drop(self._order[0])
        self._data[key] = (value, now)
        self._touch(key)

    def get(self, key, now):
        if key not in self._data:
            return None
        if self._expired(key, now):
            self._drop(key)
            return None
        self._touch(key)
        return self._data[key][0]

    def size(self, now):
        return sum(1 for k in self._data if not self._expired(k, now))

class LRUCache:
    def __init__(self, capacity, ttl):
        self.capacity = capacity
        self.ttl = ttl
        self._data = {}     # key -> (value, stored_time)
        self._order = []    # least-recently-used first

    def _expired(self, key, now):
        return now - self._data[key][1] > self.ttl

    def _purge(self, now):
        for k in list(self._order):
            if k in self._data and self._expired(k, now):
                del self._data[k]
                self._order.remove(k)

    def _make_mru(self, key):
        self._order.remove(key)
        self._order.append(key)

    def put(self, key, value, now):
        if key in self._data:
            self._data[key] = (value, now)
            self._make_mru(key)
            return
        if len(self._data) >= self.capacity:
            self._purge(now)
        if len(self._data) >= self.capacity:
            victim = self._order.pop(0)
            del self._data[victim]
        self._data[key] = (value, now)
        self._order.append(key)

    def get(self, key, now):
        if key not in self._data:
            return None
        if self._expired(key, now):
            return None
        self._make_mru(key)
        return self._data[key][0]

    def size(self, now):
        self._purge(now)
        return len(self._data)

class LRUCache:
    def __init__(self, capacity, ttl):
        self.capacity = capacity
        self.ttl = ttl
        self._data = {}     # key -> (value, stored_time)
        self._order = []    # least-recently-used first

    def _expired(self, key, now):
        return now - self._data[key][1] > self.ttl

    def _purge(self, now):
        expired = [k for k in self._order if self._expired(k, now)]
        for k in expired:
            del self._data[k]
        self._order = [k for k in self._order if k in self._data]

    def put(self, key, value, now):
        if key in self._data:
            self._data[key] = (value, now)
            self._order.remove(key)
            self._order.append(key)
            return

        if self.capacity <= 0:
            return

        if len(self._data) >= self.capacity:
            self._purge(now)

        if len(self._data) >= self.capacity:
            victim = self._order.pop(0)
            del self._data[victim]

        self._data[key] = (value, now)
        self._order.append(key)

    def get(self, key, now):
        if key not in self._data:
            return None

        if self._expired(key, now):
            del self._data[key]
            self._order.remove(key)
            return None

        self._order.remove(key)
        self._order.append(key)
        return self._data[key][0]

    def size(self, now):
        self._purge(now)
        return len(self._data)

class LRUCache:
    def __init__(self, capacity, ttl):
        self.capacity = capacity
        self.ttl = ttl
        self._data = {}     # key -> (value, stored_time)
        self._order = []    # least-recently-used first

    def _expired(self, key, now):
        return now - self._data[key][1] > self.ttl

    def _purge(self, now):
        expired = [k for k in self._order if self._expired(k, now)]
        for k in expired:
            del self._data[k]
            self._order.remove(k)

    def put(self, key, value, now):
        if self.capacity <= 0:
            return

        if key in self._data:
            self._data[key] = (value, now)
            self._order.remove(key)
            self._order.append(key)
            return

        if len(self._data) >= self.capacity:
            self._purge(now)

        if len(self._data) >= self.capacity:
            victim = self._order.pop(0)
            del self._data[victim]

        self._data[key] = (value, now)
        self._order.append(key)

    def get(self, key, now):
        if key not in self._data:
            return None

        if self._expired(key, now):
            del self._data[key]
            self._order.remove(key)
            return None

        value = self._data[key][0]
        self._order.remove(key)
        self._order.append(key)
        return value

    def size(self, now):
        self._purge(now)
        return len(self._data)

class LRUCache:
    def __init__(self, capacity, ttl):
        self.capacity = capacity
        self.ttl = ttl
        self._data = {}     # key -> (value, stored_time)
        self._order = []    # least-recently-used first

    def _expired(self, key, now):
        return now - self._data[key][1] > self.ttl

    def _purge(self, now):
        expired = [k for k in self._order
                   if k in self._data and self._expired(k, now)]
        for k in expired:
            del self._data[k]
            self._order.remove(k)

    def put(self, key, value, now):
        if key in self._data:
            self._data[key] = (value, now)
            self._order.remove(key)
            self._order.append(key)
            return

        if len(self._data) >= self.capacity:
            self._purge(now)

        if len(self._data) >= self.capacity:
            victim = self._order.pop(0)
            del self._data[victim]

        self._data[key] = (value, now)
        self._order.append(key)

    def get(self, key, now):
        if key not in self._data:
            return None

        if self._expired(key, now):
            del self._data[key]
            self._order.remove(key)
            return None

        self._order.remove(key)
        self._order.append(key)
        return self._data[key][0]

    def size(self, now):
        self._purge(now)
        return len(self._data)

def max_load(events):
    if not events:
        return (0, 0)

    changes = []
    append = changes.append
    for start, end, weight in events:
        append((start, weight))
        append((end, -weight))

    changes.sort(key=lambda x: x[0])

    current = 0
    peak = 0
    peak_time = 0
    i = 0
    n = len(changes)

    while i < n:
        t = changes[i][0]
        delta = 0
        while i < n and changes[i][0] == t:
            delta += changes[i][1]
            i += 1

        current += delta
        if current > peak:
            peak = current
            peak_time = t

    return (peak, peak_time)

def max_load(events):
    if not events:
        return (0, 0)
    changes = []
    for s, e, w in events:
        changes.append((s, w))
        changes.append((e, -w))
    changes.sort(key=lambda x: (x[0], x[1]))
    current = 0
    peak = 0
    peak_t = 0
    i = 0
    n = len(changes)
    while i < n:
        t = changes[i][0]
        while i < n and changes[i][0] == t:
            current += changes[i][1]
            i += 1
        if current > peak:
            peak = current
            peak_t = t
    return (peak, peak_t)

def max_load(events):
    if not events:
        return (0, 0)
    
    # Create a list of (time, delta) for all start and end points
    changes = []
    for start, end, weight in events:
        changes.append((start, weight))
        changes.append((end, -weight))
    
    # Sort by time; order of deltas at the same time does not affect the final sum
    changes.sort(key=lambda x: x[0])
    
    max_load = -1
    peak_time = None
    current_load = 0
    i = 0
    n = len(changes)
    
    while i < n:
        t = changes[i][0]
        # apply all changes occurring at time t
        while i < n and changes[i][0] == t:
            current_load += changes[i][1]
            i += 1
        # after all changes at time t, we have the load on [t, next_time)
        if current_load > max_load:
            max_load = current_load
            peak_time = t
            
    return (max_load, peak_time)

def max_load(events):
    if not events:
        return (0, 0)
    deltas = {}
    for s, e, w in events:
        deltas[s] = deltas.get(s, 0) + w
        deltas[e] = deltas.get(e, 0) - w
    peak = 0
    peak_t = 0
    load = 0
    for t in sorted(deltas):
        load += deltas[t]
        if load > peak:
            peak = load
            peak_t = t
    return (peak, peak_t)

def max_load(events):
    if not events:
        return (0, 0)

    points = []
    for start, end, weight in events:
        points.append((start, 1, weight))
        points.append((end, 0, weight))

    points.sort(key=lambda p: (p[0], p[1]))

    load = 0
    peak = 0
    peak_t = None

    i = 0
    n = len(points)
    while i < n:
        t = points[i][0]
        j = i
        while j < n and points[j][0] == t:
            if points[j][1] == 0:
                load -= points[j][2]
            else:
                load += points[j][2]
            j += 1
        if load > peak:
            peak = load
            peak_t = t
        i = j

    if peak_t is None:
        peak_t = 0

    return (peak, peak_t)

def max_load(events):
    if not events:
        return (0, 0)
    deltas = {}
    for s, e, w in events:
        deltas[s] = deltas.get(s, 0) + w
        deltas[e] = deltas.get(e, 0) - w
    peak = 0
    peak_t = 0
    cur = 0
    for t in sorted(deltas):
        cur += deltas[t]
        if cur > peak:
            peak = cur
            peak_t = t
    return (peak, peak_t)

def max_load(events):
    if not events:
        return (0, 0)

    changes = {}
    for start, end, weight in events:
        changes[start] = changes.get(start, 0) + weight
        changes[end] = changes.get(end, 0) - weight

    max_l = 0
    best_t = 0
    curr_l = 0

    for t in sorted(changes.keys()):
        curr_l += changes[t]
        if curr_l > max_l:
            max_l = curr_l
            best_t = t

    return (max_l, best_t)

def max_load(events):
    if not events:
        return (0, 0)

    points = []
    for start, end, weight in events:
        points.append((start, weight))
        points.append((end, -weight))

    # Sort by time. If times are equal, process 'end' events (-weight)
    # before 'start' events (+weight) to correctly handle half-open intervals [start, end).
    points.sort(key=lambda x: (x[0], x[1]))

    max_peak = 0
    earliest_t = 0
    current_load = 0
    i = 0
    n = len(points)

    while i < n:
        current_time = points[i][0]
        # Process all point changes happening at the exact same 'current_time'
        while i < n and points[i][0] == current_time:
            current_load += points[i][1]
            i += 1

        if current_load > max_peak:
            max_peak = current_load
            earliest_t = current_time

    return (max_peak, earliest_t)

def max_load(events):
    """Peak instantaneous load and the earliest time it is reached.

    Sweep line over the 2n endpoints: an event contributes +w at `start`
    and -w at `end` (half-open [start, end)). All deltas sharing a
    coordinate are applied together before sampling the load, so the
    value seen at time t is exactly the load on [t, next_t). O(n log n).
    """
    if not events:
        return (0, 0)

    deltas = []
    for start, end, weight in events:
        deltas.append((start, weight))
        deltas.append((end, -weight))
    deltas.sort()

    peak = 0
    peak_time = 0
    load = 0
    i = 0
    n = len(deltas)
    while i < n:
        t = deltas[i][0]
        while i < n and deltas[i][0] == t:
            load += deltas[i][1]
            i += 1
        if load > peak:
            peak = load
            peak_time = t

    return (peak, peak_time)

def max_load(events):
    if not events:
        return (0, 0)
    points = []
    for s, e, w in events:
        points.append((s, w))
        points.append((e, -w))
    points.sort()
    load = 0
    peak = 0
    peak_t = 0
    i = 0
    n = len(points)
    while i < n:
        t = points[i][0]
        while i < n and points[i][0] == t:
            load += points[i][1]
            i += 1
        if load > peak:
            peak = load
            peak_t = t
    return (peak, peak_t)

def max_load(events):
    if not events:
        return (0, 0)

    changes = {}
    for start, end, weight in events:
        changes[start] = changes.get(start, 0) + weight
        changes[end] = changes.get(end, 0) - weight

    load = peak = 0
    earliest = 0

    for time in sorted(changes):
        load += changes[time]
        if load > peak:
            peak = load
            earliest = time

    return (peak, earliest)

def max_load(events):
    if not events:
        return (0, 0)

    deltas = []
    for start, end, weight in events:
        deltas.append((start, weight))
        deltas.append((end, -weight))

    deltas.sort()

    load = 0
    peak = 0
    peak_time = 0
    i = 0

    while i < len(deltas):
        time = deltas[i][0]
        while i < len(deltas) and deltas[i][0] == time:
            load += deltas[i][1]
            i += 1

        if load > peak:
            peak = load
            peak_time = time

    return (peak, peak_time)

def max_load(events):
    if not events:
        return (0, 0)

    changes = {}
    for start, end, weight in events:
        changes[start] = changes.get(start, 0) + weight
        changes[end] = changes.get(end, 0) - weight

    load = peak = 0
    earliest = 0
    for time in sorted(changes):
        load += changes[time]
        if load > peak:
            peak = load
            earliest = time

    return (peak, earliest)

WITH product_revenue AS (
    SELECT
        st.city,
        strftime('%Y-%m', sa.sold_on) AS month,
        sa.product,
        SUM(sa.amount) AS revenue
    FROM sales AS sa
    JOIN stores AS st
      ON st.id = sa.store_id
    WHERE sa.store_id IS NOT NULL
      AND st.city IS NOT NULL
      AND sa.product IS NOT NULL
      AND strftime('%Y-%m', sa.sold_on) IS NOT NULL
    GROUP BY
        st.city,
        strftime('%Y-%m', sa.sold_on),
        sa.product
),
ranked AS (
    SELECT
        city,
        month,
        product,
        revenue,
        ROUND(
            100.0 * revenue / NULLIF(SUM(revenue) OVER (PARTITION BY city, month), 0),
            1
        ) AS share,
        RANK() OVER (
            PARTITION BY city, month
            ORDER BY revenue DESC
        ) AS rnk
    FROM product_revenue
)
SELECT
    city,
    month,
    product,
    revenue,
    share
FROM ranked
WHERE rnk <= 2
ORDER BY
    city ASC,
    month ASC,
    revenue DESC,
    product ASC;

WITH filtered AS (
  SELECT s.city,
         strftime('%Y-%m', sa.sold_on) AS month,
         sa.product,
         sa.amount
  FROM sales sa
  JOIN stores s ON sa.store_id = s.id
  WHERE sa.store_id IS NOT NULL
    AND s.city IS NOT NULL
    AND sa.product IS NOT NULL
),
agg AS (
  SELECT city,
         month,
         product,
         SUM(amount) AS revenue
  FROM filtered
  GROUP BY city, month, product
),
ranked AS (
  SELECT city,
         month,
         product,
         revenue,
         SUM(revenue) OVER (PARTITION BY city, month) AS total,
         RANK() OVER (PARTITION BY city, month ORDER BY revenue DESC) AS rnk
  FROM agg
)
SELECT city,
       month,
       product,
       revenue,
       ROUND(100.0 * revenue / total, 1) AS share
FROM ranked
WHERE rnk <= 2
ORDER BY city ASC, month ASC, revenue DESC, product ASC;

WITH product_revenue AS (
    SELECT s.city,
           strftime('%Y-%m', sa.sold_on) AS month,
           sa.product,
           SUM(sa.amount) AS revenue
    FROM sales sa
    JOIN stores s ON sa.store_id = s.id
    WHERE sa.store_id IS NOT NULL
      AND s.city IS NOT NULL
      AND sa.product IS NOT NULL
    GROUP BY s.city, strftime('%Y-%m', sa.sold_on), sa.product
),
ranked AS (
    SELECT city, month, product, revenue,
           RANK() OVER (PARTITION BY city, month ORDER BY revenue DESC) AS rnk,
           COALESCE(ROUND(100.0 * revenue / NULLIF(SUM(revenue) OVER (PARTITION BY city, month), 0), 1), 0.0) AS share
    FROM product_revenue
)
SELECT city, month, product, revenue, share
FROM ranked
WHERE rnk <= 2
ORDER BY city ASC, month ASC, revenue DESC, product ASC;

WITH per AS (
    SELECT c.city AS city,
           substr(s.sold_on, 1, 7) AS month,
           s.product AS product,
           SUM(s.amount) AS revenue
    FROM sales s
    JOIN stores c ON c.id = s.store_id
    WHERE c.city IS NOT NULL
      AND s.product IS NOT NULL
    GROUP BY c.city, substr(s.sold_on, 1, 7), s.product
), ranked AS (
    SELECT city, month, product, revenue,
           RANK() OVER (PARTITION BY city, month ORDER BY revenue DESC) AS rnk,
           SUM(revenue) OVER (PARTITION BY city, month) AS total
    FROM per
)
SELECT city, month, product, revenue,
       ROUND(100.0 * revenue / total, 1) AS share
FROM ranked
WHERE rnk <= 2
ORDER BY city ASC, month ASC, revenue DESC, product ASC;

WITH filtered AS (
    SELECT s.city AS city,
           substr(sa.sold_on, 1, 7) AS month,
           sa.product AS product,
           sa.amount AS amount
    FROM sales sa
    JOIN stores s ON s.id = sa.store_id
    WHERE sa.store_id IS NOT NULL
      AND s.city IS NOT NULL
      AND sa.product IS NOT NULL
),
product_totals AS (
    SELECT city, month, product, SUM(amount) AS revenue
    FROM filtered
    GROUP BY city, month, product
),
city_month_totals AS (
    SELECT city, month, SUM(revenue) AS total_revenue
    FROM product_totals
    GROUP BY city, month
),
ranked AS (
    SELECT pt.city AS city,
           pt.month AS month,
           pt.product AS product,
           pt.revenue AS revenue,
           RANK() OVER (PARTITION BY pt.city, pt.month ORDER BY pt.revenue DESC) AS rnk,
           cmt.total_revenue AS total_revenue
    FROM product_totals pt
    JOIN city_month_totals cmt
      ON cmt.city = pt.city AND cmt.month = pt.month
)
SELECT city,
       month,
       product,
       revenue,
       ROUND(100.0 * revenue / total_revenue, 1) AS share
FROM ranked
WHERE rnk <= 2
ORDER BY city ASC, month ASC, revenue DESC, product ASC;

WITH base AS (
  SELECT s.city AS city,
         strftime('%Y-%m', sa.sold_on) AS month,
         sa.product AS product,
         SUM(sa.amount) AS revenue
  FROM sales sa
  JOIN stores s ON s.id = sa.store_id
  WHERE sa.store_id IS NOT NULL
    AND s.city IS NOT NULL
    AND sa.product IS NOT NULL
  GROUP BY s.city, strftime('%Y-%m', sa.sold_on), sa.product
),
ranked AS (
  SELECT city, month, product, revenue,
         RANK() OVER (PARTITION BY city, month ORDER BY revenue DESC) AS rnk,
         SUM(revenue) OVER (PARTITION BY city, month) AS total
  FROM base
)
SELECT city, month, product, revenue,
       ROUND(100.0 * revenue / total, 1) AS share
FROM ranked
WHERE rnk <= 2
ORDER BY city ASC, month ASC, revenue DESC, product ASC;

WITH product_revenue AS (
    SELECT
        stores.city AS city,
        strftime('%Y-%m', sales.sold_on) AS month,
        sales.product AS product,
        SUM(sales.amount) AS revenue
    FROM sales
    JOIN stores ON sales.store_id = stores.id
    WHERE sales.store_id IS NOT NULL
      AND stores.city IS NOT NULL
      AND sales.product IS NOT NULL
    GROUP BY stores.city, strftime('%Y-%m', sales.sold_on), sales.product
),
ranked_products AS (
    SELECT
        city,
        month,
        product,
        revenue,
        ROUND(100.0 * revenue / SUM(revenue) OVER (PARTITION BY city, month), 1) AS share,
        RANK() OVER (PARTITION BY city, month ORDER BY revenue DESC) AS rnk
    FROM product_revenue
)
SELECT
    city,
    month,
    product,
    revenue,
    share
FROM ranked_products
WHERE rnk <= 2
ORDER BY city ASC, month ASC, revenue DESC, product ASC;

WITH monthly_sales AS (
    SELECT 
        s.city,
        strftime('%Y-%m', sa.sold_on) AS month,
        sa.product,
        SUM(sa.amount) AS revenue
    FROM sales sa
    JOIN stores s ON sa.store_id = s.id
    WHERE sa.store_id IS NOT NULL 
      AND s.city IS NOT NULL 
      AND sa.product IS NOT NULL
    GROUP BY s.city, strftime('%Y-%m', sa.sold_on), sa.product
),
city_month_totals AS (
    SELECT 
        city,
        month,
        SUM(revenue) AS total_revenue
    FROM monthly_sales
    GROUP BY city, month
),
ranked_products AS (
    SELECT 
        m.city,
        m.month,
        m.product,
        m.revenue,
        ROUND(100.0 * m.revenue / c.total_revenue, 1) AS share,
        RANK() OVER (PARTITION BY m.city, m.month ORDER BY m.revenue DESC) AS rnk
    FROM monthly_sales m
    JOIN city_month_totals c ON m.city = c.city AND m.month = c.month
)
SELECT 
    city,
    month,
    product,
    revenue,
    share
FROM ranked_products
WHERE rnk <= 2
ORDER BY city ASC, month ASC, revenue DESC, product ASC;

WITH monthly AS (
    SELECT
        st.city                        AS city,
        substr(s.sold_on, 1, 7)        AS month,
        s.product                      AS product,
        SUM(s.amount)                  AS revenue
    FROM sales s
    JOIN stores st ON st.id = s.store_id
    WHERE s.store_id IS NOT NULL
      AND st.city    IS NOT NULL
      AND s.product  IS NOT NULL
    GROUP BY st.city, substr(s.sold_on, 1, 7), s.product
),
ranked AS (
    SELECT
        city,
        month,
        product,
        revenue,
        RANK() OVER (PARTITION BY city, month ORDER BY revenue DESC) AS rnk,
        SUM(revenue) OVER (PARTITION BY city, month)                 AS city_month_total
    FROM monthly
)
SELECT
    city,
    month,
    product,
    revenue,
    ROUND(100.0 * revenue / city_month_total, 1) AS share
FROM ranked
WHERE rnk <= 2
ORDER BY city ASC, month ASC, revenue DESC, product ASC;

WITH base AS (
  SELECT st.city,
         strftime('%Y-%m', s.sold_on) AS month,
         s.product,
         SUM(s.amount) AS revenue
  FROM sales s
  JOIN stores st ON st.id = s.store_id
  WHERE s.store_id IS NOT NULL
    AND st.city IS NOT NULL
    AND s.product IS NOT NULL
  GROUP BY st.city, strftime('%Y-%m', s.sold_on), s.product
),
city_month AS (
  SELECT city, month, SUM(revenue) AS total_rev
  FROM base
  GROUP BY city, month
),
ranked AS (
  SELECT city, month, product, revenue,
         RANK() OVER (PARTITION BY city, month ORDER BY revenue DESC) AS rk
  FROM base
)
SELECT r.city,
       r.month,
       r.product,
       r.revenue,
       ROUND(100.0 * r.revenue / cm.total_rev, 1) AS share
FROM ranked r
JOIN city_month cm ON cm.city = r.city AND cm.month = r.month
WHERE r.rk <= 2
ORDER BY r.city ASC, r.month ASC, r.revenue DESC, r.product ASC;

WITH product_revenue AS (
    SELECT
        st.city,
        strftime('%Y-%m', sa.sold_on) AS month,
        sa.product,
        SUM(sa.amount) AS revenue
    FROM sales AS sa
    JOIN stores AS st ON st.id = sa.store_id
    WHERE sa.store_id IS NOT NULL
      AND st.city IS NOT NULL
      AND sa.product IS NOT NULL
    GROUP BY st.city, strftime('%Y-%m', sa.sold_on), sa.product
),
ranked AS (
    SELECT
        city,
        month,
        product,
        revenue,
        100.0 * revenue
            / SUM(revenue) OVER (PARTITION BY city, month) AS share,
        RANK() OVER (
            PARTITION BY city, month
            ORDER BY revenue DESC
        ) AS revenue_rank
    FROM product_revenue
)
SELECT
    city,
    month,
    product,
    revenue,
    ROUND(share, 1) AS share
FROM ranked
WHERE revenue_rank <= 2
ORDER BY city ASC, month ASC, revenue DESC, product ASC;

WITH product_revenue AS (
    SELECT
        s.city,
        strftime('%Y-%m', sa.sold_on) AS month,
        sa.product,
        SUM(sa.amount) AS revenue
    FROM sales AS sa
    JOIN stores AS s ON s.id = sa.store_id
    WHERE sa.store_id IS NOT NULL
      AND s.city IS NOT NULL
      AND sa.product IS NOT NULL
    GROUP BY s.city, strftime('%Y-%m', sa.sold_on), sa.product
),
ranked AS (
    SELECT
        city,
        month,
        product,
        revenue,
        RANK() OVER (
            PARTITION BY city, month
            ORDER BY revenue DESC
        ) AS revenue_rank,
        SUM(revenue) OVER (
            PARTITION BY city, month
        ) AS total_revenue
    FROM product_revenue
)
SELECT
    city,
    month,
    product,
    revenue,
    ROUND(100.0 * revenue / total_revenue, 1) AS share
FROM ranked
WHERE revenue_rank <= 2
ORDER BY city ASC, month ASC, revenue DESC, product ASC;

WITH product_revenue AS (
  SELECT
    st.city,
    strftime('%Y-%m', sa.sold_on) AS month,
    sa.product,
    SUM(sa.amount) AS revenue
  FROM sales AS sa
  JOIN stores AS st ON st.id = sa.store_id
  WHERE sa.store_id IS NOT NULL
    AND st.city IS NOT NULL
    AND sa.product IS NOT NULL
  GROUP BY st.city, strftime('%Y-%m', sa.sold_on), sa.product
),
ranked AS (
  SELECT
    city,
    month,
    product,
    revenue,
    SUM(revenue) OVER (PARTITION BY city, month) AS total_revenue,
    RANK() OVER (
      PARTITION BY city, month
      ORDER BY revenue DESC
    ) AS revenue_rank
  FROM product_revenue
)
SELECT
  city,
  month,
  product,
  revenue,
  ROUND(100.0 * revenue / total_revenue, 1) AS share
FROM ranked
WHERE revenue_rank <= 2
ORDER BY city ASC, month ASC, revenue DESC, product ASC;

def elapsed_seconds(tz_name, start, end):
    from datetime import datetime
    from zoneinfo import ZoneInfo
    tz = ZoneInfo(tz_name)
    fmt = "%Y-%m-%d %H:%M:%S"
    start_dt = datetime.strptime(start, fmt).replace(tzinfo=tz, fold=0)
    end_dt = datetime.strptime(end, fmt).replace(tzinfo=tz, fold=0)
    return (end_dt - start_dt).total_seconds()

from datetime import datetime, timedelta
from zoneinfo import ZoneInfo

def elapsed_seconds(tz_name, start, end):
    tz = ZoneInfo(tz_name)
    fmt = "%Y-%m-%d %H:%M:%S"

    def to_aware(s):
        naive = datetime.strptime(s, fmt)
        # First try the pre-transition / earlier interpretation (fold=0).
        # This is the required resolution for both spring-forward gaps
        # and fall-back overlaps.
        try:
            return naive.replace(tzinfo=tz, fold=0)
        except Exception:
            # zoneinfo never raises on construction; the exception path is
            # kept only for future-proofing.  The real work is done below.
            pass
        # Explicit gap handling: walk backwards one second at a time until
        # we land on a valid wall time, then re-apply the original
        # wall-clock components under the offset that was in force then.
        # This implements "use the UTC offset immediately before the jump".
        probe = naive
        while True:
            try:
                # Attach tz with fold=0; if the instant is valid we are done.
                aware = probe.replace(tzinfo=tz, fold=0)
                # Verify it round-trips to the same wall time (i.e. was not
                # a gap).  If it does, the offset we obtained is the one
                # that existed just before the spring-forward.
                if aware.replace(tzinfo=None) == probe:
                    # Reconstruct the original wall time under that offset.
                    return naive.replace(tzinfo=aware.tzinfo, fold=0)
            except Exception:
                pass
            probe -= timedelta(seconds=1)

    start_aware = to_aware(start)
    end_aware = to_aware(end)
    return (end_aware - start_aware).total_seconds()

from zoneinfo import ZoneInfo, NonExistentTimeError
from datetime import datetime, timedelta, timezone

def elapsed_seconds(tz_name, start, end):
    """Return the real elapsed seconds between two local wall-clock times in the given IANA timezone."""
    # Parse the local wall-clock strings
    dt_start = datetime.strptime(start, "%Y-%m-%d %H:%M:%S")
    dt_end = datetime.strptime(end, "%Y-%m-%d %H:%M:%S")

    # Load the requested time zone
    tz = ZoneInfo(tz_name)

    def get_offset(naive_dt):
        """Return the UTC offset for a naive local datetime according to the rules.

        - Non-existent times (spring-forward) → use the offset immediately before the gap.
        - Ambiguous times (fall-back) → use the first occurrence (fold=0, default behaviour).
        """
        try:
            return tz.utcoffset(naive_dt)
        except NonExistentTimeError:
            # Step backwards in 1-minute increments until we hit a valid time.
            dt = naive_dt
            while True:
                dt -= timedelta(minutes=1)
                try:
                    return tz.utcoffset(dt)
                except NonExistentTimeError:
                    continue

    # Obtain UTC offsets for both local times
    offset_start = get_offset(dt_start)
    offset_end = get_offset(dt_end)

    # Convert to UTC-aware datetimes: local = UTC + offset  →  UTC = local - offset
    utc_start = (dt_start - offset_start).replace(tzinfo=timezone.utc)
    utc_end = (dt_end - offset_end).replace(tzinfo=timezone.utc)

    # Real elapsed seconds
    return (utc_end - utc_start).total_seconds()

from datetime import datetime
from zoneinfo import ZoneInfo


def elapsed_seconds(tz_name, start, end):
    tz = ZoneInfo(tz_name)
    fmt = "%Y-%m-%d %H:%M:%S"
    # fold=0 (the default) implements both required rules per PEP 495:
    # - nonexistent (spring-forward gap) times are interpreted with the
    #   pre-transition UTC offset, i.e. as if the clock hadn't jumped;
    # - ambiguous (fall-back) times resolve to the first, earlier occurrence.
    t0 = datetime.strptime(start, fmt).replace(tzinfo=tz, fold=0)
    t1 = datetime.strptime(end, fmt).replace(tzinfo=tz, fold=0)
    return (t1 - t0).total_seconds()

from datetime import datetime
from zoneinfo import ZoneInfo

def elapsed_seconds(tz_name, start, end):
    fmt = "%Y-%m-%d %H:%M:%S"
    tz = ZoneInfo(tz_name)
    dt_start = datetime.strptime(start, fmt).replace(tzinfo=tz, fold=0)
    dt_end = datetime.strptime(end, fmt).replace(tzinfo=tz, fold=0)
    return int(round(dt_end.timestamp() - dt_start.timestamp()))

def elapsed_seconds(tz_name, start, end):
    from datetime import datetime
    from zoneinfo import ZoneInfo
    zone = ZoneInfo(tz_name)
    fmt = "%Y-%m-%d %H:%M:%S"
    s = datetime.strptime(start, fmt).replace(tzinfo=zone)  # fold=0 by default
    e = datetime.strptime(end, fmt).replace(tzinfo=zone)    # fold=0 by default
    return e.timestamp() - s.timestamp()

from datetime import datetime, timedelta, timezone
from zoneinfo import ZoneInfo


def elapsed_seconds(tz_name: str, start: str, end: str):
    tz = ZoneInfo(tz_name)

    def to_utc(dt_str: str) -> datetime:
        dt_naive = datetime.strptime(dt_str, "%Y-%m-%d %H:%M:%S")
        dt0 = dt_naive.replace(tzinfo=tz, fold=0)

        # Valid local wall time (unambiguous or first occurrence of fall-back)
        if dt0.astimezone(tz).replace(tzinfo=None) == dt_naive:
            return dt0.astimezone(timezone.utc)

        # Spring-forward gap: use UTC offset immediately BEFORE the jump
        for h in range(1, 25):
            prev = dt_naive - timedelta(hours=h)
            cand = prev.replace(tzinfo=tz, fold=0)
            if cand.astimezone(tz).replace(tzinfo=None) == prev:
                off_before = cand.utcoffset()
                return dt_naive.replace(tzinfo=timezone(off_before)).astimezone(
                    timezone.utc
                )

    return (to_utc(end) - to_utc(start)).total_seconds()

from datetime import datetime
from zoneinfo import ZoneInfo


def elapsed_seconds(tz_name: str, start: str, end: str) -> float:
    tz = ZoneInfo(tz_name)

    def parse_local_time(dt_str: str) -> datetime:
        naive = datetime.strptime(dt_str, "%Y-%m-%d %H:%M:%S")
        try:
            return naive.replace(tzinfo=tz, fold=0)
        except Exception:
            pass

        try:
            return naive.replace(tzinfo=ZoneInfo("UTC")) - tz.utcoffset(
                naive.replace(tzinfo=ZoneInfo("UTC"))
            )
        except Exception:
            pass

        # Fallback for spring-forward gap using offset before the jump
        dt_utc_guess = naive.replace(tzinfo=ZoneInfo("UTC"))
        offset = None
        for delta_minutes in (-1, -2, -5, -10, -30, -60, -120):
            from datetime import timedelta

            test_utc = dt_utc_guess + timedelta(minutes=delta_minutes)
            off = tz.utcoffset(test_utc)
            if off is not None:
                offset = off
                break
        if offset is None:
            offset = tz.utcoffset(dt_utc_guess)

        return naive.replace(tzinfo=ZoneInfo("UTC")) - offset

    dt_start = parse_local_time(start)
    dt_end = parse_local_time(end)

    return (dt_end - dt_start).total_seconds()

from datetime import datetime, timezone
from zoneinfo import ZoneInfo


def elapsed_seconds(tz_name, start, end):
    """Real elapsed seconds between two local wall-clock readings in tz_name.

    Both readings are resolved with fold=0, which per PEP 495 always selects the
    UTC offset in effect *before* the nearby transition. That gives exactly the
    two required rules:
      * skipped (spring-forward) reading -> the pre-jump offset, as if the clock
        had never jumped;
      * repeated (fall-back) reading     -> the first, pre-fallback occurrence.

    Each reading is converted to UTC before subtracting: subtracting two aware
    datetimes that share a tzinfo would ignore the zone and yield the wall-clock
    difference instead of real elapsed time.
    """
    tz = ZoneInfo(tz_name)
    fmt = "%Y-%m-%d %H:%M:%S"

    def to_utc(reading):
        local = datetime.strptime(reading, fmt).replace(tzinfo=tz, fold=0)
        return local.astimezone(timezone.utc)

    return (to_utc(end) - to_utc(start)).total_seconds()

from datetime import datetime
from zoneinfo import ZoneInfo


def elapsed_seconds(tz_name, start, end):
    tz = ZoneInfo(tz_name)
    utc = ZoneInfo("UTC")
    fmt = "%Y-%m-%d %H:%M:%S"
    s = datetime.strptime(start, fmt).replace(tzinfo=tz, fold=0)
    e = datetime.strptime(end, fmt).replace(tzinfo=tz, fold=0)
    return (e.astimezone(utc) - s.astimezone(utc)).total_seconds()

def elapsed_seconds(tz_name, start, end):
    from datetime import datetime, timezone
    from zoneinfo import ZoneInfo

    fmt = "%Y-%m-%d %H:%M:%S"
    tz = ZoneInfo(tz_name)
    start_dt = datetime.strptime(start, fmt).replace(tzinfo=tz, fold=0)
    end_dt = datetime.strptime(end, fmt).replace(tzinfo=tz, fold=0)
    return (end_dt.astimezone(timezone.utc) -
            start_dt.astimezone(timezone.utc)).total_seconds()

def elapsed_seconds(tz_name, start, end):
    from datetime import datetime, timezone
    from zoneinfo import ZoneInfo

    zone = ZoneInfo(tz_name)
    fmt = "%Y-%m-%d %H:%M:%S"

    start_dt = datetime.strptime(start, fmt).replace(tzinfo=zone, fold=0)
    end_dt = datetime.strptime(end, fmt).replace(tzinfo=zone, fold=0)

    return (
        end_dt.astimezone(timezone.utc)
        - start_dt.astimezone(timezone.utc)
    ).total_seconds()

def elapsed_seconds(tz_name, start, end):
    from datetime import datetime, timezone
    from zoneinfo import ZoneInfo

    tz = ZoneInfo(tz_name)
    fmt = "%Y-%m-%d %H:%M:%S"

    def resolve(value):
        return datetime.strptime(value, fmt).replace(tzinfo=tz, fold=0)

    return int((resolve(end).astimezone(timezone.utc) -
                resolve(start).astimezone(timezone.utc)).total_seconds())

def split_bill(amounts, n):
    from decimal import Decimal

    if n <= 0:
        raise ValueError("n must be positive")

    total_scaled = 0
    max_scale = 0

    for amount in amounts:
        d = Decimal(amount.strip() if isinstance(amount, str) else amount)
        if not d.is_finite():
            raise ValueError("amounts must be finite decimal values")

        t = d.as_tuple()
        coeff = 0
        for digit in t.digits:
            coeff = coeff * 10 + digit
        if t.sign:
            coeff = -coeff

        exp = t.exponent
        if coeff == 0:
            value = 0
            scale = 0
        elif exp >= 0:
            value = coeff * (10 ** exp)
            scale = 0
        else:
            scale = -exp
            while scale > 0 and coeff % 10 == 0:
                coeff //= 10
                scale -= 1
            value = coeff

        if value == 0:
            continue

        if scale > max_scale:
            total_scaled *= 10 ** (scale - max_scale)
            max_scale = scale

        if scale < max_scale:
            total_scaled += value * (10 ** (max_scale - scale))
        else:
            total_scaled += value

    if total_scaled == 0:
        total_cents = 0
    else:
        numerator = total_scaled * 100
        denominator = 10 ** max_scale

        sign = -1 if numerator < 0 else 1
        q, r = divmod(abs(numerator), denominator)
        twice_r = 2 * r
        if twice_r > denominator or (twice_r == denominator and (q % 2 == 1)):
            q += 1
        total_cents = sign * q

    base, leftover = divmod(total_cents, n)

    parts = []
    for i in range(n):
        cents = base + (1 if i < leftover else 0)
        sign_str = "-" if cents < 0 else ""
        cents_abs = abs(cents)
        parts.append(f"{sign_str}{cents_abs // 100}.{cents_abs % 100:02d}")

    return parts

from decimal import Decimal, ROUND_HALF_EVEN

def split_bill(amounts, n):
    total = sum(Decimal(a) for a in amounts)
    rounded = total.quantize(Decimal("0.01"), rounding=ROUND_HALF_EVEN)
    cents = int(rounded * 100)
    base, rem = divmod(cents, n)
    return [f"{(base + (i < rem)) // 100}.{(base + (i < rem)) % 100:02d}" for i in range(n)]

from decimal import Decimal, ROUND_HALF_EVEN

def split_bill(amounts, n):
    """
    Returns a list of n strings representing equal shares of the total bill,
    rounded to the nearest cent using banker's rounding, with any leftover
    cents distributed one extra cent at a time to the first parts.
    """
    # Compute exact total using Decimal
    total = Decimal('0')
    for amt in amounts:
        total += Decimal(amt)

    # Round total to the nearest cent with ROUND_HALF_EVEN
    rounded = total.quantize(Decimal('0.01'), rounding=ROUND_HALF_EVEN)

    # Total cents as integer (rounded already has exactly two decimal places)
    total_cents = int(rounded * 100)

    base_share, remainder = divmod(total_cents, n)

    result = []
    for i in range(n):
        cents = base_share + (1 if i < remainder else 0)
        dollars = cents // 100
        cents_part = cents % 100
        # Format with exactly two decimal places, no thousands separator
        result.append(f"{dollars}.{cents_part:02d}")

    return result

from decimal import Decimal, ROUND_HALF_EVEN

def split_bill(amounts, n):
    total = sum((Decimal(a) for a in amounts), Decimal("0"))
    rounded = total.quantize(Decimal("0.01"), rounding=ROUND_HALF_EVEN)
    total_cents = int(rounded * 100)
    base, extra = divmod(total_cents, n)
    return [f"{(base + (1 if i < extra else 0)) // 100}.{(base + (1 if i < extra else 0)) % 100:02d}" for i in range(n)]

from decimal import Decimal, ROUND_HALF_EVEN

def split_bill(amounts, n):
    total = sum((Decimal(a) for a in amounts), Decimal("0"))
    total_cents = int(total.quantize(Decimal("0.01"), rounding=ROUND_HALF_EVEN) * 100)

    base, remainder = divmod(total_cents, n)

    parts = []
    for i in range(n):
        cents = base + (1 if i < remainder else 0)
        parts.append(str((Decimal(cents) / 100).quantize(Decimal("0.01"))))

    return parts

from decimal import Decimal, ROUND_HALF_EVEN


def split_bill(amounts, n):
    total = sum((Decimal(a) for a in amounts), Decimal(0))
    rounded = total.quantize(Decimal("0.01"), rounding=ROUND_HALF_EVEN)
    total_cents = int(rounded * 100)
    base, rem = divmod(total_cents, n)
    parts = []
    for i in range(n):
        cents = base + 1 if i < rem else base
        parts.append(f"{cents // 100}.{cents % 100:02d}")
    return parts

from decimal import Decimal, ROUND_HALF_EVEN


def split_bill(amounts, n):
    total = sum((Decimal(a) for a in amounts), Decimal("0"))
    rounded_total = total.quantize(Decimal("0.01"), rounding=ROUND_HALF_EVEN)
    total_cents = int(rounded_total * 100)

    base_cents = total_cents // n
    remainder = total_cents % n

    parts = []
    for i in range(n):
        cents = base_cents + (1 if i < remainder else 0)
        parts.append(f"{cents // 100}.{cents % 100:02d}")

    return parts

from decimal import Decimal, ROUND_HALF_EVEN


def split_bill(amounts, n):
    total = sum(Decimal(a) for a in amounts)
    cents = int(
        (total * 100).quantize(Decimal("1"), rounding=ROUND_HALF_EVEN)
    )

    base = cents // n
    remainder = cents % n

    parts = []
    for i in range(n):
        share = base + (1 if i < remainder else 0)
        parts.append(f"{share / 100:.2f}")

    return parts

from decimal import Decimal, ROUND_HALF_EVEN


def split_bill(amounts, n):
    """Split the exact, banker's-rounded total of `amounts` into `n` money strings.

    Every part has exactly two decimal places, and the parts sum exactly to the
    rounded total: each gets `total_cents // n`, and the first `total_cents % n`
    parts get one extra cent.
    """
    if n <= 0:
        raise ValueError("n must be a positive integer")

    total = sum((Decimal(a) for a in amounts), Decimal(0))
    rounded = total.quantize(Decimal("0.01"), rounding=ROUND_HALF_EVEN)

    total_cents = int(rounded.scaleb(2))
    base, extra = divmod(total_cents, n)

    parts = []
    for i in range(n):
        cents = base + 1 if i < extra else base
        parts.append(str(Decimal(cents).scaleb(-2).quantize(Decimal("0.01"))))
    return parts

from decimal import Decimal, ROUND_HALF_EVEN


def split_bill(amounts, n):
    total = Decimal("0")
    for amount in amounts:
        total += Decimal(amount)
    rounded = total.quantize(Decimal("0.01"), rounding=ROUND_HALF_EVEN)
    total_cents = int(rounded * 100)
    base, leftover = divmod(total_cents, n)
    parts = []
    for i in range(n):
        cents = base + (1 if i < leftover else 0)
        parts.append(f"{cents // 100}.{cents % 100:02d}")
    return parts

def split_bill(amounts, n):
    from decimal import Decimal, ROUND_HALF_EVEN

    total = sum((Decimal(amount) for amount in amounts), Decimal(0))
    rounded_total = total.quantize(Decimal("0.01"), rounding=ROUND_HALF_EVEN)
    total_cents = int(rounded_total * 100)
    base_cents, extra = divmod(total_cents, n)

    return [
        f"{(base_cents + (i < extra)) // 100}.{(base_cents + (i < extra)) % 100:02d}"
        for i in range(n)
    ]

def split_bill(amounts, n):
    from decimal import Decimal, ROUND_HALF_EVEN, localcontext

    values = [Decimal(value) for value in amounts]
    max_integer_digits = max(
        (value.adjusted() + 1 if value else 1) for value in values
    ) if values else 1
    max_fractional_digits = max(
        max(-value.as_tuple().exponent, 0) for value in values
    ) if values else 0

    precision = (
        max_integer_digits
        + max_fractional_digits
        + len(str(max(len(values), 1)))
        + 2
    )

    with localcontext() as context:
        context.prec = precision
        total = sum(values, Decimal("0"))
        rounded = total.quantize(Decimal("0.01"), rounding=ROUND_HALF_EVEN)

    total_cents = int("".join(map(str, rounded.as_tuple().digits)) or "0")
    base, extra = divmod(total_cents, n)

    return [
        f"{(base + (i < extra)) // 100}.{(base + (i < extra)) % 100:02d}"
        for i in range(n)
    ]

def split_bill(amounts, n):
    from decimal import Decimal, ROUND_HALF_EVEN

    total = sum((Decimal(amount) for amount in amounts), Decimal("0"))
    total_cents = int(
        total.quantize(Decimal("0.01"), rounding=ROUND_HALF_EVEN) * 100
    )
    base, remainder = divmod(total_cents, n)

    return [
        f"{(base + (i < remainder)) // 100}.{(base + (i < remainder)) % 100:02d}"
        for i in range(n)
    ]

def truncate_graphemes(s, n):
    import unicodedata
    category = unicodedata.category

    if n == 0:
        return "..." if s else ""

    zwj = "‍"
    i = 0
    length = len(s)
    clusters = 0

    while i < length:
        first = s[i]
        i += 1
        force_next = first == zwj

        while i < length:
            ch = s[i]

            if ch == zwj:
                i += 1
                force_next = True
            elif category(ch) == "Mn":
                i += 1
                if force_next:
                    force_next = False
            elif force_next:
                i += 1
                force_next = False
            else:
                break

        clusters += 1

        if clusters == n:
            if i < length:
                return s[:i] + "..."
            return s

    return s

def truncate_graphemes(s, n):
    import unicodedata
    length = len(s)
    i = 0
    cluster_count = 0
    while i < length and cluster_count < n:
        cluster_count += 1
        i += 1
        while i < length and unicodedata.category(s[i]) == 'Mn':
            i += 1
        while i < length and s[i] == '‍':
            i += 1
            if i < length:
                i += 1
                while i < length and unicodedata.category(s[i]) == 'Mn':
                    i += 1
    if i >= length:
        return s
    return s[:i] + "..."

import unicodedata

def truncate_graphemes(s, n):
    clusters = []
    current = None          # current cluster as a list of characters
    zwj_join = False        # next code point is forced into current cluster

    for ch in s:
        if zwj_join:
            # We are inside a ZWJ-forced join
            if current is None:
                current = []
            current.append(ch)
            if ch != '‍':
                zwj_join = False
            continue

        cat = unicodedata.category(ch)
        if cat == 'Mn':                     # combining mark
            if current is not None:
                current.append(ch)
            else:
                # Leading combining mark forms its own cluster
                current = [ch]
        elif ch == '‍':                # ZERO WIDTH JOINER
            if current is None:
                current = [ch]
            else:
                current.append(ch)
            zwj_join = True
        else:                               # any other code point starts a new cluster
            if current is not None:
                clusters.append(''.join(current))
            current = [ch]
            zwj_join = False

    if current is not None:
        clusters.append(''.join(current))

    if len(clusters) <= n:
        return s
    else:
        return ''.join(clusters[:n]) + '...'

import unicodedata

def truncate_graphemes(s, n):
    clusters = []
    pending = False  # a ZWJ forces the next code point into the current cluster
    for ch in s:
        if not clusters:
            clusters.append(ch)
            pending = (ch == '‍')
        elif ch == '‍':
            clusters[-1] += ch
            pending = True
        elif unicodedata.category(ch) == 'Mn':
            clusters[-1] += ch
            pending = False
        elif pending:
            clusters[-1] += ch
            pending = False
        else:
            clusters.append(ch)
    if len(clusters) <= n:
        return s
    return ''.join(clusters[:n]) + '...'

import unicodedata

def truncate_graphemes(s, n):
    ZWJ = '‍'
    clusters = []
    pending_join = False

    for cp in s:
        if unicodedata.category(cp) == 'Mn':
            if clusters:
                clusters[-1].append(cp)
            else:
                clusters.append([cp])
            continue

        if cp == ZWJ:
            if clusters:
                clusters[-1].append(cp)
            else:
                clusters.append([cp])
            pending_join = True
            continue

        if pending_join and clusters:
            clusters[-1].append(cp)
            pending_join = False
        else:
            clusters.append([cp])

    if len(clusters) <= n:
        return s

    result = ''.join(''.join(cluster) for cluster in clusters[:n])
    return result + "..."

import unicodedata

def truncate_graphemes(s, n):
    ZWJ = '‍'
    clusters = []
    force = False  # next code point must join the current cluster
    for cp in s:
        is_zwj = cp == ZWJ
        is_mn = unicodedata.category(cp) == 'Mn'
        if not clusters:
            clusters.append(cp)
            force = is_zwj
        elif force:
            clusters[-1] += cp
            force = is_zwj  # re-arm only on chained ZWJ
        elif is_zwj:
            clusters[-1] += cp
            force = True
        elif is_mn:
            clusters[-1] += cp
            force = False
        else:
            clusters.append(cp)
            force = False
    if len(clusters) <= n:
        return s
    return ''.join(clusters[:n]) + '...'

import unicodedata


def truncate_graphemes(s, n):
    clusters = []
    zwj_pending = False

    for cp in s:
        if not clusters:
            clusters.append(cp)
            zwj_pending = cp == "\u200d"
        elif cp == "\u200d":
            clusters[-1] += cp
            zwj_pending = True
        elif unicodedata.category(cp) == "Mn":
            clusters[-1] += cp
        else:
            if zwj_pending:
                clusters[-1] += cp
                zwj_pending = False
            else:
                clusters.append(cp)

    if len(clusters) <= n:
        return s
    return "".join(clusters[:n]) + "..."

import unicodedata

def truncate_graphemes(s, n):
    if not s:
        return s

    clusters = []
    current_cluster = []
    join_next = False

    for cp in s:
        is_mn = (unicodedata.category(cp) == "Mn")
        is_zwj = (cp == "\u200D")

        if not current_cluster:
            # First code point in a cluster
            current_cluster.append(cp)
            join_next = is_zwj
        else:
            if join_next:
                # ZWJ forces this code point (and its following Mn) into the current cluster
                current_cluster.append(cp)
                join_next = is_zwj
            elif is_mn:
                # Combining mark always attaches to the current cluster
                current_cluster.append(cp)
            else:
                # Normal code point starts a new cluster
                clusters.append("".join(current_cluster))
                current_cluster = [cp]
                join_next = is_zwj

    if current_cluster:
        clusters.append("".join(current_cluster))

    if len(clusters) <= n:
        return s
    else:
        return "".join(clusters[:n]) + "..."

def truncate_graphemes(s, n):
    """Truncate `s` to at most `n` user-perceived characters, appending "..." if cut."""
    import unicodedata

    ZWJ = "\u200d"
    clusters = []
    join_next = False  # a ZWJ is pending: the next code point must not start a cluster

    for ch in s:
        if ch == ZWJ:
            # Attaches to the current cluster and pulls the following code point in too.
            if clusters:
                clusters[-1] += ch
            else:
                clusters.append(ch)
            join_next = True
        elif unicodedata.category(ch) == "Mn":
            # A combining mark always sticks to whatever it follows.
            if clusters:
                clusters[-1] += ch
            else:
                clusters.append(ch)
            join_next = False
        else:
            if join_next and clusters:
                clusters[-1] += ch
            else:
                clusters.append(ch)
            join_next = False

    if len(clusters) <= n:
        return s
    return "".join(clusters[:n]) + "..."

import unicodedata

def truncate_graphemes(s, n):
    clusters = []
    cur = ""
    forced = False
    for c in s:
        if unicodedata.category(c) == "Mn":
            cur += c
            forced = False
        elif c == "\u200d":
            cur += c
            forced = True
        else:
            if cur and not forced:
                clusters.append(cur)
                cur = c
            else:
                cur += c
            forced = False
    if cur:
        clusters.append(cur)
    if len(clusters) <= n:
        return s
    return "".join(clusters[:n]) + "..."

def truncate_graphemes(s, n):
    import unicodedata

    clusters = 0
    force_next = False

    for i, char in enumerate(s):
        if i == 0:
            starts_cluster = True
        elif unicodedata.category(char) == "Mn":
            starts_cluster = False
        elif char == "\u200d":
            starts_cluster = False
        elif force_next:
            starts_cluster = False
        else:
            starts_cluster = True

        if starts_cluster:
            clusters += 1
            if clusters > n:
                return s[:i] + "..."

        if char == "\u200d":
            force_next = True
        elif force_next and unicodedata.category(char) != "Mn":
            force_next = False

    return s

def truncate_graphemes(s, n):
    import unicodedata

    clusters = []
    join_next = False

    for char in s:
        category = unicodedata.category(char)

        if category == "Mn":
            if clusters:
                clusters[-1] += char
            else:
                clusters.append(char)
            join_next = False
        elif char == "\u200d":
            if clusters:
                clusters[-1] += char
            else:
                clusters.append(char)
            join_next = True
        elif join_next:
            clusters[-1] += char
            join_next = False
        else:
            clusters.append(char)

    if len(clusters) <= n:
        return s
    return "".join(clusters[:n]) + "..."

def truncate_graphemes(s, n):
    import unicodedata

    clusters = []
    current = ""
    join_next = False

    for char in s:
        is_mark = unicodedata.category(char) == "Mn"

        if not current:
            current = char
        elif is_mark or join_next or char == "\u200d":
            current += char
        else:
            clusters.append(current)
            current = char

        join_next = char == "\u200d"

    if current:
        clusters.append(current)

    return s if len(clusters) <= n else "".join(clusters[:n]) + "..."

SELECT
  c.name,
  (SELECT COUNT(*) FROM orders o WHERE o.customer_id = c.id) AS total_orders,
  (SELECT COUNT(o.amount) FROM orders o WHERE o.customer_id = c.id) AS priced_orders,
  COALESCE((SELECT SUM(o.amount) FROM orders o WHERE o.customer_id = c.id), 0) AS total_revenue,
  (SELECT COUNT(*) FROM notes n WHERE n.customer_id = c.id) AS note_count
FROM customers c
WHERE NOT EXISTS (
  SELECT 1 FROM flagged f WHERE f.customer_id = c.id
)
ORDER BY c.name ASC;

SELECT
    c.name,
    COALESCE(o.total_orders, 0) AS total_orders,
    COALESCE(o.priced.priced_orders, 0) AS priced_orders,
    COALESCE(o.total_revenue, 0) AS total_revenue,
    COALESCE(n.note_count, 0) AS note_count
FROM customers c
LEFT JOIN (
    SELECT
        customer_id,
        COUNT(*) AS total_orders,
        COUNT(amount) AS priced_orders,
        COALESCE(SUM(amount), 0) AS total_revenue
    FROM orders
    GROUP BY customer_id
) o ON o.customer_id = c.id
LEFT JOIN (
    SELECT
        customer_id,
        COUNT(*) AS note_count
    FROM notes
    GROUP BY customer_id
) n ON n.customer_id = c.id
WHERE c.id NOT IN (
    SELECT customer_id
    FROM flagged
    WHERE customer_id IS NOT NULL
)
ORDER BY c.name ASC;

SELECT
    c.name,
    COALESCE(o.total_orders, 0) AS total_orders,
    COALESCE(o.priced_orders, 0) AS priced_orders,
    COALESCE(o.total_revenue, 0) AS total_revenue,
    COALESCE(n.note_count, 0) AS note_count
FROM customers c
LEFT JOIN (
    SELECT
        customer_id,
        COUNT(*) AS total_orders,
        COUNT(amount) AS priced_orders,
        SUM(amount) AS total_revenue
    FROM orders
    GROUP BY customer_id
) o ON c.id = o.customer_id
LEFT JOIN (
    SELECT
        customer_id,
        COUNT(*) AS note_count
    FROM notes
    GROUP BY customer_id
) n ON c.id = n.customer_id
WHERE c.id NOT IN (
    SELECT customer_id
    FROM flagged
    WHERE customer_id IS NOT NULL
)
ORDER BY c.name ASC;

SELECT c.name,
       COALESCE(o.total_orders, 0)  AS total_orders,
       COALESCE(o.priced_orders, 0) AS priced_orders,
       COALESCE(o.total_revenue, 0) AS total_revenue,
       COALESCE(n.note_count, 0)    AS note_count
FROM customers c
LEFT JOIN (
    SELECT customer_id,
           COUNT(*)                 AS total_orders,
           COUNT(amount)            AS priced_orders,
           COALESCE(SUM(amount), 0) AS total_revenue
    FROM orders
    GROUP BY customer_id
) o ON o.customer_id = c.id
LEFT JOIN (
    SELECT customer_id, COUNT(*) AS note_count
    FROM notes
    GROUP BY customer_id
) n ON n.customer_id = c.id
WHERE NOT EXISTS (
    SELECT 1 FROM flagged f WHERE f.customer_id = c.id
)
ORDER BY c.name ASC;

SELECT
  c.name,
  COALESCE(o.total_orders, 0)   AS total_orders,
  COALESCE(o.priced_orders, 0)  AS priced_orders,
  COALESCE(o.total_revenue, 0)  AS total_revenue,
  COALESCE(n.note_count, 0)     AS note_count
FROM customers c
LEFT JOIN (
  SELECT customer_id,
         COUNT(*)                  AS total_orders,
         COUNT(amount)             AS priced_orders,
         SUM(COALESCE(amount, 0))  AS total_revenue
  FROM orders
  GROUP BY customer_id
) o ON o.customer_id = c.id
LEFT JOIN (
  SELECT customer_id, COUNT(*) AS note_count
  FROM notes
  GROUP BY customer_id
) n ON n.customer_id = c.id
WHERE c.id NOT IN (SELECT customer_id FROM flagged WHERE customer_id IS NOT NULL)
ORDER BY c.name ASC;

SELECT
  c.name,
  COALESCE(o.total_orders, 0)  AS total_orders,
  COALESCE(o.priced_orders, 0) AS priced_orders,
  COALESCE(o.total_revenue, 0) AS total_revenue,
  COALESCE(n.note_count, 0)    AS note_count
FROM customers c
LEFT JOIN (
  SELECT customer_id,
         COUNT(*)                AS total_orders,
         COUNT(amount)           AS priced_orders,
         COALESCE(SUM(amount), 0) AS total_revenue
  FROM orders
  GROUP BY customer_id
) o ON o.customer_id = c.id
LEFT JOIN (
  SELECT customer_id, COUNT(*) AS note_count
  FROM notes
  GROUP BY customer_id
) n ON n.customer_id = c.id
WHERE c.id NOT IN (SELECT customer_id FROM flagged WHERE customer_id IS NOT NULL)
ORDER BY c.name ASC;

WITH order_stats AS (
    SELECT
        customer_id,
        COUNT(*) AS total_orders,
        COUNT(amount) AS priced_orders,
        COALESCE(SUM(amount), 0) AS total_revenue
    FROM orders
    GROUP BY customer_id
),
note_stats AS (
    SELECT
        customer_id,
        COUNT(*) AS note_count
    FROM notes
    GROUP BY customer_id
)
SELECT
    c.name,
    COALESCE(o.total_orders, 0) AS total_orders,
    COALESCE(o.priced_orders, 0) AS priced_orders,
    COALESCE(o.total_revenue, 0) AS total_revenue,
    COALESCE(n.note_count, 0) AS note_count
FROM customers c
LEFT JOIN order_stats o ON c.id = o.customer_id
LEFT JOIN note_stats n ON c.id = n.customer_id
WHERE NOT EXISTS (
    SELECT 1 
    FROM flagged f 
    WHERE f.customer_id = c.id
)
ORDER BY c.name ASC;

SELECT 
    c.name,
    COALESCE(o_stats.total_orders, 0) AS total_orders,
    COALESCE(o_stats.priced_orders, 0) AS priced_orders,
    COALESCE(o_stats.total_revenue, 0.0) AS total_revenue,
    COALESCE(n_stats.note_count, 0) AS note_count
FROM customers c
LEFT JOIN (
    SELECT 
        customer_id,
        COUNT(*) AS total_orders,
        COUNT(amount) AS priced_orders,
        SUM(amount) AS total_revenue
    FROM orders
    GROUP BY customer_id
) o_stats ON c.id = o_stats.customer_id
LEFT JOIN (
    SELECT 
        customer_id,
        COUNT(*) AS note_count
    FROM notes
    GROUP BY customer_id
) n_stats ON c.id = n_stats.customer_id
WHERE c.id NOT IN (SELECT customer_id FROM flagged WHERE customer_id IS NOT NULL)
ORDER BY c.name ASC;

SELECT
    c.name                                        AS name,
    COALESCE(o.total_orders,   0)                 AS total_orders,
    COALESCE(o.priced_orders,  0)                 AS priced_orders,
    COALESCE(o.total_revenue,  0)                 AS total_revenue,
    COALESCE(n.note_count,     0)                 AS note_count
FROM customers c
LEFT JOIN (
    SELECT customer_id,
           COUNT(*)              AS total_orders,
           COUNT(amount)         AS priced_orders,
           COALESCE(SUM(amount), 0) AS total_revenue
    FROM orders
    GROUP BY customer_id
) o ON o.customer_id = c.id
LEFT JOIN (
    SELECT customer_id,
           COUNT(*) AS note_count
    FROM notes
    GROUP BY customer_id
) n ON n.customer_id = c.id
WHERE NOT EXISTS (
    SELECT 1 FROM flagged f
    WHERE f.customer_id = c.id
)
ORDER BY c.name ASC;

SELECT
  c.name,
  (SELECT COUNT(*) FROM orders o WHERE o.customer_id = c.id) AS total_orders,
  (SELECT COUNT(*) FROM orders o WHERE o.customer_id = c.id AND o.amount IS NOT NULL) AS priced_orders,
  COALESCE((SELECT SUM(o.amount) FROM orders o WHERE o.customer_id = c.id), 0) AS total_revenue,
  (SELECT COUNT(*) FROM notes n WHERE n.customer_id = c.id) AS note_count
FROM customers c
WHERE NOT EXISTS (SELECT 1 FROM flagged f WHERE f.customer_id = c.id)
ORDER BY c.name;

SELECT
    c.name,
    COALESCE(o.total_orders, 0) AS total_orders,
    COALESCE(o.priced_orders, 0) AS priced_orders,
    COALESCE(o.total_revenue, 0) AS total_revenue,
    COALESCE(n.note_count, 0) AS note_count
FROM customers AS c
LEFT JOIN (
    SELECT
        customer_id,
        COUNT(*) AS total_orders,
        COUNT(amount) AS priced_orders,
        COALESCE(SUM(amount), 0) AS total_revenue
    FROM orders
    GROUP BY customer_id
) AS o ON o.customer_id = c.id
LEFT JOIN (
    SELECT
        customer_id,
        COUNT(*) AS note_count
    FROM notes
    GROUP BY customer_id
) AS n ON n.customer_id = c.id
WHERE NOT EXISTS (
    SELECT 1
    FROM flagged AS f
    WHERE f.customer_id = c.id
)
ORDER BY c.name ASC;

SELECT
    c.name,
    COALESCE(o.total_orders, 0) AS total_orders,
    COALESCE(o.priced_orders, 0) AS priced_orders,
    COALESCE(o.total_revenue, 0) AS total_revenue,
    COALESCE(n.note_count, 0) AS note_count
FROM customers AS c
LEFT JOIN (
    SELECT
        customer_id,
        COUNT(*) AS total_orders,
        COUNT(amount) AS priced_orders,
        SUM(amount) AS total_revenue
    FROM orders
    GROUP BY customer_id
) AS o ON o.customer_id = c.id
LEFT JOIN (
    SELECT
        customer_id,
        COUNT(*) AS note_count
    FROM notes
    GROUP BY customer_id
) AS n ON n.customer_id = c.id
WHERE NOT EXISTS (
    SELECT 1
    FROM flagged AS f
    WHERE f.customer_id = c.id
)
ORDER BY c.name ASC;

SELECT
  c.name,
  COALESCE(o.total_orders, 0) AS total_orders,
  COALESCE(o.priced_orders, 0) AS priced_orders,
  COALESCE(o.total_revenue, 0) AS total_revenue,
  COALESCE(n.note_count, 0) AS note_count
FROM customers AS c
LEFT JOIN (
  SELECT
    customer_id,
    COUNT(*) AS total_orders,
    COUNT(amount) AS priced_orders,
    COALESCE(SUM(amount), 0) AS total_revenue
  FROM orders
  GROUP BY customer_id
) AS o ON o.customer_id = c.id
LEFT JOIN (
  SELECT customer_id, COUNT(*) AS note_count
  FROM notes
  GROUP BY customer_id
) AS n ON n.customer_id = c.id
WHERE NOT EXISTS (
  SELECT 1
  FROM flagged AS f
  WHERE f.customer_id = c.id
)
ORDER BY c.name ASC;

def find_all_occurrences(text, pattern):
    n = len(text)
    m = len(pattern)
    if m == 0 or m > n:
        return []
    lps = [0] * m
    length = 0
    i = 1
    while i < m:
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        elif length != 0:
            length = lps[length - 1]
        else:
            lps[i] = 0
            i += 1

    result = []
    i = 0
    j = 0

    while i < n:
        if text[i] == pattern[j]:
            i += 1
            j += 1

            if j == m:
                result.append(i - m)
                j = lps[j - 1]
        elif j != 0:
            j = lps[j - 1]
        else:
            i += 1

    return result

def find_all_occurrences(text, pattern):
    n, m = len(text), len(pattern)
    if m > n:
        return []
    lps = [0] * m
    length = 0
    i = 1
    while i < m:
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        elif length != 0:
            length = lps[length - 1]
        else:
            lps[i] = 0
            i += 1
    res = []
    i = j = 0
    while i < n:
        if text[i] == pattern[j]:
            i += 1
            j += 1
            if j == m:
                res.append(i - m)
                j = lps[j - 1]
        elif j != 0:
            j = lps[j - 1]
        else:
            i += 1
    return res

def find_all_occurrences(text, pattern):
    n = len(text)
    m = len(pattern)
    if m > n:
        return []

    # Build LPS (Longest Prefix Suffix) array for pattern
    lps = [0] * m
    length = 0
    i = 1
    while i < m:
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1

    # Search using KMP
    result = []
    j = 0  # index for pattern
    for i in range(n):
        while j > 0 and text[i] != pattern[j]:
            j = lps[j - 1]
        if text[i] == pattern[j]:
            j += 1
        if j == m:
            result.append(i - m + 1)
            j = lps[j - 1]  # continue searching for overlapping matches

    return result

def find_all_occurrences(text, pattern):
    n, m = len(text), len(pattern)
    if m > n:
        return []
    # Build KMP failure table
    fail = [0] * m
    k = 0
    for i in range(1, m):
        while k > 0 and pattern[i] != pattern[k]:
            k = fail[k - 1]
        if pattern[i] == pattern[k]:
            k += 1
        fail[i] = k
    # Scan text
    result = []
    k = 0
    for i in range(n):
        while k > 0 and text[i] != pattern[k]:
            k = fail[k - 1]
        if text[i] == pattern[k]:
            k += 1
        if k == m:
            result.append(i - m + 1)
            k = fail[k - 1]
    return result

def find_all_occurrences(text, pattern):
    n = len(text)
    m = len(pattern)
    if m == 0 or m > n:
        return []

    # Build KMP failure function (longest proper prefix which is also suffix)
    lps = [0] * m
    length = 0
    i = 1
    while i < m:
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        elif length != 0:
            length = lps[length - 1]
        else:
            lps[i] = 0
            i += 1

    result = []
    i = 0  # index for text
    j = 0  # index for pattern
    while i < n:
        if text[i] == pattern[j]:
            i += 1
            j += 1
            if j == m:
                result.append(i - j)
                j = lps[j - 1]
        elif j != 0:
            j = lps[j - 1]
        else:
            i += 1

    return result

def find_all_occurrences(text, pattern):
    n, m = len(text), len(pattern)
    if m > n:
        return []

    # Build longest-proper-prefix-suffix (failure) table for pattern.
    lps = [0] * m
    k = 0
    for i in range(1, m):
        while k > 0 and pattern[i] != pattern[k]:
            k = lps[k - 1]
        if pattern[i] == pattern[k]:
            k += 1
        lps[i] = k

    # KMP scan over text.
    result = []
    k = 0
    for i in range(n):
        while k > 0 and text[i] != pattern[k]:
            k = lps[k - 1]
        if text[i] == pattern[k]:
            k += 1
        if k == m:
            result.append(i - m + 1)
            k = lps[k - 1]  # allow overlapping matches
    return result

def find_all_occurrences(text, pattern):
    n = len(text)
    m = len(pattern)

    if m > n or m == 0:
        return []

    # Compute Knuth-Morris-Pratt (KMP) prefix function (LPS table)
    pi = [0] * m
    j = 0
    for i in range(1, m):
        while j > 0 and pattern[i] != pattern[j]:
            j = pi[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
        pi[i] = j

    result = []
    j = 0  # Number of matched characters in pattern
    for i in range(n):
        while j > 0 and text[i] != pattern[j]:
            j = pi[j - 1]
        if text[i] == pattern[j]:
            j += 1
        if j == m:
            result.append(i - m + 1)
            j = pi[j - 1]

    return result

def find_all_occurrences(text, pattern):
    n = len(text)
    m = len(pattern)
    if m > n:
        return []

    # Compute the LPS (Longest Proper Prefix which is also Suffix) array for KMP
    lps = [0] * m
    length = 0
    i = 1
    while i < m:
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1

    result = []
    i = 0  # index for text
    j = 0  # index for pattern
    while i < n:
        if pattern[j] == text[i]:
            i += 1
            j += 1

        if j == m:
            result.append(i - j)
            # Instead of resetting j to 0, use lps to allow overlapping matches
            j = lps[j - 1]
        elif i < n and pattern[j] != text[i]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1

    return result

def find_all_occurrences(text, pattern):
    n, m = len(text), len(pattern)
    if m > n:
        return []

    # KMP failure function: fail[i] is the length of the longest proper prefix
    # of pattern[:i + 1] that is also a suffix of it.
    fail = [0] * m
    k = 0
    for i in range(1, m):
        while k and pattern[i] != pattern[k]:
            k = fail[k - 1]
        if pattern[i] == pattern[k]:
            k += 1
        fail[i] = k

    result = []
    k = 0  # number of pattern characters matched so far
    for i in range(n):
        while k and text[i] != pattern[k]:
            k = fail[k - 1]
        if text[i] == pattern[k]:
            k += 1
        if k == m:
            result.append(i - m + 1)
            k = fail[k - 1]  # fall back, allowing overlapping matches
    return result

def find_all_occurrences(text, pattern):
    n, m = len(text), len(pattern)
    if m > n:
        return []
    lps = [0] * m
    j = 0
    for i in range(1, m):
        while j > 0 and pattern[i] != pattern[j]:
            j = lps[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
            lps[i] = j
    result = []
    j = 0
    for i in range(n):
        while j > 0 and text[i] != pattern[j]:
            j = lps[j - 1]
        if text[i] == pattern[j]:
            j += 1
            if j == m:
                result.append(i - m + 1)
                j = lps[j - 1]
    return result

def find_all_occurrences(text, pattern):
    prefix = [0] * len(pattern)
    matched = 0

    for i in range(1, len(pattern)):
        while matched and pattern[i] != pattern[matched]:
            matched = prefix[matched - 1]
        if pattern[i] == pattern[matched]:
            matched += 1
        prefix[i] = matched

    occurrences = []
    matched = 0

    for i, char in enumerate(text):
        while matched and char != pattern[matched]:
            matched = prefix[matched - 1]
        if char == pattern[matched]:
            matched += 1
        if matched == len(pattern):
            occurrences.append(i - len(pattern) + 1)
            matched = prefix[matched - 1]

    return occurrences

def find_all_occurrences(text, pattern):
    prefix = [0] * len(pattern)
    length = 0

    for i in range(1, len(pattern)):
        while length and pattern[i] != pattern[length]:
            length = prefix[length - 1]
        if pattern[i] == pattern[length]:
            length += 1
        prefix[i] = length

    occurrences = []
    matched = 0

    for i, char in enumerate(text):
        while matched and char != pattern[matched]:
            matched = prefix[matched - 1]
        if char == pattern[matched]:
            matched += 1
        if matched == len(pattern):
            occurrences.append(i - len(pattern) + 1)
            matched = prefix[matched - 1]

    return occurrences

def find_all_occurrences(text, pattern):
    m = len(pattern)
    if m > len(text):
        return []

    lps = [0] * m
    length = 0
    i = 1

    while i < m:
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        elif length:
            length = lps[length - 1]
        else:
            i += 1

    result = []
    i = j = 0

    while i < len(text):
        if text[i] == pattern[j]:
            i += 1
            j += 1
            if j == m:
                result.append(i - m)
                j = lps[j - 1]
        elif j:
            j = lps[j - 1]
        else:
            i += 1

    return result

SELECT
event_id,
user_id,
ts,
amt,
LAST_VALUE(amt) OVER (
PARTITION BY user_id
ORDER BY ts ASC, event_id ASC
ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING
) AS latest_amt
FROM events
ORDER BY user_id ASC, ts ASC, event_id ASC;

SELECT event_id, user_id, ts, amt, FIRST_VALUE(amt) OVER (PARTITION BY user_id ORDER BY ts DESC, event_id DESC) AS latest_amt FROM events ORDER BY user_id ASC, ts ASC, event_id ASC;

SELECT
    event_id,
    user_id,
    ts,
    amt,
    FIRST_VALUE(amt) OVER (
        PARTITION BY user_id
        ORDER BY ts DESC, event_id DESC
    ) AS latest_amt
FROM events
ORDER BY
    user_id ASC,
    ts ASC,
    event_id ASC;

SELECT
    event_id,
    user_id,
    ts,
    amt,
    FIRST_VALUE(amt) OVER (
        PARTITION BY user_id
        ORDER BY ts DESC, event_id DESC
        ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING
    ) AS latest_amt
FROM events
ORDER BY user_id ASC, ts ASC, event_id ASC;

SELECT
    event_id,
    user_id,
    ts,
    amt,
    FIRST_VALUE(amt) OVER (
        PARTITION BY user_id
        ORDER BY ts DESC, event_id DESC
        ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING
    ) AS latest_amt
FROM events
ORDER BY user_id ASC, ts ASC, event_id ASC;

SELECT
    event_id,
    user_id,
    ts,
    amt,
    LAST_VALUE(amt) OVER (
        PARTITION BY user_id
        ORDER BY ts, event_id
        ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING
    ) AS latest_amt
FROM events
ORDER BY user_id, ts, event_id;

SELECT
    event_id,
    user_id,
    ts,
    amt,
    FIRST_VALUE(amt) OVER (
        PARTITION BY user_id
        ORDER BY ts DESC, event_id DESC
    ) AS latest_amt
FROM events
ORDER BY
    user_id ASC,
    ts ASC,
    event_id ASC;

SELECT 
    event_id, 
    user_id, 
    ts, 
    amt,
    FIRST_VALUE(amt) OVER (
        PARTITION BY user_id 
        ORDER BY ts DESC, event_id DESC
    ) AS latest_amt
FROM events
ORDER BY user_id ASC, ts ASC, event_id ASC;

SELECT
    event_id,
    user_id,
    ts,
    amt,
    FIRST_VALUE(amt) OVER (
        PARTITION BY user_id
        ORDER BY ts DESC, event_id DESC
        ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING
    ) AS latest_amt
FROM events
ORDER BY user_id, ts, event_id;

SELECT event_id, user_id, ts, amt,
       FIRST_VALUE(amt) OVER (PARTITION BY user_id ORDER BY ts DESC, event_id DESC) AS latest_amt
FROM events
ORDER BY user_id ASC, ts ASC, event_id ASC;

SELECT
    event_id,
    user_id,
    ts,
    amt,
    FIRST_VALUE(amt) OVER (
        PARTITION BY user_id
        ORDER BY ts DESC, event_id DESC
    ) AS latest_amt
FROM events
ORDER BY user_id ASC, ts ASC, event_id ASC;

SELECT
    event_id,
    user_id,
    ts,
    amt,
    FIRST_VALUE(amt) OVER (
        PARTITION BY user_id
        ORDER BY ts DESC, event_id DESC
    ) AS latest_amt
FROM events
ORDER BY user_id ASC, ts ASC, event_id ASC;

SELECT
  event_id,
  user_id,
  ts,
  amt,
  FIRST_VALUE(amt) OVER (
    PARTITION BY user_id
    ORDER BY ts DESC, event_id DESC
  ) AS latest_amt
FROM events
ORDER BY user_id ASC, ts ASC, event_id ASC;

def make_validators(specs):
    validators = []

    def make_validator(field_name, min_len):
        def validator(value):
            result = len(value) >= min_len
            validator.cache[value] = result
            return result

        validator.field_name = field_name
        validator.cache = {}
        return validator

    for field_name, min_len in specs:
        validators.append(make_validator(field_name, min_len))

    return validators

def make_validators(specs):
    validators = []
    for field_name, min_len in specs:
        cache = {}
        def validator(value, _min_len=min_len, _cache=cache):
            if value in _cache:
                return _cache[value]
            result = len(value) >= _min_len
            _cache[value] = result
            return result
        validator.field_name = field_name
        validator.cache = cache
        validators.append(validator)
    return validators

def make_validators(specs):
    validators = []
    for field_name, min_len in specs:
        cache = {}
        def validator(value, min_len=min_len, cache=cache):
            if value in cache:
                return cache[value]
            result = len(value) >= min_len
            cache[value] = result
            return result
        validator.field_name = field_name
        validator.cache = cache
        validators.append(validator)
    return validators

def make_validators(specs):
    validators = []
    for field_name, min_len in specs:
        def make_validator(fname, mlen):
            cache = {}
            def validator(value):
                if value not in cache:
                    cache[value] = len(value) >= mlen
                return cache[value]
            validator.field_name = fname
            validator.cache = cache
            return validator
        validators.append(make_validator(field_name, min_len))
    return validators

def make_validators(specs):
    validators = []

    def make_validator(field_name, min_len):
        cache = {}

        def validator(value):
            if value in cache:
                return cache[value]
            result = len(value) >= min_len
            cache[value] = result
            return result

        validator.field_name = field_name
        validator.cache = cache
        return validator

    for field_name, min_len in specs:
        validators.append(make_validator(field_name, min_len))

    return validators

def make_validators(specs):
    validators = []
    for field_name, min_len in specs:
        cache = {}
        def validator(value, _min_len=min_len, _cache=cache):
            if value in _cache:
                return _cache[value]
            result = len(value) >= _min_len
            _cache[value] = result
            return result
        validator.field_name = field_name
        validator.cache = cache
        validators.append(validator)
    return validators

def make_validators(specs):
    class Validator:

        def __init__(self, field_name, min_len):
            self.field_name = field_name
            self.min_len = min_len
            self.cache = {}

        def __call__(self, value):
            if value not in self.cache:
                self.cache[value] = len(value) >= self.min_len
            return self.cache[value]

    return [Validator(field_name, min_len) for field_name, min_len in specs]

def make_validators(specs):
    validators = []
    for field_name, min_len in specs:
        cache = {}
        def validator(val, fn=field_name, ml=min_len, c=cache):
            if val in c:
                return c[val]
            res = len(val) >= ml
            c[val] = res
            return res
        validator.field_name = field_name
        validator.cache = cache
        validators.append(validator)
    return validators

def make_validators(specs):
    def make_one(field_name, min_len):
        cache = {}

        def validator(value):
            if value in cache:
                return cache[value]
            result = len(value) >= min_len
            cache[value] = result
            return result

        validator.field_name = field_name
        validator.cache = cache
        return validator

    return [make_one(field_name, min_len) for field_name, min_len in specs]

def make_validators(specs):
    validators = []
    for name, min_len in specs:
        cache = {}
        def validate(value, _cache=cache, _min_len=min_len):
            if value in _cache:
                return _cache[value]
            result = len(value) >= _min_len
            _cache[value] = result
            return result
        validate.field_name = name
        validate.cache = cache
        validators.append(validate)
    return validators

def make_validators(specs):
    validators = []

    for field_name, min_len in specs:
        def validator(value, min_len=min_len):
            if value not in validator.cache:
                validator.cache[value] = len(value) >= min_len
            return validator.cache[value]

        validator.field_name = field_name
        validator.cache = {}
        validators.append(validator)

    return validators

def make_validators(specs):
    def make_validator(field_name, min_len):
        cache = {}

        def validator(value):
            result = len(value) >= min_len
            cache[value] = result
            return result

        validator.field_name = field_name
        validator.cache = cache
        return validator

    return [make_validator(field_name, min_len) for field_name, min_len in specs]

def make_validators(specs):
    validators = []

    for field_name, min_len in specs:
        def validator(value, min_len=min_len):
            result = len(value) >= min_len
            validator.cache[value] = result
            return result

        validator.field_name = field_name
        validator.cache = {}
        validators.append(validator)

    return validators

Q1: 3
Q2: 3
Q3: yllacihcrareih
Q4: 8
Q5: 12

Q1. 3
Q2. 3
Q3. yllacihcrareih
Q4. 8
Q5. 12

Q1: 3
Q2: 3
Q3: yllacihcrareih
Q4: 8
Q5: 12

Q1: 3
Q2: 3
Q3: yllacihcrareih
Q4: 8
Q5: 12

Q1. 3
Q2. 3
Q3. ylllacihcrarheih
Q4. 8
Q5. 12

Q1. 3
Q2. 3
Q3. yllacihcrareih
Q4. 8
Q5. 12

Q1. 3
Q2. 3
Q3. yllacihcraereih
Q4. 8
Q5. 12

Q1. 3
Q2. 3
Q3. yllacihcrareih
Q4. 8
Q5. 13

Q1: 3
Q2: 3
Q3: yllacihcrareih
Q4: 8
Q5: 12

Q1: 3
Q2: 3
Q3: yllacihcrareih
Q4: 8
Q5: 12

Q1. 3
Q2. 3
Q3. yllacihcrareih
Q4. 8
Q5. 12

Q1. 3
Q2. 3
Q3. yllacihcrareih
Q4. 8
Q5. 12

Q1. 3
Q2. 3
Q3. yllacihcrarieh
Q4. 8
Q5. 12

Waves crash upon the distant sandy shore
And pull the tide back to sea
Vast waters shimmer beneath the pale moon
Endless waves return once more to sea

Waves crash upon the sandy shore forever
Azure depths hide mysteries of the deep
Vast blue expanse calls to wandering souls
Endless tides return to kiss the deep

Waves whisper secrets to the silent shore
Ancient rhythms echo in the coral deep
Vast darkness holds the tide's eternal sweep
Endless horizon mirrors a tranquil breathing deep

Where restless tides carry salt and song
Ancient currents pull the moon toward shore
Vast horizons swallow every ship's lonely light
Endless waves return to kiss the shore

Waves crash against the rocky, endless shore
Alone I watch the tide retreat again
Vast waters hold the moon and stars
Every night the waves come home again

Waves crash against the shore at dawn
And salt spray fills the morning tide
Vast blue water stretches far beyond sight
Every wave returns again with the tide

Wild foam rises high above the abyss.
Always crashing softly on the distant shore.
Vast blue waters carry all our dreams.
Endless tides return to touch the shore.

Water crashes softly on the endless shore,
Above the deep and dark blue sea,
Vast currents pull towards the ocean floor,
Echoes of waves upon the blue sea.

Waves gather salt and light at dawn
Ancient tides keep rolling toward the shore
Vast water breathes beneath a silver moon
Every wave returns me to that shore

Waves kiss the sand while stars drift
And sea foam reaches toward the shore
Vast depths hold secrets none can hear
Every restless wave returns back to shore

Waves cradle moonlight beneath the listening stars
Ancient tides whisper secrets into blue night
Vast currents carry dreams beyond silent shores
Endless foam returns singing through the night

Waves whisper beneath moonlit skies tonight softly  
Azure currents cradle dreams of distant shores  
Vast tides carry starlight through the night  
Endless blue returns, singing through the night

Waves whisper silver secrets beneath moonlit skies tonight  
Abyssal currents cradle dreaming ships in silence  
Vast horizons promise storms, stars, and distant homecomings  
Eternal tides return each heart to silence

Q1. $0.05 — The ball costs five cents because x + (x + $1.00) = $1.10.
Q2. 5 minutes — Each machine makes one widget in five minutes, so 100 machines make 100 widgets in five minutes.
Q3. 3 — Take the fox and chicken across, return with the fox, then take the fox and grain across.
Q4. 1/2 — Each flip of a fair coin is independent, so the probability remains one half.

Q1. $0.05 (ball + bat = 1.10, bat = ball + 1)
Q2. 5 minutes (each machine makes one widget every 5 min)
Q3. 3 (take fox+grain, return alone, take chicken)
Q4. 1/2 (flips are independent)

Q1: $0.05. The ball costs 5 cents because the bat is $1.05.
Q2: 5 minutes. Each machine makes one widget in 5 minutes, so 100 machines make 100 widgets in the same time.
Q3: 3 crossings. The farmer takes the fox and grain across, returns alone, then takes the chicken.
Q4: 1/2. The coin flips are independent, so past results do not affect the next flip.

Q1. $0.05 — the bat is $1.05, difference exactly $1.00.
Q2. 5 minutes — each machine makes one widget in 5 minutes.
Q3. 3 crossings — take fox + grain over, return alone (chicken alone is safe), bring chicken over.
Q4. 1/2 — flips are independent; past results don't matter.

Q1. $0.05 — since bat = ball + $1.00, ball + (ball+1.00) = 1.10.
Q2. 5 minutes — each machine independently makes one widget in 5 minutes.
Q3. 1 — the farmer can take both the fox and the grain (or fox+chicken+grain isn't needed) since boat holds two items, fox and grain together, leaving chicken alone safely, all in one crossing).
Q4. 1/2 — coin flips are independent, past results don't affect the next flip.

Q1. $0.05 — the ball is 5¢ and the bat $1.05, differing by exactly $1.00.
Q2. 5 minutes — each machine makes one widget in 5 minutes, so scaling machines and widgets equally keeps the time fixed.
Q3. 3 — take two items over, return empty, take the last (e.g., fox+grain over, return, chicken over), which is the fewest possible since 3 items at 2 per trip needs 2 forward + 1 return.
Q4. 1/2 — the coin is fair and flips are independent, so prior heads don't change it.

Q1. $0.05 (or 5 cents) — Solving $x + (x + \$1.00) = \$1.10$ gives the cost of the ball as $x = \$0.05$.
Q2. 5 minutes — Each machine takes 5 minutes to make one widget, so 100 machines operating simultaneously will produce 100 widgets in 5 minutes.
Q3. 3 — The farmer takes the fox and grain first (1), returns alone (2), and then takes the chicken across (3).
Q4. 1/2 (or 50%) — Coin flips are independent events, so previous outcomes do not affect the probability of the 6th flip.

Q1. $0.05; The ball costs 5 cents and the bat costs $1.05, which equals $1.10 and a $1.00 difference.
Q2. 5 minutes; Each machine makes one widget in 5 minutes, so 100 machines working simultaneously will make 100 widgets in 5 minutes.
Q3. 2; Since the boat holds the farmer and both items, the farmer can take all three across in a single round-trip, resulting in 2 one-way crossings.
Q4. 1/2; Coin flips are independent events, so past results do not affect the probability of future flips.

Q1. $0.05 — the bat is $1.05, which is exactly $1.00 more, and together they make $1.10.
Q2. 5 minutes — each machine takes 5 minutes per widget, so 100 machines make 100 widgets in parallel.
Q3. 3 crossings — take fox + grain over, return empty, bring the chicken (chicken alone, then fox+grain alone, are both safe).
Q4. 1/2 — the coin is fair and flips are independent, so past results don't matter.

Q1. $0.05.
Q2. 5 minutes.
Q3. 3 crossings.
Q4. 1/2.

Q1. $0.05 — The bat costs $1.05.  
Q2. 5 minutes — Each machine makes one widget in 5 minutes.  
Q3. 3 crossings — Take fox and grain across, return alone, then take the chicken.  
Q4. 1/2 — Independent fair-coin flips are unaffected by prior results.

Q1. $0.05 — The ball is x and the bat is x + $1.00, so 2x = $0.10.

Q2. 5 minutes — Each machine makes one widget in 5 minutes.

Q3. 3 crossings — Carry the fox and grain over, return alone, then carry the chicken over.

Q4. 1/2 — Coin flips are independent.

Q1. 5¢.  
Q2. 5 minutes.  
Q3. 3 crossings.  
Q4. 50%.

1. Final approved infra budget: Rs 53 lakh (Meeting 33, 2026-05-10) — the steering group confirmed no further changes this year. (Earlier figures of Rs 42 lakh in Meeting 03 and Rs 48 lakh in Meeting 15 were superseded.)
2. Vector-store migration owner and role: Meera Pillai, Staff Data Engineer (Meeting 09).
3. Load-test target change: on 2026-05-14, raised from 8,000 to 12,500 requests per second (the original 8,000 rps figure was set in Meeting 07).
4. Mobile-app launch deferrals: three times — 2026-08-17 → 2026-09-21 (Meeting 18) → 2026-10-19 (Meeting 24) → 2026-11-09, final and frozen (Meeting 38).
5. Rejected vendor: CloudKanta, after failing the data-residency audit (Meeting 12); Nimbara was selected instead.

1. Rs 53 lakh (final revision in Meeting 33 on 2026-05-10).
2. Meera Pillai, Staff Data Engineer (Meeting 09).
3. 2026-05-14, raised from 8,000 to 12,500 requests per second (noted in Meeting 29).
4. Three times; final date 2026-11-09 (deferred in Meetings 18, 24, and 38).
5. CloudKanta, after failing the data-residency audit (Meeting 12).

1. Final approved infra budget: Rs 53 lakh (Meeting 33).
2. Vector-store migration owner: Meera Pillai, Staff Data Engineer (Meeting 09).
3. Load-test target change: on 2026-05-14, from 8,000 to 12,500 requests per second (Meeting 29, referencing the 2026-05-14 meeting).
4. Mobile-app launch deferred: 3 times; final date frozen at 2026-11-09 (Meetings 18, 24, 38).
5. Rejected vendor: CloudKanta, for failing the data-residency audit (Meeting 12).

1. Rs 53 lakh (Meeting 33, 2026-05-10, final revision — steering group confirmed no further changes).
2. Meera Pillai, Staff Data Engineer.
3. 2026-05-14 — raised from 8,000 to 12,500 requests per second (noted in Meeting 29 minutes).
4. Three times: 2026-08-17 → 2026-09-21 → 2026-10-19 → 2026-11-09 (final, frozen).
5. CloudKanta — rejected after failing the data-residency audit (Nimbara selected instead).

1. Rs 53 lakh (Meeting 33, 2026-05-10).
2. Meera Pillai, Staff Data Engineer.
3. 2026-05-14; from 8,000 to 12,500 requests per second.
4. Deferred three times, final date 2026-11-09.
5. CloudKanta, rejected after failing the data-residency audit.

1. Rs 53 lakh — the final revision (Meeting 33, 2026-05-10), approved with no further changes for the year.
2. Meera Pillai, whose role is Staff Data Engineer (Meeting 09).
3. 2026-05-14 — raised from 8,000 to 12,500 requests per second, following the capacity forecast review (noted in Meeting 29).
4. Three times, to a final frozen date of 2026-11-09 (08-17 → 09-21 → 10-19 → 11-09).
5. CloudKanta, rejected for failing the data-residency audit (Meeting 12); Nimbara was chosen instead.

Based on the Project Meghdoot consolidated meeting minutes archive:

1. **FINAL approved infra budget:** Rs 53 lakh (approved in Meeting 33, dated 2026-05-10).
2. **Vector-store migration ownership:** Meera Pillai, Staff Data Engineer (mentioned in Meeting 09).
3. **Load-test target change:** In the meeting dated **2026-05-14**, the target was raised from **8,000 to 12,500** requests per second (mentioned in Meeting 29).
4. **Mobile-app launch deferrals:** It was deferred **3 times** (Meeting 18, Meeting 24, and Meeting 38), to the final frozen date of **2026-11-09**.
5. **Rejected vendor:** **CloudKanta**, rejected after failing the data-residency audit (mentioned in Meeting 12).

**1. Final approved infra budget: Rs 53 lakh.**
Meeting 33 (2026-05-10) — "final revision — the infra budget was approved at Rs 53 lakh; the steering group confirmed no further changes this year." (Trail: Rs 42 lakh → Rs 48 lakh → Rs 53 lakh.)

**2. Vector-store migration owner: Meera Pillai, Staff Data Engineer.**
Meeting 09 (2026-02-07). The *search-index* migration is a separate item, owned by Nikhil Joshi.

**3. Load-test target changed on 2026-05-14, from 8,000 to 12,500 requests per second**, after the capacity forecast review. (Original 8,000 rps target set in Meeting 07, 2026-01-28. Note the record of the change appears in the Meeting 29 block dated 2026-04-27, but it explicitly cites the meeting dated 2026-05-14 as when the change happened.)

**4. Deferred three times; final date 2026-11-09.**
2026-08-17 → 2026-09-21 (ingestion backlog, Mtg 18) → 2026-10-19 (regional failover, Mtg 24) → 2026-11-09 (Mtg 38, "third and final time," date now frozen).

**5. CloudKanta was rejected — for failing the data-residency audit.**
Meeting 12 (2026-02-19); Nimbara was selected as primary vendor instead.

Based on the consolidated meeting minutes archive, here are the answers to your questions:

1. **Final Approved Infra Budget:** **Rs 53 lakh** *(approved in Meeting 33 as the final revision)*.
2. **Vector-Store Migration Owner & Role:** **Meera Pillai**, **Staff Data Engineer** *(noted in Meeting 09)*.
3. **Load-Test Target Change Date & Values:** **2026-05-14**, raised from **8,000 to 12,500 requests per second** *(noted in Meeting 29)*.
4. **Mobile-App Launch Deferrals & Final Date:** Deferred **3 times**, to a final frozen date of **2026-11-09** *(deferred in Meetings 18, 24, and 38)*.
5. **Rejected Vendor & Reason:** **CloudKanta**, rejected for **failing the data-residency audit** *(noted in Meeting 12)*.

Found 4 direct factual contradictions:

1. Session timeout / expiry conflict
   Section 2: "Idle sessions time out after 30 minutes and require re-authentication."
   Section 9: "Sessions expire after 45 minutes of inactivity, after which a fresh login is required."
   These give different inactivity-timeout values (30 vs. 45 minutes) for the same behavior.

2. Concurrent device limit conflict
   Section 3: "An account supports at most 5 concurrent devices."
   Section 11: "Up to 8 devices may be active simultaneously on a single account."
   5 vs. 8 concurrent devices for the same account.

3. Timestamp storage timezone conflict
   Section 4: "All timestamps are stored in UTC and converted at render time."
   Section 12: "Timestamps are stored in the user's local timezone as captured at write time."
   UTC vs. local timezone — mutually exclusive storage rules.

4. Free-tier project limit conflict
   Section 6: "The free tier includes 3 projects with unlimited collaborators."
   Section 14: "Free-tier accounts are limited to a single project."
   3 projects vs. 1 project on the free tier.

Contradictions found:

1. Session timeout policy
   Section 2: "Idle sessions time out after 30 minutes and require re-authentication."
   Section 9: "Sessions expire after 45 minutes of inactivity, after which a fresh login is required."
   (Cannot both be true.)

2. Concurrent device limit per account
   Section 3: "An account supports at most 5 concurrent devices."
   Section 11: "Up to 8 devices may be active simultaneously on a single account."
   (Cannot both be true.)

3. Timestamp storage
   Section 4: "All timestamps are stored in UTC and converted at render time."
   Section 12: "Timestamps are stored in the user's local timezone as captured at write time."
   (Cannot both be true.)

4. Free-tier project limit
   Section 6: "The free tier includes 3 projects with unlimited collaborators."
   Section 14: "Free-tier accounts are limited to a single project."
   (Cannot both be true.)

These are all the direct factual contradictions in the document. No other pairs of statements present mutually incompatible facts.

1. Session timeout duration
   Section 2: "Idle sessions time out after 30 minutes and require re-authentication."
   Section 9: "Sessions expire after 45 minutes of inactivity, after which a fresh login is required."

2. Maximum concurrent devices per account
   Section 3: "An account supports at most 5 concurrent devices."
   Section 11: "Up to 8 devices may be active simultaneously on a single account."

3. Timestamp storage convention
   Section 4: "All timestamps are stored in UTC and converted at render time."
   Section 12: "Timestamps are stored in the user's local timezone as captured at write time."

4. Free-tier project limit
   Section 6: "The free tier includes 3 projects with unlimited collaborators."
   Section 14: "Free-tier accounts are limited to a single project."

I found three groups of contradictions, all concerning quantitative product limits.

Contradiction 1 — session/idle timeout duration (three-way conflict)
Section 2: "Idle sessions time out after 30 minutes and require re-authentication."
Section 9: "Sessions expire after 45 minutes of inactivity, after which a fresh login is required."
These give different inactivity timeout values (30 vs. 45 minutes) for the same behavior.

Contradiction 2 — concurrent devices per account (three-way conflict)
Section 3: "An account supports at most 5 concurrent devices."
Section 11: "Up to 8 devices may be active simultaneously on a single account."
These give different maximum simultaneous-device counts (5 vs. 8) for a single account.

Contradiction 3 — free-tier project allowance
Section 6: "The free tier includes 3 projects with unlimited collaborators."
Section 14: "Free-tier accounts are limited to a single project."
These give different free-tier project limits (3 vs. 1).

Contradiction 4 — timestamp storage timezone
Section 4: "All timestamps are stored in UTC and converted at render time."
Section 12: "Timestamps are stored in the user's local timezone as captured at write time."
These specify mutually exclusive storage schemes for timestamps (UTC vs. local timezone at write time).

1. Session timeout
   Sec 2: "Idle sessions time out after 30 minutes and require re-authentication."
   Sec 9: "Sessions expire after 45 minutes of inactivity, after which a fresh login is required."

2. Concurrent device limit
   Sec 3: "An account supports at most 5 concurrent devices."
   Sec 11: "Up to 8 devices may be active simultaneously on a single account."

3. Timestamp storage
   Sec 4: "All timestamps are stored in UTC and converted at render time."
   Sec 12: "Timestamps are stored in the user's local timezone as captured at write time."

4. Free-tier project limit
   Sec 6: "The free tier includes 3 projects with unlimited collaborators."
   Sec 14: "Free-tier accounts are limited to a single project."

I found two clusters of direct contradictions — one about session/inactivity timeouts, one about device and project limits.

Contradiction 1 — Session inactivity timeout
Section 2: "Idle sessions time out after 30 minutes and require re-authentication."
Section 9: "Sessions expire after 45 minutes of inactivity, after which a fresh login is required."
30 minutes vs. 45 minutes for the same idle-timeout behavior.

Contradiction 2 — Timestamp storage
Section 4: "All timestamps are stored in UTC and converted at render time."
Section 12: "Timestamps are stored in the user's local timezone as captured at write time."
UTC vs. local timezone — mutually exclusive storage rules.

Contradiction 3 — Maximum concurrent devices
Section 3: "An account supports at most 5 concurrent devices."
Section 11: "Up to 8 devices may be active simultaneously on a single account."
5 vs. 8 concurrent devices.

Contradiction 4 — Free-tier project limit
Section 6: "The free tier includes 3 projects with unlimited collaborators."
Section 14: "Free-tier accounts are limited to a single project."
3 projects vs. 1 project on the free tier.

Based on the product specification provided, there are several factual contradictions where different statements present opposing rules regarding system constraints. Here is the list of every contradiction found, including their exact quotes and section numbers:

### Contradiction 1: Maximum concurrent devices per account
* **Section 3 Quote:** *"An account supports at most 5 concurrent devices."*
* **Section 11 Quote:** *"Up to 8 devices may be active simultaneously on a single account."*

### Contradiction 2: Project limits for free-tier accounts
* **Section 6 Quote:** *"The free tier includes 3 projects with unlimited collaborators."*
* **Section 14 Quote:** *"Free-tier accounts are limited to a single project."*

### Contradiction 3: Timestamp storage and timezone handling
* **Section 4 Quote:** *"All timestamps are stored in UTC and converted at render time."*
* **Section 12 Quote:** *"Timestamps are stored in the user's local timezone as captured at write time."*

Four direct contradictions. Everything else in the document is repetitive filler with no factual claims to conflict.

**1. Session/idle timeout — 30 min vs 45 min**
- §2: "Idle sessions time out after 30 minutes and require re-authentication."
- §9: "Sessions expire after 45 minutes of inactivity, after which a fresh login is required."

**2. Concurrent device limit — 5 vs 8**
- §3: "An account supports at most 5 concurrent devices."
- §11: "Up to 8 devices may be active simultaneously on a single account."

**3. Free-tier project count — 3 vs 1**
- §6: "The free tier includes 3 projects with unlimited collaborators."
- §14: "Free-tier accounts are limited to a single project."

**4. Timestamp storage — UTC vs local timezone**
- §4: "All timestamps are stored in UTC and converted at render time."
- §12: "Timestamps are stored in the user's local timezone as captured at write time."

Note on scope: §5 and §6 are both titled "On-Call Rotation," as are §7/§8/§10 ("Queue Re-Partitioning"), §12/§13 ("Schema Versioning"), and §15/§16 ("Capacity Forecast") — that's a structural/organizational defect, not a factual conflict, so I've left it out of the list above.

Here are the internal contradictions found in the specification document:

---

### 1. Session Inactivity / Timeout
* **Section 2:** "Idle sessions time out after 30 minutes and require re-authentication."
* **Section 9:** "Sessions expire after 45 minutes of inactivity, after which a fresh login is required."

---

### 2. Concurrent Device Limits
* **Section 3:** "An account supports at most 5 concurrent devices."
* **Section 11:** "Up to 8 devices may be active simultaneously on a single account."

---

### 3. Timestamp Storage Format
* **Section 4:** "All timestamps are stored in UTC and converted at render time."
* **Section 12:** "Timestamps are stored in the user's local timezone as captured at write time."

---

### 4. Free Tier Project Limits
* **Section 6:** "The free tier includes 3 projects with unlimited collaborators."
* **Section 14:** "Free-tier accounts are limited to a single project."