题目背景

支持了链路层和网络层的协议以后，路由器立刻了收到无数的数据包。虽然芃芃被大量的数据淹没，不过镇定的他还是记起来教材上写的话：网络设备能够处理的报文有两种，分别是控制报文和数据报文。对于路由器来说，数据报文就是需要转发的内容；而控制报文则是用来管理它的转发流向（路由表）的。为了和其他真实的路由器进行交互，你需要实现简单的路由协议 RIP；而在建立了转发表之后，需要开始进行“抛热土豆”，正确地将其他主机的流量送到对应的下一台路由器。

题目描述

你需要根据《学习手册》中的相关知识，处理下列两类报文：

一类是 RIP 路由协议的控制报文，它被封装在 UDP 协议数据报中。你将只会收到 RIP Response 报文，且目标 IP 地址是 224.0.0.9，目标 MAC 地址为 01:00:5E:00:00:09，用于指示路由表的更新，你需要根据源 IP 地址来判断它与你拥有的哪一个 IP 在同一个子网中，从而得知路由表中对应的出端口编号。对于收到的每一条路由信息，你需要根据给定的规则（见《学习手册》）恰当维护自身的路由表，记录对于可达的每一个网络前缀的下一跳信息（包括 IP 和 MAC）。对于控制报文，总是无需进行回复。

另一类是数据报文，它将被封装在 IP 分组中，你需要对目标 IP 地址非本机所拥有的分组进行转发。如果路由表中能够查询到目标 IP 地址对应的下一跳，则你应当构造一个合法的 IP 分组，填写正确的源、目标信息，并更新相关字段（如 TTL、校验和）；如果无法查询到路由信息，则你应当构造一个正确的 ICMP Destination Network Unreachable 报文返回给源主机；如果分组的 TTL 减小到 0，则你应当构造一个正确的 ICMP Time Exceeded 报文返回给源主机，这两种错误信息都需要按照《学习手册》的要求填入相应的负载，从接收者 MAC 地址中推断出源地址 IP ，并且以太网帧中（接收者的 MAC 地址，发送者的 MAC 地址）为输入数据中对应数据报文的（发送者的 MAC 地址，接收者的 MAC 地址）；如果同时出现无法查询到路由信息并且 TTL 减到 0 的情况，应当构造一个 ICMP Destination Network Unreachable。无论何种情况，对于一个目标 IP 地址不属于本机的数据报文，你实现的路由器总会产生一个发出的以太网帧。

由于转发报文需要填写下一跳的 MAC 地址，而我们不提供主动的 ARP 查询接口；在本小题中，你需要并仅从 RIP 报文的以太网帧头中获得相应目的路由器的 MAC 地址，以转发前最后一次获得到的为准 。

我们保证，在此问题给出的正常流量片段（也就是通过了校验的片段）中，包含且只包含上述两类报文；并且对于所有需要转发的包，你都能通过上述方法从 RIP 报文中获得对应目的路由器的 MAC 地址。和上题类似，Wireshark 会显示 UDP 校验值错误，忽略即可。

输入格式

输入包含不超过 $n$ 个流量片段，总大小不超过 $m$ 字节。根据输入，你需要构造的路由表的项目不超过 $k$ 条，需要查询路由表进行转发的报文占总报文的数量约为 $p_{query}\%$。

输出格式

你的输出将与答案文件进行逐字节对比。请不要输出任何多余信息，以免导致不必要的失分。

提示

【子任务】

测试点	$n$	$m$	$k$	$p_{query}$
1	$=10^2$	$=1.5\times 10^5$	$=10$	$=50\%$
2	$=10^3$	$=1.5\times 10^6$	$=10^2$
3				$=95\%$
4	$=10^4$	$=1.5\times 10^7$	$=10^3$	$=50\%$
5				$=95\%$
6	$=10^5$	$=2\times 10^7$	$=10^4$
7
8	$=10^6$	$=2\times 10^8$	$=10^5$
9
10

【样例 1】

见题目附件 1.in/ans。

【样例解释 1】

样例输入有十个以太网帧，包括八个 RIP 包和两个需要转发的 IP 包。

对于前四个 RIP Response，可以得到如下的路由表：

收到第一个 Response 后：

104.0.0.0/6 via 10.2.7.2 if 7 metric 7
13.115.192.0/18 via 10.2.7.2 if 7 metric 9
224.0.0.0/3 via 10.2.7.2 if 7 metric 15

收到第二个 Response 后：

104.0.0.0/6 via 10.2.7.2 if 7 metric 7
13.115.192.0/18 via 10.2.7.2 if 7 metric 9

收到第三个 Response 后：

104.0.0.0/6 via 10.2.7.2 if 7 metric 7
13.115.192.0/18 via 10.2.7.2 if 7 metric 9
88.128.0.0/10 via 10.2.6.2 if 6 metric 13

收到第四个 Response 后：

104.0.0.0/6 via 10.2.7.2 if 7 metric 7
88.128.0.0/10 via 10.2.6.2 if 6 metric 13

接着是两个 UDP 包，对于 77.147.142.166 这个地址，在路由表中没有对应的项，于是回应了 ICMP Destination unreachable 。对于 107.28.70.129 地址，它在 104.0.0.0/6 范围中，于是 TTL 减一并且转发到 10.2.7.2 ，它的 MAC 地址可以从第一个 RIP Response 得到。

收到第五个 Response 后：

104.0.0.0/6 via 10.2.7.2 if 7 metric 7
88.128.0.0/10 via 10.2.6.2 if 6 metric 13
130.127.0.0/17 via 10.2.4.2 if 4 metric 3

收到第六个 Response 后：

130.127.0.0/17 via 10.2.4.2 if 4 metric 3

收到第七个 Response 后：

130.127.0.0/17 via 10.2.4.2 if 4 metric 3
160.245.176.0/20 via 10.2.5.2 if 5 metric 9

收到第八个 Response 后：

130.127.0.0/17 via 10.2.4.2 if 4 metric 3
160.245.176.0/20 via 10.2.5.2 if 5 metric 9
90.32.0.0/15 via 10.2.5.2 if 5 metric 8

【提示】

由于每个数据报文的转发都需要查询路由表，因此需要用高效的数据结构存储路由表中的关键信息，同时也要注意空间的使用效率。关于算法的高效实现，你可以参考《学习手册》附带的相关论文和资料。

在转发 IP 分组时，分组头内很少的字段会被修改。因此 IP 校验值也未必需要重新计算，很多情况下可以只进行最小限度的改动。但如果你想进行任何形式的简化，务必保证你的操作与我们叙述的操作是完全等价的。直观的想法往往会遗漏一些边界情况，请一定注意。