import heapq
import bisect
from typing import Optional, List

class Bank:
    DAY_MS = 24 * 60 * 60 * 1000

    def __init__(self):
        self.accounts = {}
        self.payments = {}
        self.payment_counter = 0
        self.cashback_heap = []
        self.merged_to = {}

    def _resolve_account(self, aid):
        while aid in self.merged_to:
            aid = self.merged_to[aid]
        return aid

    def _flush_cashback(self, ts):
        while self.cashback_heap and self.cashback_heap[0][0] <= ts:
            refund_ts, pid = heapq.heappop(self.cashback_heap)
            pay = self.payments[pid]
            if pay["status"] == "CASHBACK_RECEIVED": continue
            aid = self._resolve_account(pay["account"])
            if aid not in self.accounts: continue
            refund = pay["amount"] // 50
            acc = self.accounts[aid]
            acc["balance"] += refund
            acc["history"].append((refund_ts, acc["balance"]))
            pay["status"] = "CASHBACK_RECEIVED"

    def createAccount(self, ts, aid) -> bool:
        self._flush_cashback(ts)
        if aid in self.accounts: return False
        self.accounts[aid] = {"balance": 0, "outgoing": 0, "history": [(ts, 0)]}
        return True

    def deposit(self, ts, aid, amount) -> Optional[int]:
        self._flush_cashback(ts)
        aid = self._resolve_account(aid)
        if aid not in self.accounts: return None
        acc = self.accounts[aid]
        acc["balance"] += amount
        acc["history"].append((ts, acc["balance"]))
        return acc["balance"]

    def transfer(self, ts, src, dst, amount) -> Optional[int]:
        self._flush_cashback(ts)
        src = self._resolve_account(src); dst = self._resolve_account(dst)
        if src == dst or src not in self.accounts or dst not in self.accounts: return None
        sa = self.accounts[src]
        if sa["balance"] < amount: return None
        sa["balance"] -= amount; sa["outgoing"] += amount
        self.accounts[dst]["balance"] += amount
        sa["history"].append((ts, sa["balance"]))
        self.accounts[dst]["history"].append((ts, self.accounts[dst]["balance"]))
        return sa["balance"]

    def topSpenders(self, ts, n) -> List[str]:
        self._flush_cashback(ts)
        items = sorted(
            ((aid, acc["outgoing"]) for aid, acc in self.accounts.items()),
            key=lambda x: (-x[1], x[0])
        )
        return [f"{aid}({amt})" for aid, amt in items[:n]]

    def pay(self, ts, aid, amount) -> Optional[str]:
        self._flush_cashback(ts)
        aid = self._resolve_account(aid)
        if aid not in self.accounts: return None
        acc = self.accounts[aid]
        if acc["balance"] < amount: return None
        acc["balance"] -= amount; acc["outgoing"] += amount
        acc["history"].append((ts, acc["balance"]))
        self.payment_counter += 1
        pid = f"payment{self.payment_counter}"
        cashback_ts = ts + self.DAY_MS
        self.payments[pid] = {"account": aid, "amount": amount, "cashback_ts": cashback_ts, "status": "IN_PROGRESS"}
        heapq.heappush(self.cashback_heap, (cashback_ts, pid))
        return pid

    def getPaymentStatus(self, ts, aid, pid) -> Optional[str]:
        self._flush_cashback(ts)
        aid = self._resolve_account(aid)
        if aid not in self.accounts or pid not in self.payments: return None
        if self._resolve_account(self.payments[pid]["account"]) != aid: return None
        return self.payments[pid]["status"]

    def mergeAccounts(self, ts, a1, a2) -> bool:
        self._flush_cashback(ts)
        a1 = self._resolve_account(a1); a2 = self._resolve_account(a2)
        if a1 == a2 or a1 not in self.accounts or a2 not in self.accounts: return False
        acc1 = self.accounts[a1]; acc2 = self.accounts[a2]
        acc1["balance"] += acc2["balance"]
        acc1["outgoing"] += acc2["outgoing"]
        merged_hist = sorted(acc1["history"] + acc2["history"], key=lambda x: x[0])
        clean = []
        for tts, bal in merged_hist:
            if clean and clean[-1][0] == tts:
                clean[-1] = (tts, bal)
            else:
                clean.append((tts, bal))
        acc1["history"] = clean
        acc1["history"].append((ts, acc1["balance"]))
        self.merged_to[a2] = a1
        del self.accounts[a2]
        return True

    def getBalance(self, ts, aid, time_at) -> Optional[int]:
        self._flush_cashback(ts)
        aid = self._resolve_account(aid)
        if aid not in self.accounts: return None
        hist = self.accounts[aid]["history"]
        keys = [h[0] for h in hist]
        idx = bisect.bisect_right(keys, time_at) - 1
        if idx < 0: return None
        return hist[idx][1]

import java.util.*;

class Bank {
    static final long DAY_MS = 24L * 60 * 60 * 1000;

    static class Account {
        long balance = 0, outgoing = 0;
        List<long[]> history = new ArrayList<>(); // (ts, balance)
    }

    static class Payment {
        String account; long amount; long cashbackTs; String status; // "IN_PROGRESS" / "CASHBACK_RECEIVED"
    }

    Map<String, Account> accounts = new HashMap<>();
    Map<String, Payment> payments = new HashMap<>();
    Map<String, String> mergedTo = new HashMap<>();
    PriorityQueue<long[]> cashbackHeap = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
    Map<Long, String> heapPid = new HashMap<>(); // simple: store pid via cashbackHeap entry's second field
    int paymentCounter = 0;

    String resolve(String aid) {
        while (mergedTo.containsKey(aid)) aid = mergedTo.get(aid);
        return aid;
    }

    void flushCashback(long ts) {
        while (!cashbackHeap.isEmpty() && cashbackHeap.peek()[0] <= ts) {
            long[] top = cashbackHeap.poll();
            long refundTs = top[0];
            String pid = "payment" + top[1];
            Payment pay = payments.get(pid);
            if (pay == null || "CASHBACK_RECEIVED".equals(pay.status)) continue;
            String aid = resolve(pay.account);
            Account acc = accounts.get(aid);
            if (acc == null) continue;
            long refund = pay.amount / 50;
            acc.balance += refund;
            acc.history.add(new long[]{refundTs, acc.balance});
            pay.status = "CASHBACK_RECEIVED";
        }
    }

    public boolean createAccount(long ts, String aid) {
        flushCashback(ts);
        if (accounts.containsKey(aid)) return false;
        Account a = new Account();
        a.history.add(new long[]{ts, 0});
        accounts.put(aid, a);
        return true;
    }

    public Optional<Long> deposit(long ts, String aid, long amount) {
        flushCashback(ts);
        aid = resolve(aid);
        Account a = accounts.get(aid);
        if (a == null) return Optional.empty();
        a.balance += amount;
        a.history.add(new long[]{ts, a.balance});
        return Optional.of(a.balance);
    }

    public Optional<Long> transfer(long ts, String src, String dst, long amount) {
        flushCashback(ts);
        src = resolve(src); dst = resolve(dst);
        if (src.equals(dst)) return Optional.empty();
        Account sa = accounts.get(src), da = accounts.get(dst);
        if (sa == null || da == null || sa.balance < amount) return Optional.empty();
        sa.balance -= amount; sa.outgoing += amount;
        da.balance += amount;
        sa.history.add(new long[]{ts, sa.balance});
        da.history.add(new long[]{ts, da.balance});
        return Optional.of(sa.balance);
    }

    public List<String> topSpenders(long ts, int n) {
        flushCashback(ts);
        List<Map.Entry<String, Account>> list = new ArrayList<>(accounts.entrySet());
        list.sort((x, y) -> {
            if (x.getValue().outgoing != y.getValue().outgoing) return Long.compare(y.getValue().outgoing, x.getValue().outgoing);
            return x.getKey().compareTo(y.getKey());
        });
        List<String> out = new ArrayList<>();
        for (int i = 0; i < Math.min(n, list.size()); i++)
            out.add(list.get(i).getKey() + "(" + list.get(i).getValue().outgoing + ")");
        return out;
    }

    public Optional<String> pay(long ts, String aid, long amount) {
        flushCashback(ts);
        aid = resolve(aid);
        Account a = accounts.get(aid);
        if (a == null || a.balance < amount) return Optional.empty();
        a.balance -= amount; a.outgoing += amount;
        a.history.add(new long[]{ts, a.balance});
        paymentCounter++;
        String pid = "payment" + paymentCounter;
        Payment p = new Payment();
        p.account = aid; p.amount = amount; p.cashbackTs = ts + DAY_MS; p.status = "IN_PROGRESS";
        payments.put(pid, p);
        cashbackHeap.offer(new long[]{p.cashbackTs, paymentCounter});
        return Optional.of(pid);
    }

    public Optional<String> getPaymentStatus(long ts, String aid, String pid) {
        flushCashback(ts);
        aid = resolve(aid);
        if (!accounts.containsKey(aid)) return Optional.empty();
        Payment p = payments.get(pid);
        if (p == null) return Optional.empty();
        if (!resolve(p.account).equals(aid)) return Optional.empty();
        return Optional.of(p.status);
    }

    public boolean mergeAccounts(long ts, String a1, String a2) {
        flushCashback(ts);
        a1 = resolve(a1); a2 = resolve(a2);
        if (a1.equals(a2)) return false;
        Account x = accounts.get(a1), y = accounts.get(a2);
        if (x == null || y == null) return false;
        x.balance += y.balance;
        x.outgoing += y.outgoing;
        List<long[]> merged = new ArrayList<>(x.history.size() + y.history.size());
        merged.addAll(x.history); merged.addAll(y.history);
        merged.sort((p, q) -> Long.compare(p[0], q[0]));
        List<long[]> clean = new ArrayList<>();
        for (long[] h : merged) {
            if (!clean.isEmpty() && clean.get(clean.size() - 1)[0] == h[0]) clean.set(clean.size() - 1, h);
            else clean.add(h);
        }
        clean.add(new long[]{ts, x.balance});
        x.history = clean;
        mergedTo.put(a2, a1);
        accounts.remove(a2);
        return true;
    }

    public Optional<Long> getBalance(long ts, String aid, long timeAt) {
        flushCashback(ts);
        aid = resolve(aid);
        Account a = accounts.get(aid);
        if (a == null) return Optional.empty();
        int lo = 0, hi = a.history.size();
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (a.history.get(mid)[0] <= timeAt) lo = mid + 1; else hi = mid;
        }
        if (lo == 0) return Optional.empty();
        return Optional.of(a.history.get(lo - 1)[1]);
    }
}

#include <bits/stdc++.h>
using namespace std;

class Bank {
    static constexpr long long DAY_MS = 24LL * 60 * 60 * 1000;

    struct Account {
        long long balance = 0, outgoing = 0;
        vector<pair<long long, long long>> history; // (ts, balance)
    };
    struct Payment {
        string account; long long amount, cashbackTs; string status;
    };

    unordered_map<string, Account> accounts;
    unordered_map<string, Payment> payments;
    unordered_map<string, string> mergedTo;
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> cashbackHeap;
    int paymentCounter = 0;

    string resolve(string aid) {
        while (mergedTo.count(aid)) aid = mergedTo[aid];
        return aid;
    }

    void flushCashback(long long ts) {
        while (!cashbackHeap.empty() && cashbackHeap.top().first <= ts) {
            auto [refundTs, n] = cashbackHeap.top(); cashbackHeap.pop();
            string pid = "payment" + to_string(n);
            auto it = payments.find(pid);
            if (it == payments.end() || it->second.status == "CASHBACK_RECEIVED") continue;
            string aid = resolve(it->second.account);
            auto ait = accounts.find(aid);
            if (ait == accounts.end()) continue;
            long long refund = it->second.amount / 50;
            ait->second.balance += refund;
            ait->second.history.push_back({refundTs, ait->second.balance});
            it->second.status = "CASHBACK_RECEIVED";
        }
    }

public:
    bool createAccount(long long ts, string aid) {
        flushCashback(ts);
        if (accounts.count(aid)) return false;
        Account a; a.history.push_back({ts, 0});
        accounts[aid] = move(a);
        return true;
    }

    optional<long long> deposit(long long ts, string aid, long long amount) {
        flushCashback(ts);
        aid = resolve(aid);
        auto it = accounts.find(aid);
        if (it == accounts.end()) return nullopt;
        it->second.balance += amount;
        it->second.history.push_back({ts, it->second.balance});
        return it->second.balance;
    }

    optional<long long> transfer(long long ts, string src, string dst, long long amount) {
        flushCashback(ts);
        src = resolve(src); dst = resolve(dst);
        if (src == dst) return nullopt;
        auto si = accounts.find(src), di = accounts.find(dst);
        if (si == accounts.end() || di == accounts.end() || si->second.balance < amount) return nullopt;
        si->second.balance -= amount; si->second.outgoing += amount;
        di->second.balance += amount;
        si->second.history.push_back({ts, si->second.balance});
        di->second.history.push_back({ts, di->second.balance});
        return si->second.balance;
    }

    vector<string> topSpenders(long long ts, int n) {
        flushCashback(ts);
        vector<pair<string, long long>> v;
        for (auto& [k, a] : accounts) v.push_back({k, a.outgoing});
        sort(v.begin(), v.end(), [](auto& a, auto& b) {
            if (a.second != b.second) return a.second > b.second;
            return a.first < b.first;
        });
        vector<string> out;
        for (int i = 0; i < min((int)v.size(), n); i++)
            out.push_back(v[i].first + "(" + to_string(v[i].second) + ")");
        return out;
    }

    optional<string> pay(long long ts, string aid, long long amount) {
        flushCashback(ts);
        aid = resolve(aid);
        auto it = accounts.find(aid);
        if (it == accounts.end() || it->second.balance < amount) return nullopt;
        it->second.balance -= amount; it->second.outgoing += amount;
        it->second.history.push_back({ts, it->second.balance});
        paymentCounter++;
        string pid = "payment" + to_string(paymentCounter);
        Payment p{aid, amount, ts + DAY_MS, "IN_PROGRESS"};
        payments[pid] = p;
        cashbackHeap.push({p.cashbackTs, paymentCounter});
        return pid;
    }

    optional<string> getPaymentStatus(long long ts, string aid, string pid) {
        flushCashback(ts);
        aid = resolve(aid);
        if (!accounts.count(aid)) return nullopt;
        auto it = payments.find(pid);
        if (it == payments.end()) return nullopt;
        if (resolve(it->second.account) != aid) return nullopt;
        return it->second.status;
    }

    bool mergeAccounts(long long ts, string a1, string a2) {
        flushCashback(ts);
        a1 = resolve(a1); a2 = resolve(a2);
        if (a1 == a2) return false;
        auto xi = accounts.find(a1), yi = accounts.find(a2);
        if (xi == accounts.end() || yi == accounts.end()) return false;
        xi->second.balance += yi->second.balance;
        xi->second.outgoing += yi->second.outgoing;
        vector<pair<long long, long long>> merged = xi->second.history;
        merged.insert(merged.end(), yi->second.history.begin(), yi->second.history.end());
        sort(merged.begin(), merged.end(), [](auto& a, auto& b) { return a.first < b.first; });
        vector<pair<long long, long long>> clean;
        for (auto& h : merged) {
            if (!clean.empty() && clean.back().first == h.first) clean.back() = h;
            else clean.push_back(h);
        }
        clean.push_back({ts, xi->second.balance});
        xi->second.history = clean;
        mergedTo[a2] = a1;
        accounts.erase(yi);
        return true;
    }

    optional<long long> getBalance(long long ts, string aid, long long timeAt) {
        flushCashback(ts);
        aid = resolve(aid);
        auto it = accounts.find(aid);
        if (it == accounts.end()) return nullopt;
        auto& h = it->second.history;
        int lo = 0, hi = h.size();
        while (lo < hi) {
            int mid = (lo + hi) >> 1;
            if (h[mid].first <= timeAt) lo = mid + 1; else hi = mid;
        }
        if (lo == 0) return nullopt;
        return h[lo - 1].second;
    }
};

from typing import List

def caught_fish(fishing: List[int], baitsss: List[int]) -> int:
    fish = sorted(fishing, reverse=True)
    baits = sorted(baitsss, reverse=True)
    count = 0
    i = 0
    for b in baits:
        used = 0
        while i < len(fish) and used < 3 and fish[i] > b:
            i += 1
            used += 1
            count += 1
    return count

import java.util.*;

class Solution {
    int caughtFish(int[] fishing, int[] baitsss) {
        Integer[] fish = Arrays.stream(fishing).boxed().toArray(Integer[]::new);
        Integer[] baits = Arrays.stream(baitsss).boxed().toArray(Integer[]::new);
        Arrays.sort(fish, Collections.reverseOrder());
        Arrays.sort(baits, Collections.reverseOrder());
        int count = 0, i = 0;
        for (int b : baits) {
            int used = 0;
            while (i < fish.length && used < 3 && fish[i] > b) { i++; used++; count++; }
        }
        return count;
    }
}

class Solution {
public:
    int caughtFish(vector<int>& fishing, vector<int>& baitsss) {
        vector<int> fish = fishing, baits = baitsss;
        sort(fish.begin(), fish.end(), greater<int>());
        sort(baits.begin(), baits.end(), greater<int>());
        int count = 0, i = 0;
        for (int b : baits) {
            int used = 0;
            while (i < (int) fish.size() && used < 3 && fish[i] > b) { i++; used++; count++; }
        }
        return count;
    }
};

from typing import List

def coder_writing(records: List[str]) -> str:
    totals = {}
    for r in records:
        name, grade = r.split(":")
        name = name.strip(); g = int(grade.strip())
        s, c = totals.get(name, (0, 0))
        totals[name] = (s + g, c + 1)
    best_name = ""
    best_avg = -float("inf")
    for name, (s, c) in totals.items():
        avg = s / c
        if avg > best_avg:
            best_avg = avg
            best_name = name
    return best_name

import java.util.*;

class Solution {
    String coderWriting(String[] records) {
        Map<String, double[]> totals = new HashMap<>();
        for (String r : records) {
            String[] p = r.split(":");
            String name = p[0].trim();
            double g = Double.parseDouble(p[1].trim());
            double[] arr = totals.getOrDefault(name, new double[]{0, 0});
            arr[0] += g; arr[1]++;
            totals.put(name, arr);
        }
        String best = "";
        double bestAvg = -Double.MAX_VALUE;
        for (var e : totals.entrySet()) {
            double avg = e.getValue()[0] / e.getValue()[1];
            if (avg > bestAvg) { bestAvg = avg; best = e.getKey(); }
        }
        return best;
    }
}

class Solution {
public:
    string coderWriting(vector<string>& records) {
        unordered_map<string, pair<double, int>> totals;
        for (auto& r : records) {
            auto sp = r.find(':');
            string name = r.substr(0, sp);
            while (!name.empty() && name.back() == ' ') name.pop_back();
            double g = stod(r.substr(sp + 1));
            auto& a = totals[name];
            a.first += g; a.second++;
        }
        string best;
        double bestAvg = -1e18;
        for (auto& [name, p] : totals) {
            double avg = p.first / p.second;
            if (avg > bestAvg) { bestAvg = avg; best = name; }
        }
        return best;
    }
};