在 DHCP 启动时，首先初始化 IP 地址池，将所有地址设置状态为未分配，占用者为空，并清零过期时刻。

其中地址的状态有未分配、待分配、占用、过期四种。

处于未分配状态的 IP 地址没有占用者，而其余三种状态的 IP 地址均有一名占用者。

处于待分配和占用状态的 IP 地址拥有一个大于零的过期时刻。

在当前时刻发送报文时，首先更新当前时刻IP池中IP地址的状态。在到达该过期时刻时，若该地址的状态是待分配，则该地址的状态会自动变为未分配，且占用者清空，过期时刻清零；否则该地址的状态会由占用自动变为过期，且过期时刻清零。

处于未分配和过期状态的 IP 地址过期时刻为零，即没有过期时刻。

对于收到的报文，设其收到的时刻为 t。处理细节如下：

1. 判断接收主机是否为本机，或者为 *，若不是，则判断类型是否为 Request，若不是，则不处理；
2. 若类型不是 Discover、Request 之一，则不处理；
3. 若接收主机为 *，但类型不是 Discover，或接收主机是本机，但类型是 Discover，则不处理。

对于 Discover 报文，按照下述方法处理：

1. 检查是否有占用者为发送主机的 IP 地址：
   • 若有，则选取该 IP 地址；
   • 若没有，则选取最小的状态为未分配的 IP 地址；
   • 若没有，则选取最小的状态为过期的 IP 地址；
   • 若没有，则不处理该报文，处理结束；
2. 将该 IP 地址状态设置为待分配，占用者设置为发送主机；
3. 若报文中过期时刻为 0 ，则设置过期时刻为 t+Tdef；否则根据报文中的过期时刻和收到报文的时刻计算过期时间，判断是否超过上下限：若没有超过，则设置过期时刻为报文中的过期时刻；否则则根据超限情况设置为允许的最早或最晚的过期时刻；
4. 向发送主机发送 Offer 报文，其中，IP 地址为选定的 IP 地址，过期时刻为所设定的过期时刻。

对于 Request 报文，按照下述方法处理：

1. 检查接收主机是否为本机：
   • 若不是，则找到占用者为发送主机的所有 IP 地址，对于其中状态为待分配的，将其状态设置为未分配，并清空其占用者，清零其过期时刻，处理结束；
2. 检查报文中的 IP 地址是否在地址池内，且其占用者为发送主机，若不是，则向发送主机发送 Nak 报文，处理结束；
3. 无论该 IP 地址的状态为何，将该 IP 地址的状态设置为占用；
4. 与 Discover 报文相同的方法，设置 IP 地址的过期时刻；
5. 向发送主机发送 Ack 报文。

enum State {
    unassigned, to_be_assigned, occupy, overdue
};
struct IP {
    State state;
    string occupier;
    int deadtime;
} ip[N];
int n, m, Tdef, Tmax, Tmin;
string dhcpname;

void update(int curtime)
{
    for(int i = 1; i <= n; i++)
        if((ip[i].state == to_be_assigned || ip[i].state == occupy) && ip[i].deadtime <= curtime)
        {
            if(ip[i].state == to_be_assigned)
            {
                ip[i].state = unassigned;
                ip[i].occupier = "";
                ip[i].deadtime = 0;
            }
            else
            {
                ip[i].state  = overdue;
                ip[i].deadtime = 0;
            }
        }
}

int get_ip_by_occupier(string client)
{
    for(int i = 1; i <= n; i++)
        if(ip[i].occupier == client)
            return i;
    return 0;
}

int get_ip_by_state(State state)
{
    for(int i = 1; i <= n; i++)
        if(ip[i].state == state)
            return i;
    return 0;
}

int main()
{
    cin >> n >> Tdef >> Tmax >> Tmin  >> dhcpname;

    cin >> m;
    while(m--)
    {
        int curtime;
        string client, server, type;
        int ip_address, deadtime;

        cin >> curtime >> client >> server >> type >> ip_address >> deadtime;

        if(!(server == dhcpname || server == "*") && type != "REQ") continue;
        if(!(type == "DIS" || type == "REQ")) continue;
        if(server == "*" && type != "DIS" || server == dhcpname && type  == "DIS") continue;

        update(curtime);

        if(type == "DIS")
        {
            int k = get_ip_by_occupier(client);
            if(!k) k = get_ip_by_state(unassigned);
            if(!k) k = get_ip_by_state(overdue);
            if(!k) continue;
            ip[k].state = to_be_assigned, ip[k].occupier = client;
            if(deadtime == 0)
                ip[k].deadtime = curtime + Tdef;
            else
                ip[k].deadtime = min(max(deadtime, curtime + Tmin), curtime + Tmax);

            cout << dhcpname << ' ' << client << ' ' << "OFR" << ' ' << k << ' ' << ip[k].deadtime << endl;
        }
        else
        {
            if(server != dhcpname)
            {
                for(int i = 1; i <= n; i++)
                    if(ip[i].occupier == client && ip[i].state == to_be_assigned)
                    {
                        ip[i].state = unassigned;
                        ip[i].occupier = "";
                        ip[i].deadtime = 0;
                    }
            }
            else
            {
                if(ip_address >= 1 && ip_address <= n && ip[ip_address].occupier == client)
                {
                    ip[ip_address].state = occupy;
                    if(deadtime == 0)
                        ip[ip_address].deadtime = curtime + Tdef;
                    else
                        ip[ip_address].deadtime = min(max(deadtime, curtime + Tmin), curtime + Tmax);

                    cout << dhcpname << ' ' << client << ' ' << "ACK" << ' ' << ip_address << ' ' << ip[ip_address].deadtime << endl;
                }
                else
                    cout << dhcpname << ' ' << client << ' ' << "NAK" << ' ' << ip_address << ' ' << 0 << endl;
            }
        }
    }

    //system("pause");
    return 0;
}