GPU Credit Management - Optimized Queries

Design a credit manager that tracks GPU credits that can be added, expire, and be consumed. The system must support three operations, all tagged with a monotonically increasing timestamp t:

1. add(t, x, t_expire) – add x credits at time t that will expire at t_expire (t_expire > t).
2. cost(t, x) – attempt to consume x credits at time t. Deduct the oldest non-expired credits first (FIFO). If the current balance at t is insufficient return False and change nothing; otherwise deduct and return True.
3. query(t) – return the number of non-expired credits at time t.

All operations arrive in non-decreasing order of t. The implementation must be optimized for high throughput: add and cost must run in amortized O(log n) or better, and query in O(1). You may assume that the total number of add operations is ≤ 10⁶ and that credit values and balances never exceed 2³¹-1.