// runnable
import java.time.*;
import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.function.Supplier;

enum SeatStatus { AVAILABLE, HELD, BOOKED }

class SeatUnavailableException extends RuntimeException {
    SeatUnavailableException(String msg) { super(msg); }
}

class Seat {
    final String id;
    SeatStatus status = SeatStatus.AVAILABLE;
    String holdId;
    Instant holdExpiresAt;
    Seat(String id) { this.id = id; }
}

record Hold(String id, String userId, List<String> seatIds, Instant expiresAt) {}
record Booking(String id, String userId, String showId, List<String> seatIds, long amountCents) {}

class Show {
    private final String id;
    private final long priceCents;
    private final Duration holdTtl;
    private final Supplier<Instant> clock;
    private final Map<String, Seat> seats = new LinkedHashMap<>();
    private final Map<String, Hold> holds = new HashMap<>();
    private final AtomicInteger holdCounter = new AtomicInteger(1);

    Show(String id, int rows, int cols, long priceCents, Duration holdTtl, Supplier<Instant> clock) {
        this.id = id; this.priceCents = priceCents; this.holdTtl = holdTtl; this.clock = clock;
        for (int r = 0; r < rows; r++)
            for (int c = 1; c <= cols; c++) {
                String sid = "" + (char) ('A' + r) + c;
                seats.put(sid, new Seat(sid));
            }
    }

    String id() { return id; }
    long priceCents() { return priceCents; }

    private boolean isFree(Seat s) {
        return s.status == SeatStatus.AVAILABLE
            || (s.status == SeatStatus.HELD && !clock.get().isBefore(s.holdExpiresAt));
    }

    synchronized Hold hold(String userId, List<String> seatIds) {
        for (String sid : seatIds) {                                   // check everything first: all or nothing
            Seat s = seats.get(sid);
            if (s == null) throw new IllegalArgumentException("no such seat " + sid);
            if (!isFree(s)) throw new SeatUnavailableException("seat " + sid + " is not available");
        }
        Instant expires = clock.get().plus(holdTtl);
        Hold h = new Hold("H" + holdCounter.getAndIncrement(), userId, List.copyOf(seatIds), expires);
        for (String sid : seatIds) {
            Seat s = seats.get(sid);
            s.status = SeatStatus.HELD; s.holdId = h.id(); s.holdExpiresAt = expires;
        }
        holds.put(h.id(), h);
        return h;
    }

    synchronized void confirm(Hold h) {
        Hold current = holds.get(h.id());
        if (current == null) throw new IllegalStateException("hold not found or already released");
        if (!clock.get().isBefore(current.expiresAt())) {
            release(h);
            throw new IllegalStateException("hold expired");
        }
        for (String sid : current.seatIds()) {
            Seat s = seats.get(sid);
            s.status = SeatStatus.BOOKED; s.holdId = null; s.holdExpiresAt = null;
        }
        holds.remove(h.id());
    }

    synchronized void release(Hold h) {
        Hold current = holds.remove(h.id());
        if (current == null) return;
        for (String sid : current.seatIds()) {
            Seat s = seats.get(sid);
            if (s.status == SeatStatus.HELD && h.id().equals(s.holdId)) {     // do not free seats re-held by someone else
                s.status = SeatStatus.AVAILABLE; s.holdId = null; s.holdExpiresAt = null;
            }
        }
    }

    synchronized List<String> availableSeats() {
        return seats.values().stream().filter(this::isFree).map(s -> s.id).toList();
    }
}

interface PaymentGateway {
    boolean charge(String userId, long cents);
}

class BookingService {
    private final Map<String, Show> shows = new HashMap<>();
    private final PaymentGateway payments;
    private final AtomicInteger bookingCounter = new AtomicInteger(1);

    BookingService(PaymentGateway payments) { this.payments = payments; }
    void addShow(Show s) { shows.put(s.id(), s); }

    Booking book(String userId, String showId, List<String> seatIds) {
        Show show = shows.get(showId);
        if (show == null) throw new IllegalArgumentException("no such show " + showId);
        Hold hold = show.hold(userId, seatIds);
        long amount = show.priceCents() * seatIds.size();
        boolean paid;
        try {
            paid = payments.charge(userId, amount);
        } catch (RuntimeException e) {
            show.release(hold);
            throw e;
        }
        if (!paid) {
            show.release(hold);
            throw new IllegalStateException("payment declined");
        }
        show.confirm(hold);       // a real system would refund here if the hold had lapsed
        return new Booking("BK" + bookingCounter.getAndIncrement(), userId, showId, seatIds, amount);
    }
}

public class Main {
    public static void main(String[] args) {
        Instant[] now = { Instant.parse("2026-03-01T18:00:00Z") };
        Show show = new Show("S1", 2, 3, 250, Duration.ofMinutes(5), () -> now[0]);
        BookingService svc = new BookingService((user, cents) -> !user.equals("poor"));
        svc.addShow(show);

        Booking b = svc.book("u1", "S1", List.of("A1", "A2"));
        System.out.println("u1 booked " + b.seatIds() + " for " + b.amountCents());

        try { svc.book("u2", "S1", List.of("A2", "A3")); }
        catch (SeatUnavailableException e) { System.out.println("u2 failed: " + e.getMessage()); }
        System.out.println("available: " + show.availableSeats());               // A3 untouched: all or nothing

        try { svc.book("poor", "S1", List.of("B1")); }
        catch (IllegalStateException e) { System.out.println("poor failed: " + e.getMessage()); }
        System.out.println("available: " + show.availableSeats());               // B1 released

        Hold h3 = show.hold("u3", List.of("B1"));
        try { show.hold("u4", List.of("B1")); }
        catch (SeatUnavailableException e) { System.out.println("u4 blocked while u3 holds B1"); }
        now[0] = now[0].plus(Duration.ofMinutes(6));                              // u3's hold expires
        show.hold("u4", List.of("B1"));
        System.out.println("u4 got B1 after expiry");
        try { show.confirm(h3); }
        catch (IllegalStateException e) { System.out.println("u3 confirm failed: " + e.getMessage()); }
    }
}

// runnable
import java.util.*;

interface SplitStrategy {
    /** Returns each participant's share in cents. Shares add up to the total. */
    Map<String, Long> split(long totalCents, List<String> participants, List<Long> values);
}

class EqualSplit implements SplitStrategy {
    public Map<String, Long> split(long total, List<String> ps, List<Long> values) {
        Map<String, Long> out = new LinkedHashMap<>();
        long base = total / ps.size(), rem = total % ps.size();
        for (int i = 0; i < ps.size(); i++) out.put(ps.get(i), base + (i < rem ? 1 : 0));
        return out;
    }
}

class ExactSplit implements SplitStrategy {
    public Map<String, Long> split(long total, List<String> ps, List<Long> values) {
        if (values.size() != ps.size()) throw new IllegalArgumentException("one amount per participant");
        long sum = values.stream().mapToLong(Long::longValue).sum();
        if (sum != total) throw new IllegalArgumentException("amounts add up to " + sum + ", expected " + total);
        Map<String, Long> out = new LinkedHashMap<>();
        for (int i = 0; i < ps.size(); i++) out.put(ps.get(i), values.get(i));
        return out;
    }
}

class PercentSplit implements SplitStrategy {
    public Map<String, Long> split(long total, List<String> ps, List<Long> values) {
        if (values.size() != ps.size()) throw new IllegalArgumentException("one percentage per participant");
        if (values.stream().mapToLong(Long::longValue).sum() != 100) throw new IllegalArgumentException("percentages must add up to 100");
        Map<String, Long> out = new LinkedHashMap<>();
        long assigned = 0;
        for (int i = 0; i < ps.size(); i++) {
            long share = total * values.get(i) / 100;
            out.put(ps.get(i), share);
            assigned += share;
        }
        long leftover = total - assigned;                             // rounding cents go to the first participants
        for (int i = 0; leftover > 0; i = (i + 1) % ps.size(), leftover--) out.merge(ps.get(i), 1L, Long::sum);
        return out;
    }
}

record Transfer(String from, String to, long cents) {
    @Override public String toString() { return from + " pays " + to + " " + Money.fmt(cents); }
}

class Money {
    static String fmt(long cents) { return String.format("%d.%02d", cents / 100, cents % 100); }
}

class ExpenseService {
    private final Map<String, Map<String, Long>> owes = new TreeMap<>();   // owes.get(a).get(b) = cents a owes b

    void addExpense(String paidBy, long total, SplitStrategy strategy, List<String> participants, List<Long> values) {
        Map<String, Long> shares = strategy.split(total, participants, values);
        long sum = shares.values().stream().mapToLong(Long::longValue).sum();
        if (sum != total) throw new IllegalStateException("shares do not add up to the total");
        shares.forEach((user, share) -> {
            if (!user.equals(paidBy) && share > 0) addDebt(user, paidBy, share);
        });
    }

    private void addDebt(String from, String to, long cents) {
        long reverse = owes.getOrDefault(to, new TreeMap<>()).getOrDefault(from, 0L);
        if (reverse > 0) {                                             // cancel the opposite direction first
            long cancel = Math.min(reverse, cents);
            adjust(to, from, -cancel);
            cents -= cancel;
        }
        if (cents > 0) adjust(from, to, cents);
    }

    private void adjust(String a, String b, long delta) {
        Map<String, Long> m = owes.computeIfAbsent(a, k -> new TreeMap<>());
        long v = m.getOrDefault(b, 0L) + delta;
        if (v == 0) m.remove(b); else m.put(b, v);
    }

    List<String> balances() {
        List<String> out = new ArrayList<>();
        owes.forEach((a, m) -> m.forEach((b, c) -> out.add(a + " owes " + b + " " + Money.fmt(c))));
        return out;
    }

    List<Transfer> simplify() {
        Map<String, Long> net = new TreeMap<>();                       // positive: is owed, negative: owes
        owes.forEach((a, m) -> m.forEach((b, c) -> { net.merge(a, -c, Long::sum); net.merge(b, c, Long::sum); }));

        Comparator<Map.Entry<String, Long>> byAmountDesc = (x, y) -> Long.compare(y.getValue(), x.getValue());
        PriorityQueue<Map.Entry<String, Long>> creditors = new PriorityQueue<>(byAmountDesc);
        PriorityQueue<Map.Entry<String, Long>> debtors = new PriorityQueue<>(byAmountDesc);
        net.forEach((u, v) -> {
            if (v > 0) creditors.add(new AbstractMap.SimpleEntry<>(u, v));
            else if (v < 0) debtors.add(new AbstractMap.SimpleEntry<>(u, -v));
        });

        List<Transfer> out = new ArrayList<>();
        while (!creditors.isEmpty() && !debtors.isEmpty()) {
            var c = creditors.poll();
            var d = debtors.poll();
            long pay = Math.min(c.getValue(), d.getValue());
            out.add(new Transfer(d.getKey(), c.getKey(), pay));
            if (c.getValue() > pay) creditors.add(new AbstractMap.SimpleEntry<>(c.getKey(), c.getValue() - pay));
            if (d.getValue() > pay) debtors.add(new AbstractMap.SimpleEntry<>(d.getKey(), d.getValue() - pay));
        }
        return out;
    }
}

public class Main {
    public static void main(String[] args) {
        System.out.println(new EqualSplit().split(1000, List.of("A", "B", "C"), List.of()));   // {A=334, B=333, C=333}

        ExpenseService svc = new ExpenseService();
        List<String> all = List.of("A", "B", "C", "D");
        svc.addExpense("A", 4000, new EqualSplit(), all, List.of());                                      // A paid 40.00 for everyone
        svc.addExpense("B", 3000, new EqualSplit(), List.of("B", "C", "D"), List.of());                   // B paid 30.00 for B, C, D
        svc.addExpense("D", 600, new ExactSplit(), List.of("A", "C"), List.of(200L, 400L));               // D paid 6.00, A 2.00 and C 4.00

        svc.balances().forEach(System.out::println);
        System.out.println("simplified:");
        svc.simplify().forEach(t -> System.out.println("  " + t));

        try { svc.addExpense("A", 1000, new PercentSplit(), List.of("A", "B"), List.of(60L, 30L)); }
        catch (IllegalArgumentException e) { System.out.println("error: " + e.getMessage()); }
    }
}

// runnable
import java.util.*;
import java.util.concurrent.*;
import java.util.function.Consumer;

record Message(long offset, String topic, String payload) {}

class Topic {
    private final String name;
    private final List<Message> log = new ArrayList<>();
    Topic(String name) { this.name = name; }

    synchronized Message append(String payload) {
        Message m = new Message(log.size(), name, payload);
        log.add(m);
        return m;
    }
    synchronized Optional<Message> at(long offset) {
        return offset < log.size() ? Optional.of(log.get((int) offset)) : Optional.empty();
    }
}

class Subscription {
    private final Topic topic;
    private final Consumer<Message> handler;
    private final int maxAttempts;
    private long offset = 0;                                   // only touched by the single worker thread
    private final ExecutorService worker = Executors.newSingleThreadExecutor();
    final String group;
    final List<Message> deadLetters = new CopyOnWriteArrayList<>();

    Subscription(String group, Topic topic, Consumer<Message> handler, int maxAttempts) {
        this.group = group; this.topic = topic; this.handler = handler; this.maxAttempts = maxAttempts;
    }

    void signal() { worker.submit(this::drain); }

    private void drain() {
        Optional<Message> next;
        while ((next = topic.at(offset)).isPresent()) {
            Message m = next.get();
            boolean ok = false;
            for (int attempt = 1; attempt <= maxAttempts && !ok; attempt++) {
                try { handler.accept(m); ok = true; }
                catch (RuntimeException e) { /* retry, a real broker would back off here */ }
            }
            if (!ok) deadLetters.add(m);
            offset++;                                          // move on even after a dead letter
        }
    }

    void close() throws InterruptedException {
        worker.shutdown();                                     // lets already queued drain tasks finish
        worker.awaitTermination(5, TimeUnit.SECONDS);
    }
}

class Broker {
    private final Map<String, Topic> topics = new ConcurrentHashMap<>();
    private final Map<String, List<Subscription>> subs = new ConcurrentHashMap<>();

    void createTopic(String name) { topics.putIfAbsent(name, new Topic(name)); }

    Subscription subscribe(String topic, String group, Consumer<Message> handler) {
        Topic t = topics.get(topic);
        if (t == null) throw new IllegalArgumentException("no such topic " + topic);
        Subscription s = new Subscription(group, t, handler, 3);      // starts from offset 0, replaying history
        subs.computeIfAbsent(topic, k -> new CopyOnWriteArrayList<>()).add(s);
        s.signal();
        return s;
    }

    void publish(String topic, String payload) {
        Topic t = topics.get(topic);
        if (t == null) throw new IllegalArgumentException("no such topic " + topic);
        t.append(payload);
        subs.getOrDefault(topic, List.of()).forEach(Subscription::signal);
    }

    void shutdown() throws InterruptedException {
        for (List<Subscription> list : subs.values()) for (Subscription s : list) s.close();
    }
}

public class Main {
    public static void main(String[] args) throws InterruptedException {
        List<String> billing = Collections.synchronizedList(new ArrayList<>());
        List<String> email = Collections.synchronizedList(new ArrayList<>());

        Broker broker = new Broker();
        broker.createTopic("orders");
        broker.subscribe("orders", "billing", m -> billing.add(m.payload()));
        Subscription emailSub = broker.subscribe("orders", "email", m -> {
            if (m.payload().equals("bad")) throw new RuntimeException("cannot render template");
            email.add(m.payload());
        });

        for (String p : List.of("o1", "o2", "bad", "o3")) broker.publish("orders", p);
        broker.shutdown();

        System.out.println("billing: " + billing);
        System.out.println("email:   " + email);
        System.out.println("email dead letters: " + emailSub.deadLetters.stream().map(Message::payload).toList());
    }
}

// runnable
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.function.LongSupplier;

interface RateLimiter {
    boolean allow(String key);
}

class FixedWindowLimiter implements RateLimiter {
    private static final class State { long window = -1; int count; }
    private final int limit;
    private final long windowMs;
    private final LongSupplier clock;
    private final Map<String, State> states = new ConcurrentHashMap<>();

    FixedWindowLimiter(int limit, long windowMs, LongSupplier clock) {
        this.limit = limit; this.windowMs = windowMs; this.clock = clock;
    }
    public boolean allow(String key) {
        State s = states.computeIfAbsent(key, k -> new State());
        long window = clock.getAsLong() / windowMs;
        synchronized (s) {
            if (s.window != window) { s.window = window; s.count = 0; }
            if (s.count < limit) { s.count++; return true; }
            return false;
        }
    }
}

class SlidingWindowLogLimiter implements RateLimiter {
    private final int limit;
    private final long windowMs;
    private final LongSupplier clock;
    private final Map<String, ArrayDeque<Long>> logs = new ConcurrentHashMap<>();

    SlidingWindowLogLimiter(int limit, long windowMs, LongSupplier clock) {
        this.limit = limit; this.windowMs = windowMs; this.clock = clock;
    }
    public boolean allow(String key) {
        ArrayDeque<Long> q = logs.computeIfAbsent(key, k -> new ArrayDeque<>());
        long now = clock.getAsLong();
        synchronized (q) {
            while (!q.isEmpty() && q.peekFirst() <= now - windowMs) q.pollFirst();   // forget old requests
            if (q.size() < limit) { q.addLast(now); return true; }
            return false;
        }
    }
}

class TokenBucketLimiter implements RateLimiter {
    private static final class State { double tokens; long last; boolean started; }
    private final int capacity;
    private final double refillPerMs;
    private final LongSupplier clock;
    private final Map<String, State> states = new ConcurrentHashMap<>();

    TokenBucketLimiter(int limit, long windowMs, LongSupplier clock) {
        this.capacity = limit; this.refillPerMs = (double) limit / windowMs; this.clock = clock;
    }
    public boolean allow(String key) {
        State s = states.computeIfAbsent(key, k -> new State());
        long now = clock.getAsLong();
        synchronized (s) {
            if (!s.started) { s.tokens = capacity; s.last = now; s.started = true; }
            s.tokens = Math.min(capacity, s.tokens + (now - s.last) * refillPerMs);
            s.last = now;
            if (s.tokens >= 1) { s.tokens -= 1; return true; }
            return false;
        }
    }
}

enum Algorithm { FIXED_WINDOW, SLIDING_LOG, TOKEN_BUCKET }

record LimitConfig(Algorithm algorithm, int limit, long windowMs) {}

class RateLimiters {
    static RateLimiter create(LimitConfig c, LongSupplier clock) {
        return switch (c.algorithm()) {
            case FIXED_WINDOW -> new FixedWindowLimiter(c.limit(), c.windowMs(), clock);
            case SLIDING_LOG -> new SlidingWindowLogLimiter(c.limit(), c.windowMs(), clock);
            case TOKEN_BUCKET -> new TokenBucketLimiter(c.limit(), c.windowMs(), clock);
        };
    }
}

public class Main {
    /** 3 requests just before a window boundary and 3 just after. */
    static int boundaryBurst(Algorithm algo) {
        long[] t = { 0 };
        RateLimiter rl = RateLimiters.create(new LimitConfig(algo, 3, 1000), () -> t[0]);
        int allowed = 0;
        t[0] = 900;
        for (int i = 0; i < 3; i++) if (rl.allow("u")) allowed++;
        t[0] = 1000;
        for (int i = 0; i < 3; i++) if (rl.allow("u")) allowed++;
        return allowed;
    }

    public static void main(String[] args) {
        System.out.println("allowed across boundary: fixed=" + boundaryBurst(Algorithm.FIXED_WINDOW)
            + " sliding=" + boundaryBurst(Algorithm.SLIDING_LOG)
            + " bucket=" + boundaryBurst(Algorithm.TOKEN_BUCKET));

        long[] t = { 0 };
        RateLimiter rl = RateLimiters.create(new LimitConfig(Algorithm.TOKEN_BUCKET, 2, 1000), () -> t[0]);
        System.out.println("alice: " + rl.allow("alice") + " " + rl.allow("alice") + " " + rl.allow("alice"));   // true true false
        System.out.println("bob:   " + rl.allow("bob"));                                                        // independent key
        t[0] = 500;                                                                                             // half a second refills one token
        System.out.println("alice after 500ms: " + rl.allow("alice"));
    }
}

// runnable
import java.util.*;

interface BankService {
    boolean verifyPin(String card, String pin);
    long balance(String card);
    void debit(String card, long amount);
}

class InMemoryBank implements BankService {
    private final Map<String, String> pins = new HashMap<>();
    private final Map<String, Long> balances = new HashMap<>();
    void addAccount(String card, String pin, long balance) { pins.put(card, pin); balances.put(card, balance); }
    public boolean verifyPin(String card, String pin) { return pin.equals(pins.get(card)); }
    public long balance(String card) { return balances.get(card); }
    public void debit(String card, long amount) {
        if (balances.get(card) < amount) throw new IllegalStateException("insufficient funds");
        balances.merge(card, -amount, Long::sum);
    }
}

/** One link per denomination. Plans without changing any state. */
class NoteHandler {
    private final int denomination;
    private NoteHandler next;
    NoteHandler(int denomination) { this.denomination = denomination; }
    NoteHandler then(NoteHandler n) { this.next = n; return n; }

    boolean plan(long remaining, Map<Integer, Integer> available, Map<Integer, Integer> out) {
        int use = (int) Math.min(remaining / denomination, available.getOrDefault(denomination, 0));
        if (use > 0) out.put(denomination, use);
        long left = remaining - (long) use * denomination;
        if (left == 0) return true;
        return next != null && next.plan(left, available, out);
    }
}

class CashDispenser {
    private final Map<Integer, Integer> notes = new TreeMap<>(Comparator.reverseOrder());
    private final NoteHandler chain;
    private final int smallest;

    CashDispenser(Map<Integer, Integer> initial) {
        notes.putAll(initial);
        NoteHandler head = null, tail = null;
        for (int denom : notes.keySet()) {                           // largest first
            NoteHandler h = new NoteHandler(denom);
            if (head == null) head = h; else tail.then(h);
            tail = h;
        }
        this.chain = head;
        this.smallest = Collections.min(notes.keySet());
    }

    int smallestNote() { return smallest; }

    Map<Integer, Integer> plan(long amount) {
        Map<Integer, Integer> out = new TreeMap<>(Comparator.reverseOrder());
        if (!chain.plan(amount, notes, out)) throw new IllegalStateException("ATM cannot dispense " + amount + " with the notes it has");
        return out;
    }

    void commit(Map<Integer, Integer> plan) { plan.forEach((d, n) -> notes.merge(d, -n, Integer::sum)); }
}

enum AtmState { IDLE, CARD_INSERTED, AUTHENTICATED }

class Atm {
    private AtmState state = AtmState.IDLE;
    private String card;
    private int badPins;
    private final BankService bank;
    private final CashDispenser dispenser;

    Atm(BankService bank, CashDispenser dispenser) { this.bank = bank; this.dispenser = dispenser; }

    private void require(AtmState expected) {
        if (state != expected) throw new IllegalStateException("not allowed in state " + state);
    }
    private void reset() { state = AtmState.IDLE; card = null; badPins = 0; }

    void insertCard(String card) { require(AtmState.IDLE); this.card = card; this.badPins = 0; state = AtmState.CARD_INSERTED; }

    void enterPin(String pin) {
        require(AtmState.CARD_INSERTED);
        if (bank.verifyPin(card, pin)) { state = AtmState.AUTHENTICATED; return; }
        if (++badPins >= 3) { reset(); throw new IllegalStateException("card retained after 3 wrong PINs"); }
        throw new IllegalArgumentException("wrong PIN, attempt " + badPins + " of 3");
    }

    long balance() { require(AtmState.AUTHENTICATED); return bank.balance(card); }

    Map<Integer, Integer> withdraw(long amount) {
        require(AtmState.AUTHENTICATED);
        if (amount <= 0 || amount % dispenser.smallestNote() != 0)
            throw new IllegalArgumentException("amount must be a positive multiple of " + dispenser.smallestNote());
        if (bank.balance(card) < amount) throw new IllegalStateException("insufficient balance");
        Map<Integer, Integer> plan = dispenser.plan(amount);      // 1. can we dispense it? (no side effects)
        bank.debit(card, amount);                                 // 2. authorize and debit
        dispenser.commit(plan);                                   // 3. remove the notes and hand them out
        return plan;
    }

    void eject() { reset(); }
}

public class Main {
    public static void main(String[] args) {
        InMemoryBank bank = new InMemoryBank();
        bank.addAccount("C1", "1234", 1000);
        CashDispenser cash = new CashDispenser(Map.of(100, 2, 50, 2, 20, 5, 10, 5));
        Atm atm = new Atm(bank, cash);

        try { atm.withdraw(50); } catch (IllegalStateException e) { System.out.println("error: " + e.getMessage()); }

        atm.insertCard("C1");
        try { atm.enterPin("0000"); } catch (IllegalArgumentException e) { System.out.println("error: " + e.getMessage()); }
        atm.enterPin("1234");
        System.out.println("withdraw 280 -> " + atm.withdraw(280) + ", balance " + atm.balance());

        try { atm.withdraw(5); } catch (IllegalArgumentException e) { System.out.println("error: " + e.getMessage()); }
        try { atm.withdraw(5000); } catch (IllegalStateException e) { System.out.println("error: " + e.getMessage()); }
        try { atm.withdraw(200); } catch (IllegalStateException e) { System.out.println("error: " + e.getMessage()); }
        System.out.println("balance unchanged after failed withdrawals: " + atm.balance());
        atm.eject();

        atm.insertCard("C1");
        for (int i = 0; i < 3; i++) {
            try { atm.enterPin("9999"); } catch (RuntimeException e) { System.out.println("error: " + e.getMessage()); }
        }
    }
}

// runnable
import java.util.*;

abstract class FsNode {
    final String name;
    FsNode(String name) { this.name = name; }
    abstract long size();
    abstract boolean isDirectory();
}

class FileNode extends FsNode {
    private String content;
    FileNode(String name, String content) { super(name); this.content = content; }
    String content() { return content; }
    void write(String c) { content = c; }
    long size() { return content.length(); }
    boolean isDirectory() { return false; }
}

class DirNode extends FsNode {
    final Map<String, FsNode> children = new TreeMap<>();
    DirNode(String name) { super(name); }
    long size() { return children.values().stream().mapToLong(FsNode::size).sum(); }
    boolean isDirectory() { return true; }
}

class FileSystem {
    private final DirNode root = new DirNode("");

    private static List<String> parts(String path) {
        if (path == null || !path.startsWith("/")) throw new IllegalArgumentException("path must be absolute: " + path);
        return Arrays.stream(path.split("/")).filter(s -> !s.isEmpty()).toList();
    }

    private FsNode resolve(String path) {
        FsNode cur = root;
        for (String p : parts(path)) {
            if (!(cur instanceof DirNode d) || !d.children.containsKey(p)) throw new NoSuchElementException("not found: " + path);
            cur = d.children.get(p);
        }
        return cur;
    }

    DirNode mkdir(String path) {
        DirNode cur = root;
        for (String p : parts(path)) {
            FsNode child = cur.children.get(p);
            if (child == null) {
                DirNode d = new DirNode(p);
                cur.children.put(p, d);
                cur = d;
            } else if (child instanceof DirNode d) {
                cur = d;
            } else {
                throw new IllegalArgumentException(p + " is a file, not a directory");
            }
        }
        return cur;
    }

    void writeFile(String path, String content) {
        List<String> ps = parts(path);
        if (ps.isEmpty()) throw new IllegalArgumentException("cannot write to root");
        String name = ps.get(ps.size() - 1);
        DirNode parent = mkdir("/" + String.join("/", ps.subList(0, ps.size() - 1)));
        FsNode existing = parent.children.get(name);
        if (existing instanceof DirNode) throw new IllegalArgumentException(path + " is a directory");
        if (existing instanceof FileNode f) f.write(content);
        else parent.children.put(name, new FileNode(name, content));
    }

    String read(String path) {
        if (resolve(path) instanceof FileNode f) return f.content();
        throw new IllegalArgumentException(path + " is a directory");
    }

    List<String> ls(String path) {
        FsNode n = resolve(path);
        if (n instanceof DirNode d)
            return d.children.values().stream().map(c -> c.isDirectory() ? c.name + "/" : c.name).toList();
        return List.of(n.name);
    }

    long size(String path) { return resolve(path).size(); }

    void delete(String path) {
        List<String> ps = parts(path);
        if (ps.isEmpty()) throw new IllegalArgumentException("cannot delete root");
        FsNode parent = resolve("/" + String.join("/", ps.subList(0, ps.size() - 1)));
        if (!(parent instanceof DirNode d) || d.children.remove(ps.get(ps.size() - 1)) == null)
            throw new NoSuchElementException("not found: " + path);
    }

    List<String> find(String name) {
        List<String> out = new ArrayList<>();
        walk(root, "", name, out);
        return out;
    }

    private void walk(DirNode dir, String prefix, String name, List<String> out) {
        for (FsNode c : dir.children.values()) {
            String p = prefix + "/" + c.name;
            if (c.name.equals(name)) out.add(p);
            if (c instanceof DirNode d) walk(d, p, name, out);
        }
    }
}

public class Main {
    public static void main(String[] args) {
        FileSystem fs = new FileSystem();
        fs.mkdir("/docs/work");
        fs.writeFile("/docs/work/plan.txt", "ship it");
        fs.writeFile("/docs/readme.md", "hello world");
        fs.writeFile("/readme.md", "root");

        System.out.println(fs.ls("/"));                       // [docs/, readme.md]
        System.out.println(fs.ls("/docs"));                   // [readme.md, work/]
        System.out.println(fs.read("/docs/work/plan.txt"));   // ship it
        System.out.println(fs.size("/docs"));                 // 18
        System.out.println(fs.find("readme.md"));             // [/docs/readme.md, /readme.md]

        fs.delete("/docs/work");
        System.out.println(fs.size("/docs"));                 // 11

        try { fs.read("/docs"); } catch (IllegalArgumentException e) { System.out.println("error: " + e.getMessage()); }
        try { fs.read("/nope/x"); } catch (NoSuchElementException e) { System.out.println("error: " + e.getMessage()); }
        try { fs.mkdir("/readme.md/sub"); } catch (IllegalArgumentException e) { System.out.println("error: " + e.getMessage()); }
    }
}