All O(1) Data Structure

class AllOne {
    unordered_map<string, int> counts;
public:
    void inc(string key) {
        counts[key] = counts[key] + 1;
    }
    void dec(string key) {
        auto it = counts.find(key);
        if (it == counts.end()) return;
        if (it->second == 1) counts.erase(it);
        else it->second -= 1;
    }
    string getMaxKey() {
        string best = "";
        int bestCount = 0;
        for (auto& [k, c] : counts) {
            if (c > bestCount) { best = k; bestCount = c; }
        }
        return best;
    }
    string getMinKey() {
        string best = "";
        int bestCount = INT_MAX;
        for (auto& [k, c] : counts) {
            if (c < bestCount) { best = k; bestCount = c; }
        }
        return best;
    }
};

class AllOne {
    private Map<String, Integer> counts = new HashMap<>();
    public void inc(String key) {
        counts.put(key, counts.getOrDefault(key, 0) + 1);
    }
    public void dec(String key) {
        Integer c = counts.get(key);
        if (c == null) return;
        if (c == 1) counts.remove(key);
        else counts.put(key, c - 1);
    }
    public String getMaxKey() {
        String best = "";
        int bestCount = 0;
        for (Map.Entry<String, Integer> e : counts.entrySet()) {
            if (e.getValue() > bestCount) { best = e.getKey(); bestCount = e.getValue(); }
        }
        return best;
    }
    public String getMinKey() {
        String best = "";
        int bestCount = Integer.MAX_VALUE;
        for (Map.Entry<String, Integer> e : counts.entrySet()) {
            if (e.getValue() < bestCount) { best = e.getKey(); bestCount = e.getValue(); }
        }
        return best;
    }
}

class AllOne:
    def __init__(self):
        self.counts = {}
    def inc(self, key):
        self.counts[key] = self.counts.get(key, 0) + 1
    def dec(self, key):
        c = self.counts.get(key)
        if c is None: return
        if c == 1: del self.counts[key]
        else: self.counts[key] = c - 1
    def getMaxKey(self):
        best = ''
        best_count = 0
        for k, c in self.counts.items():
            if c > best_count: best, best_count = k, c
        return best
    def getMinKey(self):
        best = ''
        best_count = float('inf')
        for k, c in self.counts.items():
            if c < best_count: best, best_count = k, c
        return best

class AllOne {
  private counts = new Map<string, number>();
  inc(key: string): void {
    this.counts.set(key, (this.counts.get(key) ?? 0) + 1);
  }
  dec(key: string): void {
    const c = this.counts.get(key);
    if (c === undefined) return;
    if (c === 1) this.counts.delete(key);
    else this.counts.set(key, c - 1);
  }
  getMaxKey(): string {
    let best = '';
    let bestCount = 0;
    for (const [k, c] of this.counts) {
      if (c > bestCount) { best = k; bestCount = c; }
    }
    return best;
  }
  getMinKey(): string {
    let best = '';
    let bestCount = Infinity;
    for (const [k, c] of this.counts) {
      if (c < bestCount) { best = k; bestCount = c; }
    }
    return best;
  }
}

class AllOne {
    unordered_map<string, int> counts;
    unordered_map<int, set<string>> buckets;
    void move(const string& key, int from, int to) {
        if (from > 0) {
            set<string>& old = buckets[from];
            old.erase(key);
            if (old.empty()) buckets.erase(from);
        }
        if (to > 0) {
            if (!buckets.count(to)) buckets[to] = {};
            buckets[to].insert(key);
            counts[key] = to;
        } else {
            counts.erase(key);
        }
    }
public:
    void inc(string key) {
        int c = counts.count(key) ? counts[key] : 0;
        move(key, c, c + 1);
    }
    void dec(string key) {
        auto it = counts.find(key);
        if (it == counts.end()) return;
        int c = it->second; move(key, c, c - 1);
    }
    string getMaxKey() {
        if (buckets.empty()) return "";
        int top = 0; for (auto& [c, keys] : buckets) top = max(top, c);
        return *buckets[top].begin();
    }
    string getMinKey() {
        if (buckets.empty()) return "";
        int low = INT_MAX; for (auto& [c, keys] : buckets) low = min(low, c);
        return *buckets[low].begin();
    }
};

class AllOne {
    private Map<String, Integer> counts = new HashMap<>();
    private Map<Integer, LinkedHashSet<String>> buckets = new HashMap<>();
    private void move(String key, int from, int to) {
        if (from > 0) {
            LinkedHashSet<String> old = buckets.get(from);
            old.remove(key);
            if (old.isEmpty()) buckets.remove(from);
        }
        if (to > 0) {
            buckets.putIfAbsent(to, new LinkedHashSet<>());
            buckets.get(to).add(key);
            counts.put(key, to);
        } else {
            counts.remove(key);
        }
    }
    public void inc(String key) {
        int c = counts.getOrDefault(key, 0);
        move(key, c, c + 1);
    }
    public void dec(String key) {
        Integer c = counts.get(key);
        if (c == null) return;
        move(key, c, c - 1);
    }
    public String getMaxKey() {
        if (buckets.isEmpty()) return "";
        int top = Collections.max(buckets.keySet());
        return buckets.get(top).iterator().next();
    }
    public String getMinKey() {
        if (buckets.isEmpty()) return "";
        int low = Collections.min(buckets.keySet());
        return buckets.get(low).iterator().next();
    }
}

class AllOne:
    def __init__(self):
        self.counts = {}
        self.buckets = {}  # count -> dict used as an insertion-ordered set of keys
    def _move(self, key, frm, to):
        if frm > 0:
            old = self.buckets[frm]
            del old[key]
            if not old: del self.buckets[frm]
        if to > 0:
            if to not in self.buckets: self.buckets[to] = {}
            self.buckets[to][key] = None
            self.counts[key] = to
        else:
            del self.counts[key]
    def inc(self, key):
        c = self.counts.get(key, 0)
        self._move(key, c, c + 1)
    def dec(self, key):
        c = self.counts.get(key)
        if c is None: return
        self._move(key, c, c - 1)
    def getMaxKey(self):
        if not self.buckets: return ''
        top = max(self.buckets)
        return next(iter(self.buckets[top]))
    def getMinKey(self):
        if not self.buckets: return ''
        low = min(self.buckets)
        return next(iter(self.buckets[low]))

class AllOne {
  private counts = new Map<string, number>();
  private buckets = new Map<number, Set<string>>();
  private move(key: string, from: number, to: number): void {
    if (from > 0) {
      const old = this.buckets.get(from)!;
      old.delete(key);
      if (old.size === 0) this.buckets.delete(from);
    }
    if (to > 0) {
      if (!this.buckets.has(to)) this.buckets.set(to, new Set());
      this.buckets.get(to)!.add(key);
      this.counts.set(key, to);
    } else {
      this.counts.delete(key);
    }
  }
  inc(key: string): void {
    const c = this.counts.get(key) ?? 0;
    this.move(key, c, c + 1);
  }
  dec(key: string): void {
    const c = this.counts.get(key);
    if (c === undefined) return;
    this.move(key, c, c - 1);
  }
  getMaxKey(): string {
    if (this.buckets.size === 0) return '';
    const top = Math.max(...this.buckets.keys());
    return this.buckets.get(top)!.values().next().value as string;
  }
  getMinKey(): string {
    if (this.buckets.size === 0) return '';
    const low = Math.min(...this.buckets.keys());
    return this.buckets.get(low)!.values().next().value as string;
  }
}

struct Bucket {
    set<string> keys;
    Bucket *prev = nullptr, *next = nullptr;
    int count;
    Bucket(int c) : count(c) {}
};
class AllOne {
    unordered_map<string, Bucket*> nodeOf;
    Bucket* head = new Bucket(0);
    Bucket* tail = new Bucket(INT_MAX);
    Bucket* insertAfter(Bucket* node, int count) {
        Bucket* b = new Bucket(count);
        b->prev = node;
        b->next = node->next;
        node->next->prev = b;
        node->next = b;
        return b;
    }
    void unlink(Bucket* b) {
        b->prev->next = b->next;
        b->next->prev = b->prev;
        delete b;
    }
public:
    AllOne() {
        head->next = tail;
        tail->prev = head;
    }
    void inc(string key) {
        auto it = nodeOf.find(key);
        Bucket* cur = it == nodeOf.end() ? head : it->second;
        Bucket* next = cur->next;
        if (next->count != cur->count + 1) next = insertAfter(cur, cur->count + 1);
        next->keys.insert(key);
        nodeOf[key] = next;
        if (cur != head) {
            cur->keys.erase(key);
            if (cur->keys.empty()) unlink(cur);
        }
    }
    void dec(string key) {
        auto it = nodeOf.find(key);
        Bucket* cur = it == nodeOf.end() ? nullptr : it->second;
        if (!cur) return;
        if (cur->count == 1) {
            nodeOf.erase(key);
        } else {
            Bucket* prev = cur->prev;
            if (prev->count != cur->count - 1) prev = insertAfter(prev, cur->count - 1);
            prev->keys.insert(key);
            nodeOf[key] = prev;
        }
        cur->keys.erase(key);
        if (cur->keys.empty()) unlink(cur);
    }
    string getMaxKey() {
        Bucket* b = tail->prev;
        return b == head ? "" : *b->keys.begin();
    }
    string getMinKey() {
        Bucket* b = head->next;
        return b == tail ? "" : *b->keys.begin();
    }
};

class Bucket {
    LinkedHashSet<String> keys = new LinkedHashSet<>();
    Bucket prev, next;
    int count;
    Bucket(int count) { this.count = count; }
}
class AllOne {
    private Map<String, Bucket> nodeOf = new HashMap<>();
    private Bucket head = new Bucket(0);
    private Bucket tail = new Bucket(Integer.MAX_VALUE);
    public AllOne() {
        head.next = tail;
        tail.prev = head;
    }
    private Bucket insertAfter(Bucket node, int count) {
        Bucket b = new Bucket(count);
        b.prev = node;
        b.next = node.next;
        node.next.prev = b;
        node.next = b;
        return b;
    }
    private void unlink(Bucket b) {
        b.prev.next = b.next;
        b.next.prev = b.prev;
    }
    public void inc(String key) {
        Bucket cur = nodeOf.getOrDefault(key, head);
        Bucket next = cur.next;
        if (next.count != cur.count + 1) next = insertAfter(cur, cur.count + 1);
        next.keys.add(key);
        nodeOf.put(key, next);
        if (cur != head) {
            cur.keys.remove(key);
            if (cur.keys.isEmpty()) unlink(cur);
        }
    }
    public void dec(String key) {
        Bucket cur = nodeOf.get(key);
        if (cur == null) return;
        if (cur.count == 1) {
            nodeOf.remove(key);
        } else {
            Bucket prev = cur.prev;
            if (prev.count != cur.count - 1) prev = insertAfter(prev, cur.count - 1);
            prev.keys.add(key);
            nodeOf.put(key, prev);
        }
        cur.keys.remove(key);
        if (cur.keys.isEmpty()) unlink(cur);
    }
    public String getMaxKey() {
        Bucket b = tail.prev;
        return b == head ? "" : b.keys.iterator().next();
    }
    public String getMinKey() {
        Bucket b = head.next;
        return b == tail ? "" : b.keys.iterator().next();
    }
}

class Bucket:
    def __init__(self, count):
        self.keys = {}  # insertion-ordered set
        self.prev = None
        self.next = None
        self.count = count
class AllOne:
    def __init__(self):
        self.node_of = {}
        self.head = Bucket(0)
        self.tail = Bucket(float('inf'))
        self.head.next = self.tail
        self.tail.prev = self.head
    def _insert_after(self, node, count):
        b = Bucket(count)
        b.prev = node
        b.next = node.next
        node.next.prev = b
        node.next = b
        return b
    def _unlink(self, b):
        b.prev.next = b.next
        b.next.prev = b.prev
    def inc(self, key):
        cur = self.node_of.get(key, self.head)
        nxt = cur.next
        if nxt.count != cur.count + 1: nxt = self._insert_after(cur, cur.count + 1)
        nxt.keys[key] = None
        self.node_of[key] = nxt
        if cur is not self.head:
            del cur.keys[key]
            if not cur.keys: self._unlink(cur)
    def dec(self, key):
        cur = self.node_of.get(key)
        if cur is None: return
        if cur.count == 1:
            del self.node_of[key]
        else:
            prev = cur.prev
            if prev.count != cur.count - 1: prev = self._insert_after(prev, cur.count - 1)
            prev.keys[key] = None
            self.node_of[key] = prev
        del cur.keys[key]
        if not cur.keys: self._unlink(cur)
    def getMaxKey(self):
        b = self.tail.prev
        return '' if b is self.head else next(iter(b.keys))
    def getMinKey(self):
        b = self.head.next
        return '' if b is self.tail else next(iter(b.keys))

class Bucket {
  keys = new Set<string>();
  prev: Bucket | null = null;
  next: Bucket | null = null;
  constructor(public count: number) {}
}
class AllOne {
  private nodeOf = new Map<string, Bucket>();
  private head = new Bucket(0);
  private tail = new Bucket(Infinity);
  constructor() {
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }
  private insertAfter(node: Bucket, count: number): Bucket {
    const b = new Bucket(count);
    b.prev = node;
    b.next = node.next;
    node.next!.prev = b;
    node.next = b;
    return b;
  }
  private unlink(b: Bucket): void {
    b.prev!.next = b.next;
    b.next!.prev = b.prev;
  }
  inc(key: string): void {
    const cur = this.nodeOf.get(key) ?? this.head;
    let next = cur.next!;
    if (next.count !== cur.count + 1) next = this.insertAfter(cur, cur.count + 1);
    next.keys.add(key);
    this.nodeOf.set(key, next);
    if (cur !== this.head) {
      cur.keys.delete(key);
      if (cur.keys.size === 0) this.unlink(cur);
    }
  }
  dec(key: string): void {
    const cur = this.nodeOf.get(key);
    if (!cur) return;
    if (cur.count === 1) {
      this.nodeOf.delete(key);
    } else {
      let prev = cur.prev!;
      if (prev.count !== cur.count - 1) prev = this.insertAfter(prev, cur.count - 1);
      prev.keys.add(key);
      this.nodeOf.set(key, prev);
    }
    cur.keys.delete(key);
    if (cur.keys.size === 0) this.unlink(cur);
  }
  getMaxKey(): string {
    const b = this.tail.prev!;
    return b === this.head ? '' : (b.keys.values().next().value as string);
  }
  getMinKey(): string {
    const b = this.head.next!;
    return b === this.tail ? '' : (b.keys.values().next().value as string);
  }
}

class AllOne {
    unordered_map<string, int> slotOf;
    vector<set<string>> members;
    vector<long long> cnt;
    vector<int> prv;
    vector<int> nxt;
    vector<int> freeSlots;
    int head, tail;
    int alloc(long long count) {
        int s;
        if (!freeSlots.empty()) { s = freeSlots.back(); freeSlots.pop_back(); }
        else { s = cnt.size(); cnt.push_back(0); members.emplace_back(); nxt.push_back(-1); prv.push_back(-1); }
        cnt[s] = count;
        members[s].clear();
        nxt[s] = -1;
        prv[s] = -1;
        return s;
    }
    void linkAfter(int s, int after) {
        nxt[s] = nxt[after];
        prv[s] = after;
        prv[nxt[after]] = s;
        nxt[after] = s;
    }
    void release(int s) {
        nxt[prv[s]] = nxt[s];
        prv[nxt[s]] = prv[s];
        freeSlots.push_back(s);
    }
public:
    AllOne() {
        head = alloc(0);
        tail = alloc(LLONG_MAX);
        nxt[head] = tail;
        prv[tail] = head;
    }
    void inc(string key) {
        auto it = slotOf.find(key);
        int cur = it == slotOf.end() ? head : it->second;
        int next = nxt[cur];
        if (cnt[next] != cnt[cur] + 1) {
            next = alloc(cnt[cur] + 1);
            linkAfter(next, cur);
        }
        members[next].insert(key);
        slotOf[key] = next;
        if (cur != head) {
            members[cur].erase(key);
            if (members[cur].empty()) release(cur);
        }
    }
    void dec(string key) {
        auto it = slotOf.find(key);
        int cur = it == slotOf.end() ? -1 : it->second;
        if (cur == -1) return;
        if (cnt[cur] == 1) {
            slotOf.erase(key);
        } else {
            int prev = prv[cur];
            if (cnt[prev] != cnt[cur] - 1) {
                prev = alloc(cnt[cur] - 1);
                linkAfter(prev, prv[cur]);
            }
            members[prev].insert(key);
            slotOf[key] = prev;
        }
        members[cur].erase(key);
        if (members[cur].empty()) release(cur);
    }
    string getMaxKey() {
        int b = prv[tail];
        return b == head ? "" : *members[b].begin();
    }
    string getMinKey() {
        int b = nxt[head];
        return b == tail ? "" : *members[b].begin();
    }
};

class AllOne {
    private Map<String, Integer> slotOf = new HashMap<>();
    private List<LinkedHashSet<String>> members = new ArrayList<>();
    private List<Long> cnt = new ArrayList<>();
    private List<Integer> prv = new ArrayList<>();
    private List<Integer> nxt = new ArrayList<>();
    private ArrayDeque<Integer> free = new ArrayDeque<>();
    private final int head, tail;
    public AllOne() {
        head = alloc(0);
        tail = alloc(Long.MAX_VALUE);
        nxt.set(head, tail);
        prv.set(tail, head);
    }
    private int alloc(long count) {
        int s;
        if (!free.isEmpty()) { s = free.pop(); }
        else { s = cnt.size(); cnt.add(0L); members.add(new LinkedHashSet<>()); nxt.add(-1); prv.add(-1); }
        cnt.set(s, count);
        members.get(s).clear();
        nxt.set(s, -1);
        prv.set(s, -1);
        return s;
    }
    private void linkAfter(int s, int after) {
        nxt.set(s, nxt.get(after));
        prv.set(s, after);
        prv.set(nxt.get(after), s);
        nxt.set(after, s);
    }
    private void release(int s) {
        nxt.set(prv.get(s), nxt.get(s));
        prv.set(nxt.get(s), prv.get(s));
        free.push(s);
    }
    public void inc(String key) {
        int cur = slotOf.getOrDefault(key, head);
        int next = nxt.get(cur);
        if (cnt.get(next) != cnt.get(cur) + 1) {
            next = alloc(cnt.get(cur) + 1);
            linkAfter(next, cur);
        }
        members.get(next).add(key);
        slotOf.put(key, next);
        if (cur != head) {
            members.get(cur).remove(key);
            if (members.get(cur).isEmpty()) release(cur);
        }
    }
    public void dec(String key) {
        Integer curBox = slotOf.get(key);
        if (curBox == null) return;
        int cur = curBox;
        if (cnt.get(cur) == 1) {
            slotOf.remove(key);
        } else {
            int prev = prv.get(cur);
            if (cnt.get(prev) != cnt.get(cur) - 1) {
                prev = alloc(cnt.get(cur) - 1);
                linkAfter(prev, prv.get(cur));
            }
            members.get(prev).add(key);
            slotOf.put(key, prev);
        }
        members.get(cur).remove(key);
        if (members.get(cur).isEmpty()) release(cur);
    }
    public String getMaxKey() {
        int b = prv.get(tail);
        return b == head ? "" : members.get(b).iterator().next();
    }
    public String getMinKey() {
        int b = nxt.get(head);
        return b == tail ? "" : members.get(b).iterator().next();
    }
}

class AllOne:
    def __init__(self):
        self.slot_of = {}
        self.members = []
        self.cnt = []
        self.prv = []
        self.nxt = []
        self.free = []
        self.head = self._alloc(0)
        self.tail = self._alloc(float('inf'))
        self.nxt[self.head] = self.tail
        self.prv[self.tail] = self.head
    def _alloc(self, count):
        if self.free:
            s = self.free.pop()
        else:
            s = len(self.cnt)
            self.cnt.append(0); self.members.append({}); self.nxt.append(-1); self.prv.append(-1)
        self.cnt[s] = count
        self.members[s] = {}
        self.nxt[s] = -1
        self.prv[s] = -1
        return s
    def _link_after(self, s, after):
        self.nxt[s] = self.nxt[after]
        self.prv[s] = after
        self.prv[self.nxt[after]] = s
        self.nxt[after] = s
    def _release(self, s):
        self.nxt[self.prv[s]] = self.nxt[s]
        self.prv[self.nxt[s]] = self.prv[s]
        self.free.append(s)
    def inc(self, key):
        cur = self.slot_of.get(key, self.head)
        nxt = self.nxt[cur]
        if self.cnt[nxt] != self.cnt[cur] + 1:
            nxt = self._alloc(self.cnt[cur] + 1)
            self._link_after(nxt, cur)
        self.members[nxt][key] = None
        self.slot_of[key] = nxt
        if cur != self.head:
            del self.members[cur][key]
            if not self.members[cur]: self._release(cur)
    def dec(self, key):
        cur = self.slot_of.get(key)
        if cur is None: return
        if self.cnt[cur] == 1:
            del self.slot_of[key]
        else:
            prev = self.prv[cur]
            if self.cnt[prev] != self.cnt[cur] - 1:
                prev = self._alloc(self.cnt[cur] - 1)
                self._link_after(prev, self.prv[cur])
            self.members[prev][key] = None
            self.slot_of[key] = prev
        del self.members[cur][key]
        if not self.members[cur]: self._release(cur)
    def getMaxKey(self):
        b = self.prv[self.tail]
        return '' if b == self.head else next(iter(self.members[b]))
    def getMinKey(self):
        b = self.nxt[self.head]
        return '' if b == self.tail else next(iter(self.members[b]))

class AllOne {
  private slotOf = new Map<string, number>();
  private members: Set<string>[] = [];
  private cnt: number[] = [];
  private prv: number[] = [];
  private nxt: number[] = [];
  private free: number[] = [];
  private readonly head: number;
  private readonly tail: number;
  constructor() {
    this.head = this.alloc(0);
    this.tail = this.alloc(Number.MAX_SAFE_INTEGER);
    this.nxt[this.head] = this.tail;
    this.prv[this.tail] = this.head;
  }
  private alloc(count: number): number {
    const s = this.free.length > 0 ? this.free.pop()! : this.cnt.length;
    this.cnt[s] = count;
    this.members[s] = new Set<string>();
    this.nxt[s] = -1;
    this.prv[s] = -1;
    return s;
  }
  private linkAfter(s: number, after: number): void {
    this.nxt[s] = this.nxt[after];
    this.prv[s] = after;
    this.prv[this.nxt[after]] = s;
    this.nxt[after] = s;
  }
  private release(s: number): void {
    this.nxt[this.prv[s]] = this.nxt[s];
    this.prv[this.nxt[s]] = this.prv[s];
    this.free.push(s);
  }
  inc(key: string): void {
    const cur = this.slotOf.get(key) ?? this.head;
    let next = this.nxt[cur];
    if (this.cnt[next] !== this.cnt[cur] + 1) {
      next = this.alloc(this.cnt[cur] + 1);
      this.linkAfter(next, cur);
    }
    this.members[next].add(key);
    this.slotOf.set(key, next);
    if (cur !== this.head) {
      this.members[cur].delete(key);
      if (this.members[cur].size === 0) this.release(cur);
    }
  }
  dec(key: string): void {
    const cur = this.slotOf.get(key);
    if (cur === undefined) return;
    if (this.cnt[cur] === 1) {
      this.slotOf.delete(key);
    } else {
      let prev = this.prv[cur];
      if (this.cnt[prev] !== this.cnt[cur] - 1) {
        prev = this.alloc(this.cnt[cur] - 1);
        this.linkAfter(prev, this.prv[cur]);
      }
      this.members[prev].add(key);
      this.slotOf.set(key, prev);
    }
    this.members[cur].delete(key);
    if (this.members[cur].size === 0) this.release(cur);
  }
  getMaxKey(): string {
    const b = this.prv[this.tail];
    return b === this.head ? '' : (this.members[b].values().next().value as string);
  }
  getMinKey(): string {
    const b = this.nxt[this.head];
    return b === this.tail ? '' : (this.members[b].values().next().value as string);
  }
}