from __future__ import annotations

import heapq
import math
from abc import ABC, abstractmethod
from dataclasses import dataclass
from enum import IntEnum
from itertools import count
from threading import Lock
from typing import Optional

class Size(IntEnum):
    SMALL = 1  # the numbers are the fit order
    MEDIUM = 2
    LARGE = 3

@dataclass(frozen=True)
class Vehicle:
    plate: str
    size: Size

import java.util.*;

enum Size { SMALL, MEDIUM, LARGE } // declaration order is the fit order

record Vehicle(String plate, Size size) {}

#include <array>
#include <iostream>
#include <memory>
#include <mutex>
#include <optional>
#include <queue>
#include <stdexcept>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

enum class Size { SMALL = 1, MEDIUM = 2, LARGE = 3 };  // the numbers are the fit order

struct Vehicle {
    string plate;
    Size size;
};

@dataclass(frozen=True)
class Spot:
    id: int
    floor: int
    size: Size

@dataclass(frozen=True)
class Ticket:
    id: int
    plate: str
    spot: Spot
    entry_time: int  # seconds; passed in, never read from a clock

record Spot(int id, int floor, Size size) {}

record Ticket(int id, String plate, Spot spot, long entryTime) {} // seconds; passed in, never read from a clock

struct Spot {
    int id, floor;
    Size size;
};

struct Ticket {
    int id;
    string plate;
    const Spot* spot;
    long entryTime;  // seconds; passed in, never read from a clock
};

class SpotIndex:
    """Free spots only, one min-heap per size: best fit in O(log n)."""

    def __init__(self, spots: list[Spot]) -> None:
        self._free: dict[Size, list[tuple[int, Spot]]] = {size: [] for size in Size}
        for spot in spots:
            self.give(spot)

    def take(self, vehicle: Vehicle) -> Optional[Spot]:
        for size in Size:  # SMALL, MEDIUM, LARGE: the smallest that fits wins
            if size >= vehicle.size and self._free[size]:
                return heapq.heappop(self._free[size])[1]
        return None

    def give(self, spot: Spot) -> None:
        heapq.heappush(self._free[spot.size], (spot.id, spot))

class SpotIndex {
    // Free spots only, one min-heap per size: best fit in O(log n).
    private final List<PriorityQueue<Spot>> free = new ArrayList<>();

    SpotIndex(List<Spot> spots) {
        for (int i = 0; i < Size.values().length; i++)
            free.add(new PriorityQueue<>(Comparator.comparingInt(Spot::id)));
        spots.forEach(this::give);
    }

    Spot take(Vehicle v) {
        for (int size = v.size().ordinal(); size < free.size(); size++) { // the smallest that fits wins
            Spot s = free.get(size).poll();
            if (s != null) return s;
        }
        return null;
    }

    void give(Spot s) { free.get(s.size().ordinal()).add(s); }
}

class SpotIndex {
    // Free spots only, one min-heap per size: best fit in O(log n).
    struct ById {
        bool operator()(const Spot* a, const Spot* b) const { return a->id > b->id; }
    };
    using Heap = priority_queue<const Spot*, vector<const Spot*>, ById>;
    array<Heap, 4> free;  // indexed by Size (1..3)

public:
    explicit SpotIndex(const vector<Spot>& spots) {
        for (const Spot& s : spots) give(&s);
    }

    const Spot* take(const Vehicle& v) {
        for (int size = int(v.size); size <= 3; size++) {  // the smallest that fits wins
            if (free[size].empty()) continue;
            const Spot* s = free[size].top();
            free[size].pop();
            return s;
        }
        return nullptr;
    }

    void give(const Spot* s) { free[int(s->size)].push(s); }
};

class PricingRule(ABC):
    @abstractmethod
    def apply(self, ticket: Ticket, exit_time: int, fee: int) -> int:
        """Return the new fee, given the fee so far."""

class PerHour(PricingRule):
    def __init__(self, rates: dict[Size, int]) -> None:
        self._rates = dict(rates)  # price per started hour, by spot size

    def apply(self, ticket: Ticket, exit_time: int, fee: int) -> int:
        hours = max(1, math.ceil((exit_time - ticket.entry_time) / 3600))
        return hours * self._rates[ticket.spot.size]

class PeakSurcharge(PricingRule):
    """+50% when the vehicle came in during rush hour."""

    PEAK_HOURS = (8, 9, 17, 18)

    def apply(self, ticket: Ticket, exit_time: int, fee: int) -> int:
        hour = ticket.entry_time // 3600 % 24
        return fee * 3 // 2 if hour in self.PEAK_HOURS else fee

class Pricing:
    def __init__(self, rules: list[PricingRule]) -> None:
        self._rules = list(rules)

    def fee(self, ticket: Ticket, exit_time: int) -> int:
        fee = 0
        for rule in self._rules:  # each rule gets the fee so far
            fee = rule.apply(ticket, exit_time, fee)
        return fee

interface PricingRule {
    /** Returns the new fee, given the fee so far. */
    int apply(Ticket t, long exitTime, int fee);
}

class PerHour implements PricingRule {
    private final int[] rates; // price per started hour, indexed by Size

    PerHour(int[] rates) { this.rates = rates.clone(); }

    public int apply(Ticket t, long exitTime, int fee) {
        long hours = Math.max(1, (exitTime - t.entryTime() + 3599) / 3600);
        return (int) hours * rates[t.spot().size().ordinal()];
    }
}

class PeakSurcharge implements PricingRule {
    // +50% when the vehicle came in during rush hour.
    public int apply(Ticket t, long exitTime, int fee) {
        long hour = t.entryTime() / 3600 % 24;
        boolean peak = hour == 8 || hour == 9 || hour == 17 || hour == 18;
        return peak ? fee * 3 / 2 : fee;
    }
}

class Pricing {
    private final List<PricingRule> rules;

    Pricing(List<PricingRule> rules) { this.rules = List.copyOf(rules); }

    int fee(Ticket t, long exitTime) {
        int fee = 0;
        for (PricingRule rule : rules) fee = rule.apply(t, exitTime, fee); // each rule gets the fee so far
        return fee;
    }
}

struct PricingRule {
    // Returns the new fee, given the fee so far.
    virtual int apply(const Ticket& t, long exitTime, int fee) const = 0;
    virtual ~PricingRule() = default;
};

struct PerHour : PricingRule {
    array<int, 4> rates;  // price per started hour, indexed by Size

    explicit PerHour(array<int, 4> rates) : rates(rates) {}

    int apply(const Ticket& t, long exitTime, int) const override {
        long hours = max(1L, (exitTime - t.entryTime + 3599) / 3600);
        return hours * rates[int(t.spot->size)];
    }
};

struct PeakSurcharge : PricingRule {
    // +50% when the vehicle came in during rush hour.
    int apply(const Ticket& t, long, int fee) const override {
        long hour = t.entryTime / 3600 % 24;
        bool peak = hour == 8 || hour == 9 || hour == 17 || hour == 18;
        return peak ? fee * 3 / 2 : fee;
    }
};

class Pricing {
    vector<unique_ptr<PricingRule>> rules;

public:
    explicit Pricing(vector<unique_ptr<PricingRule>> rules) : rules(std::move(rules)) {}

    int fee(const Ticket& t, long exitTime) const {
        int fee = 0;
        for (auto& rule : rules) fee = rule->apply(t, exitTime, fee);  // each rule gets the fee so far
        return fee;
    }
};

class WeekendDiscount(PricingRule):
    """-20% when the vehicle came in on a Saturday or Sunday."""

    def apply(self, ticket: Ticket, exit_time: int, fee: int) -> int:
        weekday = (ticket.entry_time // 86400 + 4) % 7  # 0 = Sunday
        return fee * 4 // 5 if weekday in (0, 6) else fee

class WeekendDiscount implements PricingRule {
    // -20% when the vehicle came in on a Saturday or Sunday.
    public int apply(Ticket t, long exitTime, int fee) {
        long weekday = (t.entryTime() / 86400 + 4) % 7; // 0 = Sunday
        return weekday == 0 || weekday == 6 ? fee * 4 / 5 : fee;
    }
}

struct WeekendDiscount : PricingRule {
    // -20% when the vehicle came in on a Saturday or Sunday.
    int apply(const Ticket& t, long, int fee) const override {
        long weekday = (t.entryTime / 86400 + 4) % 7;  // 0 = Sunday
        return weekday == 0 || weekday == 6 ? fee * 4 / 5 : fee;
    }
};

class UnknownTicketError(Exception):
    pass

class AlreadyParkedError(Exception):
    pass

class ParkingLot:
    def __init__(self, spots: list[Spot], pricing: Pricing) -> None:
        self._index = SpotIndex(spots)
        self._pricing = pricing
        self._open: dict[int, Ticket] = {}
        self._plates: set[str] = set()
        self._ids = count(1)
        self._lock = Lock()

    def park(self, vehicle: Vehicle, now: int) -> Optional[Ticket]:
        """Return a ticket, or None when the lot is full."""
        with self._lock:  # find + take + ticket is one step
            if vehicle.plate in self._plates:
                raise AlreadyParkedError(vehicle.plate)
            spot = self._index.take(vehicle)
            if spot is None:
                return None
            ticket = Ticket(next(self._ids), vehicle.plate, spot, now)
            self._open[ticket.id] = ticket
            self._plates.add(ticket.plate)
            return ticket

    def unpark(self, ticket_id: int, now: int) -> int:
        """Return the fee. Raises UnknownTicketError for an unknown or used ticket."""
        with self._lock:
            ticket = self._open.pop(ticket_id, None)
            if ticket is None:
                raise UnknownTicketError(ticket_id)
            self._plates.discard(ticket.plate)
            self._index.give(ticket.spot)
            return self._pricing.fee(ticket, now)

class UnknownTicketException extends RuntimeException {
    UnknownTicketException(int id) { super("unknown ticket " + id); }
}

class AlreadyParkedException extends RuntimeException {
    AlreadyParkedException(String plate) { super("already parked: " + plate); }
}

class ParkingLot {
    private final SpotIndex index;
    private final Pricing pricing;
    private final Map<Integer, Ticket> open = new HashMap<>();
    private final Set<String> plates = new HashSet<>();
    private int nextId = 1;

    ParkingLot(List<Spot> spots, Pricing pricing) {
        this.index = new SpotIndex(spots);
        this.pricing = pricing;
    }

    /** Returns a ticket, or null when the lot is full. */
    synchronized Ticket park(Vehicle v, long now) { // find + take + ticket is one step
        if (plates.contains(v.plate())) throw new AlreadyParkedException(v.plate());
        Spot spot = index.take(v);
        if (spot == null) return null;
        Ticket t = new Ticket(nextId++, v.plate(), spot, now);
        open.put(t.id(), t);
        plates.add(t.plate());
        return t;
    }

    /** Returns the fee. Throws UnknownTicketException for an unknown or used ticket. */
    synchronized int unpark(int ticketId, long now) {
        Ticket t = open.remove(ticketId);
        if (t == null) throw new UnknownTicketException(ticketId);
        plates.remove(t.plate());
        index.give(t.spot());
        return pricing.fee(t, now);
    }
}

struct UnknownTicket : runtime_error {
    explicit UnknownTicket(int id) : runtime_error("unknown ticket " + to_string(id)) {}
};

struct AlreadyParked : runtime_error {
    explicit AlreadyParked(const string& plate) : runtime_error("already parked: " + plate) {}
};

class ParkingLot {
    SpotIndex index;
    Pricing pricing;
    unordered_map<int, Ticket> open;
    unordered_set<string> plates;
    int nextId = 1;
    mutex lock;

public:
    ParkingLot(const vector<Spot>& spots, Pricing pricing)
        : index(spots), pricing(std::move(pricing)) {}

    // Returns a ticket, or nullopt when the lot is full.
    optional<Ticket> park(const Vehicle& v, long now) {
        lock_guard<mutex> guard(lock);  // find + take + ticket is one step
        if (plates.count(v.plate)) throw AlreadyParked(v.plate);
        const Spot* spot = index.take(v);
        if (!spot) return nullopt;
        Ticket t{nextId++, v.plate, spot, now};
        open[t.id] = t;
        plates.insert(t.plate);
        return t;
    }

    // Returns the fee. Throws UnknownTicket for an unknown or used ticket.
    int unpark(int ticketId, long now) {
        lock_guard<mutex> guard(lock);
        auto it = open.find(ticketId);
        if (it == open.end()) throw UnknownTicket(ticketId);
        Ticket t = it->second;
        open.erase(it);
        plates.erase(t.plate);
        index.give(t.spot);
        return pricing.fee(t, now);
    }
};

from concurrent.futures import ThreadPoolExecutor

rates = {Size.SMALL: 10, Size.MEDIUM: 20, Size.LARGE: 40}
pricing = Pricing([PerHour(rates), PeakSurcharge(), WeekendDiscount()])

# Best fit: a car takes the medium spot, the next car overflows into large, then full.
lot = ParkingLot([Spot(1, 1, Size.SMALL), Spot(2, 1, Size.MEDIUM), Spot(3, 2, Size.LARGE)], pricing)
first = lot.park(Vehicle("A", Size.MEDIUM), now=0)
second = lot.park(Vehicle("B", Size.MEDIUM), now=0)
third = lot.park(Vehicle("C", Size.LARGE), now=0)
print(first.spot.id, second.spot.id, third)  # 2 3 None

# 50 cars, 10 spots, 16 threads: exactly 10 tickets, no spot twice.
lot = ParkingLot([Spot(i, 1, Size.MEDIUM) for i in range(1, 11)], pricing)
cars = [Vehicle(f"CAR-{i}", Size.MEDIUM) for i in range(50)]
with ThreadPoolExecutor(max_workers=16) as pool:
    results = list(pool.map(lambda car: lot.park(car, now=0), cars))
got = [t for t in results if t]
print(len(got), len({t.spot.id for t in got}))  # 10 10

print(lot.unpark(got[0].id, now=3600))           # 20: one hour, off-peak
late = lot.park(Vehicle("LATE", Size.MEDIUM), now=8 * 3600)
print(lot.unpark(late.id, now=8 * 3600 + 1800))  # 30: 1 h x 20, +50% rush hour

sat = 2 * 86400                                  # day 2 after the epoch is a Saturday
ticket = lot.park(Vehicle("WKND", Size.MEDIUM), now=sat)
try:
    lot.park(Vehicle("WKND", Size.MEDIUM), now=sat)
except AlreadyParkedError:
    print("already parked")                      # the same plate cannot enter twice
print(lot.unpark(ticket.id, now=sat + 3600))     # 16: 1 h x 20, -20% weekend
try:
    lot.unpark(999, now=0)
except UnknownTicketError:
    print("unknown ticket")

import java.util.concurrent.*;

class Test {
    public static void main(String[] args) throws Exception {
        Pricing pricing = new Pricing(List.of(new PerHour(new int[]{10, 20, 40}), new PeakSurcharge(), new WeekendDiscount()));

        // Best fit: a car takes the medium spot, the next car overflows into large, then full.
        ParkingLot small = new ParkingLot(
            List.of(new Spot(1, 1, Size.SMALL), new Spot(2, 1, Size.MEDIUM), new Spot(3, 2, Size.LARGE)), pricing);
        Ticket first = small.park(new Vehicle("A", Size.MEDIUM), 0);
        Ticket second = small.park(new Vehicle("B", Size.MEDIUM), 0);
        Ticket third = small.park(new Vehicle("C", Size.LARGE), 0);
        System.out.println(first.spot().id() + " " + second.spot().id() + " " + third); // 2 3 null

        // 50 cars, 10 spots, 16 threads: exactly 10 tickets, no spot twice.
        List<Spot> spots = new ArrayList<>();
        for (int i = 1; i <= 10; i++) spots.add(new Spot(i, 1, Size.MEDIUM));
        ParkingLot lot = new ParkingLot(spots, pricing);
        List<Ticket> got = Collections.synchronizedList(new ArrayList<>());
        ExecutorService pool = Executors.newFixedThreadPool(16);
        for (int i = 0; i < 50; i++) {
            Vehicle car = new Vehicle("CAR-" + i, Size.MEDIUM);
            pool.submit(() -> {
                Ticket t = lot.park(car, 0);
                if (t != null) got.add(t);
            });
        }
        pool.shutdown();
        pool.awaitTermination(5, TimeUnit.SECONDS);
        System.out.println(got.size() + " " + got.stream().map(t -> t.spot().id()).distinct().count()); // 10 10

        System.out.println(lot.unpark(got.get(0).id(), 3600)); // 20: one hour, off-peak
        Ticket late = lot.park(new Vehicle("LATE", Size.MEDIUM), 8 * 3600);
        System.out.println(lot.unpark(late.id(), 8 * 3600 + 1800)); // 30: 1 h x 20, +50% rush hour

        long sat = 2 * 86400; // day 2 after the epoch is a Saturday
        Ticket ticket = lot.park(new Vehicle("WKND", Size.MEDIUM), sat);
        try {
            lot.park(new Vehicle("WKND", Size.MEDIUM), sat);
        } catch (AlreadyParkedException e) {
            System.out.println("already parked"); // the same plate cannot enter twice
        }
        System.out.println(lot.unpark(ticket.id(), sat + 3600)); // 16: 1 h x 20, -20% weekend
        try {
            lot.unpark(999, 0);
        } catch (UnknownTicketException e) {
            System.out.println("unknown ticket");
        }
    }
}

#include <set>
#include <thread>

Pricing makePricing() {
    vector<unique_ptr<PricingRule>> rules;
    rules.push_back(make_unique<PerHour>(array<int, 4>{0, 10, 20, 40}));  // small, medium, large
    rules.push_back(make_unique<PeakSurcharge>());
    rules.push_back(make_unique<WeekendDiscount>());
    return Pricing(std::move(rules));
}

int main() {
    // Best fit: a car takes the medium spot, the next car overflows into large, then full.
    vector<Spot> three{{1, 1, Size::SMALL}, {2, 1, Size::MEDIUM}, {3, 2, Size::LARGE}};
    ParkingLot small(three, makePricing());
    Vehicle a{"A", Size::MEDIUM}, b{"B", Size::MEDIUM}, c{"C", Size::LARGE};
    auto first = small.park(a, 0), second = small.park(b, 0), third = small.park(c, 0);
    cout << first->spot->id << " " << second->spot->id << " " << (third ? "ticket" : "none") << "\n";  // 2 3 none

    // 50 cars, 10 spots, 16 threads: exactly 10 tickets, no spot twice.
    vector<Spot> spots;
    for (int i = 1; i <= 10; i++) spots.push_back({i, 1, Size::MEDIUM});
    ParkingLot lot(spots, makePricing());
    vector<Vehicle> cars;
    for (int i = 0; i < 50; i++) cars.push_back({"CAR-" + to_string(i), Size::MEDIUM});
    vector<optional<Ticket>> results(50);
    vector<thread> threads;
    for (int i = 0; i < 50; i++)
        threads.emplace_back([&, i] { results[i] = lot.park(cars[i], 0); });
    for (thread& t : threads) t.join();

    set<int> used;
    int firstId = -1, n = 0;
    for (auto& r : results)
        if (r) { n++; used.insert(r->spot->id); if (firstId < 0) firstId = r->id; }
    cout << n << " " << used.size() << "\n";  // 10 10

    cout << lot.unpark(firstId, 3600) << "\n";  // 20: one hour, off-peak
    Vehicle lateCar{"LATE", Size::MEDIUM};
    auto late = lot.park(lateCar, 8 * 3600);
    cout << lot.unpark(late->id, 8 * 3600 + 1800) << "\n";  // 30: 1 h x 20, +50% rush hour

    long sat = 2 * 86400;  // day 2 after the epoch is a Saturday
    Vehicle wknd{"WKND", Size::MEDIUM};
    auto ticket = lot.park(wknd, sat);
    try {
        lot.park(wknd, sat);
    } catch (const AlreadyParked&) {
        cout << "already parked\n";  // the same plate cannot enter twice
    }
    cout << lot.unpark(ticket->id, sat + 3600) << "\n";  // 16: 1 h x 20, -20% weekend
    try {
        lot.unpark(999, 0);
    } catch (const UnknownTicket&) {
        cout << "unknown ticket\n";
    }
}