题目背景

众所周知，在乱西星的现代战争中，制空权是很重要的。为此，人们发展出了无人机技术——遗憾的是，由于乱西星的算法水平和各种意义上的通讯水平实在太落后了，所以这些无人机只能采用各自独立的傻瓜式战斗模式，这些模式不含任何随机因素，因此一场傻瓜式无人机空战总是几乎能在开始前就被预测到结果。

总而言之，乱西星上正在相互战争的 |\| 国和 () 国的傻瓜式无人机战斗机编队在其边境交界处的空域遭遇了，现在两国军方希望你能预测这一空战的结果。

题目描述

空域与时刻

由于乱西星的神秘物理法则，乱西星的时间和空间并不是连续的；若认为遭遇战开始的时刻是第 $1$ 时刻，那么对于任意的第 $k\in \N$ 个时刻，在这一时刻开始和结束时，一个物体（无人机或导弹）只能在形如 $(x,y,z)\in\mathbb Z^3$ 的位置（即空域内的整点）上。

无人机

由于空域相比无人机要大得多，因此我们可以将无人机视为一个质点（尽管他们实际上长得和地球上的一般意义上的飞机十分相似）。

飞行状态

在每个时刻，一架无人机的飞行状态可以用以下三组参数描述：

1. 当前时刻所在的坐标 $\vec p=(x,y,z)\in\mathbb Z^3$；
2. 当前时刻的飞行方向向量 $\vec{d},\|\vec d\|=1$；
   • 其中， $\|\vec{v}\|$ 表示向量 $\vec v$ 的长度：设 $\vec{v}=(v_x,v_y,v_z)$，则 $\|\vec{v}\|=\sqrt{v_x^2+v_y^2+v_z^2}$。
   • 你可以简单地将 $\vec d$ 理解为机头指向的方向。
3. 当前时刻的无人机升力线方向 $\vec u,\|\vec u\|=1,\vec u\bot \vec d$；
   • 你可以简单的将 $\vec u$ 理解为飞机所在平面的、从机腹指向机背的单位法向量。
   • 此时，$\vec d$ 和 $\vec u$ 可以唯一确定一个“左手向” $\vec l=\vec u\times \vec d$。

飞行性能

不严格地讲，一般而言，一架飞机通常有三个操作轴，即俯仰、滚转和偏航：俯(负杆)和仰(正杆)分别对应飞机机头向下和向上（即保持 $\vec l$ 不变）；滚转即飞机以飞行方向为中轴线旋转（即保持 $\vec d$ 不变）；偏航则为飞机机头向左或者向右（即保持 $\vec u$ 不变）。由于无人机的特殊设计，其没有偏航轴，只能进行俯仰和滚转——容易看出，即使仅进行俯仰和滚转，一架无人机也能随意地改变 $\vec d$ 和 $\vec u$ （在保持 $\|\vec u\|=\|\vec d\|=1,\vec u\bot \vec d$ 的前提下）。

以上的俯仰(正杆或负杆)、滚转操作，以及直线飞行，及其复合统称“机动”。

由于无人机型号差异，一架无人机的飞行性能可以用以下三组参数描述（为方便起见，在本节中，对进行一次机动前的飞行状态对应参数为 $\vec p=(x,y,z),\vec d,\vec u,\vec l$，进行一次机动后的飞行状态对应的参数为 $\vec p'=(x',y',z'),\vec d',\vec u',\vec l'$）：

1. 正杆率 $\theta_u\in(\dfrac\pi4,\dfrac\pi2)$ 和负杆率 $\theta_d\in(\dfrac\pi4,\dfrac \pi2)$；
   • 若无人机仅进行正杆机动，则必须有 $\vec p=\vec p',\vec l=\vec l',\vec u\cdot \vec d'\ge 0$；此时，进行一次这样的机动花费的时间是 $\dfrac{\angle(\vec d,\vec d')}{\theta_u}$。
   • 若无人机仅进行负杆机动，则必须有 $\vec p=\vec p',\vec l=\vec l',\vec u\cdot \vec d'\le 0$；此时，进行一次这样的机动花费的时间是 $\dfrac{\angle(\vec d,\vec d')}{\theta_d}$。
2. 滚转率 $\gamma\in(\dfrac\pi4,\dfrac \pi 2)$；
   • 若无人机仅进行滚转机动，则必须有 $\vec p=\vec p',\vec d=\vec d'$；此时，进行一次这样的机动花费的时间是 $\dfrac{\angle(\vec u,\vec u')}{\gamma}$。
3. 飞行极速 $v_{m}>0$；
   • 若无人机仅进行直线飞行，则必须有 $\vec d=\vec d',\vec u=\vec u'$；此时，花费的时间是 $\dfrac{\|\vec p'-\vec p\|}{v_m}$。

合法位移

在每个时刻，若一架无人机可以从 $\vec p=(x,y,z),\vec d,\vec u,\vec l$ 这一飞行状态，严格按照滚转、俯仰(正杆或负杆)和直线飞行的顺序进行机动，使飞行状态变为 $\vec p'=(x',y',z')\not=\vec p,\vec d',\vec u',\vec l'$，满足 $\vec d'//(\vec p'-\vec p)$，并且各机动花费的时间之和不超过 $1$，则称这是一次(无人机的)合法的综合机动。

如果一架无人机可以从 $\vec p=(x,y,z),\vec d,\vec u,\vec l$ 通过一次合法的综合机动，使飞行状态变为 $\vec p'=(x',y',z')\not=\vec p,\vec d',\vec u',\vec l'$，并且在所有使飞行状态变为 $\vec p''=\vec p',\vec d'',\vec u'',\vec l''$ 的合法综合机动中，总用时是最短的，则称之为一次（无人机的）合法位移（或称该位移合法）。此时，无人机会沿直线从 $\vec p$ 移动到 $\vec p'$。如无特殊指明，下文中“位移”均默认(应当为)合法位移。

眼镜蛇机动

在每个时刻，无论无人机飞行性能如何，无人机总是可以通过眼镜蛇机动，从 $\vec p=(x,y,z),\vec d,\vec u,\vec l$ 这一飞行状态，变为 $\vec p'=\vec p,\vec d'=\vec u,\vec u'=-\vec d,\vec l'=\vec l$ 这一飞行状态。注意，这种机动不被视为合法机动。

其它参数

除此之外，一架无人机还具有以下参数：

1. 无人机编号（简称“编号”）；
   • 保证任意两架无人机编号不同。
2. 所在阵营（简称“阵营”）；
   • 所在阵营必须是|\| 国或者是 () 国中之一，并且双方互称敌方阵营。

坠毁

一架无人机坠毁，当且仅当其符合下列条件之一：

1. 在某激活的导弹位移过程中，与该导弹的距离不大于导弹的空爆距离（详见下文）。
2. 在某导弹位移结束后，与该导弹位置重合（从而导弹直接命中无人机导致坠毁，下同）。
3. 在无人机位移过程中，存在至少一枚激活的导弹，与其距离不大于该导弹的空爆距离。
4. 在无人机位移结束后，存在至少一枚导弹所在位置与其位置重合。
5. 在无人机位移结束后，存在另一架无人机与其坐标相同（从而发生碰撞导致双双坠毁）。

无人机坠毁后将立即消失，此后不会发射导弹，也不会导致其它无人机坠毁。但无人机已经发射的导弹不会立刻消失或爆炸。

此时也称无人机被摧毁。

空空红外制导导弹

类似的，一枚空空红外制导导弹（下文简称“导弹”）也可视为一质点，并且同样可以描述其飞行状态和飞行性能。

飞行状态

由于导弹无所谓上下左右，因此仅需要以下两组参数以描述一个导弹的飞行状态：

1. 当前时刻所在的坐标 $\vec p=(x,y,z)\in\Z^3$；
2. 当前时刻的飞行方向向量 $\vec{d},\|\vec d\|=1$；
   • 你可以简单地将 $\vec d$ 理解为导弹弹头指向的方向。

飞行性能

同样由于一枚导弹无所谓上下左右，因此其不存在俯仰、滚转和偏航轴，其向各个方向改变 $\vec d$ 的性能是相同的，此时统称仅改变 $\vec d$ 的操作为 "偏航"。其与直线飞行及复合统称“机动”。

因此一枚导弹的飞行性能可以用以下两组参数描述（为方便起见，在本节中，对进行一次机动前的飞行状态对应参数为 $\vec p=(x,y,z),\vec d$，进行一次机动后的飞行状态对应的参数为 $\vec p'=(x',y',z'),\vec d'$）：

1. 偏航率 $\theta_r\in(\dfrac\pi4,\dfrac\pi2)$；
   • 若导弹仅进行偏航机动，则必须有 $\vec p=\vec p'$；此时，进行一次这样的机动花费的时间是 $\dfrac{\angle(\vec d,\vec d')}{\theta_r}$；
2. 飞行极速 $v_m>0$；
   • 若导弹仅进行直线飞行，则必须有 $\vec d=\vec d'$；此时，花费的时间是 $\dfrac{\|\vec p'-\vec p\|}{v_m}$。

合法位移

在每个时刻，若一枚导弹可以从 $\vec p=(x,y,z),\vec d$ 这一飞行状态，严格按照偏航和直线飞行的顺序进行机动，使飞行状态变为 $\vec p'=(x',y',z')\not=\vec p,\vec d'$，满足 $\vec d//(\vec p'-\vec p)$，并且各机动花费的时间之和不超过 $1$，则称这是一次(导弹的)合法位移（或称该位移合法）。此时，导弹会沿直线从 $\vec p$ 移动到 $\vec p'$。如无特殊指明，下文中“位移”均（应当）默认为合法位移。

其它参数

除此之外，一枚导弹还具有以下参数：

1. 保险距离 $d_s>0$ 和激活状态；
   • 导弹被发射后立即处于未激活状态。
   • 每个时刻结束时，若导弹处于未激活状态，并且发射该导弹的无人机已坠毁，或者与发射该导弹的无人机的距离大于保险距离 $d_s$ 时，进入激活状态。此后将保持激活状态，并称该导弹被激活，或称其为一枚激活的导弹。
2. 空爆距离 $d_p>0$；
   • 每次导弹位移过程中，当一枚激活的导弹与任一无人机（包括发射该导弹的无人机）距离不大于 $d_p$ 时，该导弹会进入可空爆状态（详见下文“可空爆”）。
   • 每次无人机位移过程中，若存在一无人机与一枚激活的导弹距离不大于 $d_p$ 时，该导弹也会进入可空爆状态。
3. 最大锁定角 $\beta_s\in(\dfrac\pi4,\dfrac\pi2)$；
   • 任意时刻，一枚飞行状态为 $\vec p=(x,y,z),\vec d$、最大锁定角的导弹能锁定到 $\vec p'$ 处的无人机，当且仅当 $\vec d\cdot(\vec p'-\vec p)>0$，并且 $\angle(\vec d,\vec p'-\vec p)\le \beta_s$。
   • 此时称该无人机能被该导弹锁定，或称其在导弹的锁定范围内。
   • 称 $\angle(\vec d,\vec p'-\vec p)$ 为锁定角。
4. 制导时长 $t_z>0$；
   • 若导弹在第 $k$ 个时刻被发射，则到第 $k+t_z$ 个时刻结束时，若导弹仍未爆炸，则导弹会立刻消失（见“爆炸、消失与可空爆”）。此时称导弹超过制导时长。

爆炸、消失与可空爆

一枚导弹在符合下列全部条件时，会立刻爆炸并消失：

1. 在导弹位移开始前，导弹处于激活状态；

2. 符合以下条件之一：

   1. 在该导弹位移过程中，存在一架位于 $\vec q$ 的无人机，使 $\min_{\lambda\in[0,1]}\|\lambda \vec p+(1-\lambda)\vec p'-\vec q\|\le d_p$，其中 $\vec p,\vec p'$ 为导弹本次位移的起点和终点。

      • 此时，所有这样的无人机都会被该导弹摧毁。同时，一架无人机可能同时被若干枚导弹摧毁。

   2. 在无人机位移过程中，存在一架无人机，记其从位置 $\vec q$ 位移到 $\vec q'$ ，满足 $\min_{\lambda\in[0,1]}\|\lambda \vec q+(1-\lambda)\vec q'-\vec p\|\le d_p$，其中 $\vec p$ 为导弹此时的位置。

      • 此时，所有这样的无人机都会被该导弹摧毁。同时，该导弹也可能同时摧毁若干这样的无人机。

此时，称该导弹可空爆，或该导弹进入可空爆状态。

一枚导弹在符合下列条件之一时，不会发生爆炸，但是会在当前时刻结束时消失：

1. 导弹脱锁（见下文“导弹脱锁”），并且在当前时刻开始时已被激活；

2. 导弹超过制导时长；

3. 导弹未激活，并且导弹位移结束后与一无人机位置重合；

   • 此时，该无人机会被这枚导弹摧毁。同时，一架无人机可能同时被若干枚导弹摧毁。

4. 导弹未激活，无人机位移结束后，该导弹与一无人机位置重合。

   • 此时，该无人机会被这枚导弹摧毁。同时，一枚导弹可能同时摧毁若干这样的无人机。

无人机视野、雷达搜索与导弹锁定

无人机视野

任意时刻，一架飞行状态为 $\vec p=(x,y,z),\vec d,\vec u,\vec l$ 的无人机能够发现一架位于 $\vec p'=(x',y',z')$ 的无人机，当且仅当 $\vec d\cdot(\vec p'-\vec p)> 0$；此时称 $\vec p'$ 处的无人机在 $\vec p$ 处无人机的视野内。

无人机机载雷达搜索范围

一架无人机的机载雷达（下文简称“雷达”）的扫描范围可以用以下两个参数描述：

1. 水平扫描范围 $L_x\in\N^+$ 和垂直扫描范围 $H_y\in\N^+$；
   • 任意时刻，一架飞行状态为 $\vec p=(x,y,z),\vec d,\vec u,\vec l$ 、雷达扫描范围为 $L_x,H_y$ 的无人机的能够扫描到一架位于 $\vec p'$ 的无人机，当且仅当，$\vec d\cdot(\vec p'-\vec p)>0$ 并且 $\exist x,y,s.t.\ |x|\le L_x,|y|\le H_y$ 且 $[\vec p'-(\vec p+x\vec l+y\vec u)]//\vec d$。
   • 即若以 $\vec p$ 为原点、以 $\vec l$ 和 $\vec u$ 为 $X,Y$ 轴建一平面 $\alpha=\alpha(\vec p;\vec l,\vec u)$，则 $\vec p'$ 在这一平面上的投影 $\vec r=P(\vec p';\alpha)$ 应当落在 $[-L_x,L_x]\times [-H_y,H_y]$ 中。
   • 此时称 $\vec p'$ 处的无人机在 $\vec p$ 处无人机雷达扫描范围内。

导弹脱锁

当无人机位移结束后，若一枚导弹选定的目标已坠毁，或其不能被该导弹锁定，则称该导弹脱锁，或处于脱锁状态。

此后将一直保持脱锁状态，无论是否此前选定的无人机是否重新可以被导弹锁定。

无人机选定目标策略

任意时刻，无人机（简称"本机"，下同）按下述策略选择目标无人机。

1. 若本机视野内无敌方阵营无人机（简称“敌机”，下同），则本机无选定目标；
2. 否则，若上一时刻本机选择的无人机仍位于本机视野内，则本机仍选定该目标；
3. 否则，若存在至少一架敌机处于本机雷达扫描范围内，则选取其中与本机距离最近的；若与本机距离最近的敌机不唯一，则选取编号最小的。
4. 否则，对视野内的处于 $\vec p'$ 的敌机，记 $\alpha=\alpha(\vec p;\vec l,\vec u),\vec r=P(\vec p';\alpha)=(r_x,r_y)$，则选取 $\min\{|r_x-L_x|,|r_x+L_x|\}+\min\{|r_y-H_y|,|r_y+H_y|\}$ 最小的。若有多个最小值，则同样选择编号最小的。

飞行策略

无人机飞行策略

设无人机飞行状态是 $\vec p=(x,y,z),\vec d,\vec u,\vec l$，其飞行极速为 $v_m$，机载雷达扫描范围为 $L_x,H_y$。

1. 若无人机有位于 $\vec p'$ 的选定目标：
   1. 若无人机能够合法地位移到某个位置，使敌机现在的位置 $\vec p'$ 仍处于本机的视野内，则无人机会合法地移动到飞行状态 $\vec q=(x_q,y_q,z_q),\vec d_q,\vec u_q,\vec l_q$，使敌机现在的位置 $\vec p'$ 仍处于本机视野内，且 $\|\vec p'-\vec q\|$ 最小。
      1. 若有多个这样的位置，记 $\alpha_q=\alpha(\vec q;\vec l_q,\vec u_q),\vec r_q=P(\vec p';\alpha_q)=(r_{qx},r_{qy})$，则优先选取使 $\vec r_q=(r_{qx},r_{qy})\in[-L_x,L_x]\times [-H_y,H_y]$ 的位置；
         1. 若仍有多个这样的位置，则选取使 $\|\vec r_q\|=\sqrt{r_{qx}^2+r_{qy}^2}$ 最小的；
         2. 若仍有多个这样的位置，则选取 $\vec q$ 字典序最小的。
      2. 若不存在这样的 $\vec r_q$，则选取使 $\min\{|r_{qx}-L_x|,|r_{qx}+L_x|\}+\min\{|r_{qy}-H_y|,|r_{qy}+H_y|\}$ 最小的；
         1. 若仍有多个这样的位置，则选取 $\vec q$ 字典序最小的。
   2. 否则，无人机会合法地移动到某个位置 $\vec q$，使 $\|\vec q-\vec p-v_m\vec d\|$ 最小；
      1. 若有多个这样的位置，则选取 $\vec q$ 字典序最小的。
2. 否则，无人机通过眼镜蛇机动，将飞行状态变为 $\vec p=(x,y,z),\vec u,-\vec d,\vec l$。

保证在上述1.的情况下，无人机总能合法地移动到某个位置。

导弹飞行策略

设导弹当前时刻飞行状态 $\vec p,\vec d$，其选定的敌机飞行状态为 $\vec p',\vec d',\vec u',\vec l'$；

若上一时刻结束时，导弹未脱锁，则记 $\vec q'$ 为敌机根据其飞行策略，下一时刻会移动到的位置。

若导弹能合法位移到 $\vec q'$，则导弹会直接位移到 $\vec q'$。

否则，导弹会合法地位移到能使敌机位移后的位置 $\vec q'$ 处于锁定范围内的位置 $\vec q$ ，且 $\|\vec q-\vec q'\|$ 最小。

1. 若有多个这样的 $\vec q$，则选取位移后锁定角最小的；
2. 若仍有多种可能，则选取 $\vec q$ 字典序最小的。

若不存在这样的位置，或者上个时刻结束时，导弹已经脱锁，则导弹会合法地位移到某个位置 $\vec q$，使 $\|\vec q-\vec p-v_m\vec d\|$ 最小。

保证导弹总能合法地移动到某个位置。

无人机发射导弹规则

一飞行状态为 $\vec p=(x,y,z),\vec d,\vec u,\vec l$ 的无人机（简称"本机"）向被本机选定的、处于 $\vec p'$ 的目标无人机（简称“敌机”）发射导弹的规则为：

在每个时刻开始时，若选定的敌机已处于本机雷达扫描范围内，且当前不存在由本机发射且未爆炸（或消失）的导弹，则向敌机发射一初始飞行状态为 $\vec p,\vec d=\dfrac{\vec p'-\vec p}{\|\vec p'-\vec p\|}$ 的未激活的导弹，该导弹选定敌机。

同一时刻内各事件发生顺序

1. 所有无人机选定目标，并确定当前时刻内的飞行策略；
2. 所有能发射导弹的无人机发射导弹；
3. 所有导弹确定飞行策略并位移，该过程中部分无人机可能被摧毁；
4. 所有可空爆的导弹爆炸并消失；
5. 所有无人机按 1. 中确定的飞行策略位移，该过程中部分无人机可能被摧毁；
6. 所有可空爆的导弹爆炸并消失；
7. 所有位置相同的无人机发生碰撞并坠毁。
8. 所有超过制导时长和脱锁且已激活的导弹消失。
9. 所有可激活的导弹被激活。

任务

给定空域开始时（即第 $1$ 时刻开始时），各无人机的飞行性能与状态、导弹的飞行性能，假定这场空战会持续 $T$ 个时刻，双方指挥官希望你能按时间顺序依次给出每个时刻发生的所有重要事件。

输入格式

第一行两个正整数 $n,T$ ，表示共有 $2n$ 架无人机，模拟前 $T$ 个时刻。其中，前 $n$ 架阵营是 |\| 国，后 $n$ 架阵营是 () 国。

接下来有 $2n$ 组数据，每一组包含若干行，其中第 $i$ 组描述了编号为 $i$ 的无人机。

在每组数据中：

第一行三个整数表示 $\vec p\in\mathbb Z^3$；保证所有的 $\vec p$ 两两不同，且坐标的绝对值不超过 $100$。

第二行六个整数依次表示无人机的 $\vec d,\vec u$，保证 $\vec d,\vec u\in S_v$；

• 其中， $S_v=\{(1,0,0),(-1,0,0),(0,1,0),(0,-1,0),(0,0,1),(0,0,-1)\}$；

第三行六个实数依次表示无人机的 $\theta_u,\theta_d,\gamma,v_m,L_x,H_y$；

第四行五个实数和一个正整数依次表示导弹的 $\theta_r,v_m,d_s,d_p,\beta_s,t_z$。

输出格式

输出 $T$ 组数据，第 $i$ 组数据表示第 $i$ 个时刻发生的重要事件。

在每组数据中：

第一行三个非负整数 $p_1,p_2,p_3$ ，表示在这个时刻的导弹位移过程中被摧毁的无人机数量、在这个时刻的无人机位移过程中被摧毁的无人机数量、这个时刻结束时，有多少组无人机因位置相同而两两碰撞坠毁。

接下来 $p_1$ 行，每行形如 $id_0\ k\ id_1\ id_2\ \cdots\ id_k$，表示编号为 $id_0$ 的无人机在这个时刻的导弹位移过程中被摧毁，并且在该过程中摧毁该无人机的导弹共有 $k$ 枚，分别来自编号为 $id_1,id_2,\cdots,id_k$ 的无人机。

为保证输出唯一，这 $p_1$ 行中的每一行内，$id_1,\dots,id_k$ 应当从小到大输出，行之间按 $id_0$ 从小到大输出。

接下来 $p_2$ 行，每行形如 $id_0\ k\ id_1\ id_2\ \cdots\ id_k$，表示编号为 $id_0$ 的无人机在这个时刻的无人机位移过程中被摧毁，并且在该过程中摧毁该无人机的导弹共有 $k$ 枚，分别来自编号为 $id_1,id_2,\cdots,id_k$ 的无人机。

为保证输出唯一，这 $p_2$ 行中的每一行内，$id_1,\dots,id_k$ 应当从小到大输出，行之间按 $id_0$ 从小到大输出。

接下来 $p_3$ 行，每行形如 $k\ id_1\ id_2\ \dots id_k$，表示该时刻结束时，有 $k$ 架无人机位置相同 ，它们的编号是 $id_1,...,id_n$。

为保证输出唯一，这 $p_3$ 行中的每一行内，$id_1,\dots,id_k$ 应当从小到大输出，行之间按 $id_1$ 从小到大输出，并且每个编号出现至多一次。

1 1
0 0 0
1 0 0 0 0 1
1 1 1 4 1 1
1 3 1 1 1 1
8 0 0
-1 0 0 0 0 1
1 1 1 4 1 1
1 3 1 1 1 1

0 0 1
2 1 2

1 4
0 0 0
1 0 0 0 0 1
1 1 1 3 1 1
1 15 3 2 1 10
60 0 0
-1 0 0 0 0 1
1 1 1 3 1 1
1 15 3 2 1 10

0 0 0
0 0 0
0 0 0
0 2 0
1 1 2
2 1 1

提示

样例解释 1

在第 $1$ 时刻，两架飞机于 $(4,0,0)$ 处相撞。

样例解释 2

在第 $4$ 时刻，两枚导弹分别摧毁了敌机。

数据范围

$T,n\le 100,3\le v_m\le 20$；

$v_m>10$ 的无人机和导弹总数不超过 $10$；

$\theta_u,\theta_d,\gamma,\theta_r,\beta_s\in(\dfrac\pi4,\dfrac\pi2)$；

$1\le d_s,d_p\le 20,1\le t_z\le 100$；

$|x|,|y|,|z|\le 100$；

$1\le L_x,H_y\le 100$。

所有输入的实数精确到小数点后不超过 $6$ 位。

最初时，$\vec p$ 两两不同。

题目来源

来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）初赛。

题解等资源可在 https://github.com/THUSAAC/THUPC2023-Pre 查看。