Fix the Python function below. Return JSON with exactly one key, "code", whose string is the complete replacement module. Do not include markdown or prose. This is a pure Python function task; no imports, filesystem, network or external tools are needed.

Required interface: paginate(records, limit, cursor=None) returns {"items": list, "next_cursor": tuple_or_None}.

Every record is a dict with unique string id, canonical fixed-width UTC timestamp "YYYY-MM-DDTHH:MM:SSZ", and arbitrary other fields. Input may be unsorted. Order records by descending timestamp, then ascending id. A cursor is a (timestamp, id) tuple representing the last emitted row; return rows strictly after it in that ordering, even if the cursor row is absent. Never mutate the caller's list or records. Preserve all record fields. next_cursor is the last returned row's (timestamp, id) only if at least one additional eligible row exists; otherwise it is None. For empty results it is None. limit must be an integer from 1 through 100, excluding booleans; raise ValueError for every invalid limit, even on empty input. A non-None cursor must be a 2-tuple of strings; raise ValueError otherwise.

Faulty implementation:
def paginate(records, limit, cursor=None):
    records.sort(key=lambda row: row["timestamp"])
    if cursor:
        records = [row for row in records if row["timestamp"] > cursor[0]]
    page = records[:limit]
    next_cursor = (page[-1]["timestamp"], page[-1]["id"]) if page else None
    return {"items": page, "next_cursor": next_cursor}
