Air Combat on Luanxi Star

Airspace and Time

Due to the mysterious physical laws of Luanxi Star, time and space are not continuous. If the encounter begins at time $1$, then for any time $k \in \mathbb{Z}^+$, at the beginning and end of this time, an object (a drone or a missile) can only be at a position $(x, y, z) \in \mathbb{Z}^3$ (i.e., an integer point in the airspace).

Drones

Since the airspace is much larger than the drones, we can treat each drone as a point mass.

Flight State At each time, the flight state of a drone can be described by the following three sets of parameters: 1. The current coordinate $\vec{p} = (x, y, z) \in \mathbb{Z}^3$; 2. The current flight direction vector $\vec{d}$, $\|\vec{d}\| = 1$; - Here, $\|\vec{v}\|$ denotes the length of vector $\vec{v}$: for $\vec{v} = (v_x, v_y, v_z)$, $\|\vec{v}\| = \sqrt{v_x^2 + v_y^2 + v_z^2}$. - You can simply understand $\vec{d}$ as the direction the nose is pointing. 3. The current lift line direction $\vec{u}$, $\|\vec{u}\| = 1, \vec{u} \perp \vec{d}$; - You can simply understand $\vec{u}$ as the unit normal vector in the plane of the aircraft, pointing from the belly to the back. - At this point, $\vec{d}$ and $\vec{u}$ uniquely determine a "left-hand direction" $\vec{l} = \vec{u} \times \vec{d}$.

Flight Performance Generally speaking, an aircraft has three operational axes: pitch, roll, and yaw. Pitch (negative stick) and elevation (positive stick) correspond to the nose pointing down and up (keeping $\vec{l}$ constant); roll is the rotation of the aircraft along the flight axis (keeping $\vec{d}$ constant); yaw is the nose pointing left or right (keeping $\vec{u}$ constant). Due to the special design of these drones, they have no yaw axis and can only perform pitch and roll. It is easy to see that even with only pitch and roll, a drone can change $\vec{d}$ and $\vec{u}$ arbitrarily (provided $\|\vec{u}\| = \|\vec{d}\| = 1$ and $\vec{u} \perp \vec{d}$).

The above pitch (positive or negative stick), roll operations, and straight flight, along with their combinations, are collectively referred to as "maneuvers."

Due to differences in drone models, the flight performance of a drone can be described by the following three parameters (for convenience, in this section, the parameters before a maneuver are $\vec{p} = (x, y, z), \vec{d}, \vec{u}, \vec{l}$, and the parameters after a maneuver are $\vec{p}' = (x', y', z'), \vec{d}', \vec{u}', \vec{l}'$): 1. Positive stick rate $\theta_u \in (\frac{\pi}{4}, \frac{\pi}{2})$ and negative stick rate $\theta_d \in (\frac{\pi}{4}, \frac{\pi}{2})$; - If the drone only performs a positive stick maneuver, it must have $\vec{p} = \vec{p}', \vec{l} = \vec{l}', \vec{u} \cdot \vec{d}' \geq 0$; the time taken for one such maneuver is $\frac{\angle(\vec{d}, \vec{d}')}{\theta_u}$. - If the drone only performs a negative stick maneuver, it must have $\vec{p} = \vec{p}', \vec{l} = \vec{l}', \vec{u} \cdot \vec{d}' \leq 0$; the time taken for one such maneuver is $\frac{\angle(\vec{d}, \vec{d}')}{\theta_d}$. 2. Roll rate $\gamma \in (\frac{\pi}{4}, \frac{\pi}{2})$; - If the drone only performs a roll maneuver, it must have $\vec{p} = \vec{p}', \vec{d} = \vec{d}'$; the time taken for one such maneuver is $\frac{\angle(\vec{u}, \vec{u}')}{\gamma}$. 3. Maximum flight speed $v_m > 0$; - If the drone only performs straight flight, it must have $\vec{d} = \vec{d}', \vec{u} = \vec{u}'$; the time taken is $\frac{\|\vec{p}' - \vec{p}\|}{v_m}$.

Legal Displacement At each time, if a drone can move from flight state $\vec{p} = (x, y, z), \vec{d}, \vec{u}, \vec{l}$ by strictly following the order of roll, pitch (positive or negative stick), and straight flight to a new state $\vec{p}' = (x', y', z') \neq \vec{p}, \vec{d}', \vec{u}', \vec{l}'$, satisfying $\vec{d} // (\vec{p}' - \vec{p})$, and the sum of the time taken for each maneuver does not exceed 1, this is called a legal (drone) composite maneuver.

If a drone can move from $\vec{p} = (x, y, z), \vec{d}, \vec{u}, \vec{l}$ to $\vec{p}' = (x', y', z') \neq \vec{p}, \vec{d}', \vec{u}', \vec{l}'$ via a legal composite maneuver, and among all such maneuvers that result in $\vec{p}'$, the total time is the shortest, this is called a legal displacement (or the displacement is legal). At this point, the drone moves in a straight line from $\vec{p}$ to $\vec{p}'$. Unless otherwise specified, "displacement" defaults to a legal displacement.

Cobra Maneuver At any time, regardless of flight performance, a drone can always perform a Cobra maneuver to change from state $\vec{p} = (x, y, z), \vec{d}, \vec{u}, \vec{l}$ to $\vec{p}' = \vec{p}, \vec{d}' = \vec{u}, \vec{u}' = -\vec{d}, \vec{l}' = \vec{l}$. Note that this maneuver is not considered a legal maneuver.

Other Parameters 1. Drone ID (referred to as "ID"); - Any two drones are guaranteed to have different IDs. 2. Faction (referred to as "Faction"); - The faction must be either the $|\|$ country or the $()$ country, and both sides consider each other as the enemy faction.

Destruction A drone is destroyed if and only if one of the following conditions is met: 1. During the displacement of an active missile, the distance to the missile is no greater than the missile's airburst distance. 2. After a missile's displacement, its position coincides with the drone. 3. During the drone's displacement, there exists at least one active missile such that the distance to it is no greater than its airburst distance. 4. After the drone's displacement, there exists at least one missile whose position coincides with the drone's position. 5. After the drone's displacement, there exists another drone with the same coordinates (causing a collision, destroying both).

Once a drone is destroyed, it disappears immediately, will not launch any more missiles, and will not cause other drones to be destroyed. However, missiles already launched by the drone do not immediately disappear or explode.

Air-to-Air Infrared Guided Missiles

Similarly, an air-to-air infrared guided missile (referred to as "missile") can be treated as a point mass, and its flight state and performance can be described similarly.

Flight State Since a missile has no concept of up, down, left, or right, only two parameters are needed to describe its flight state: 1. Current coordinate $\vec{p} = (x, y, z) \in \mathbb{Z}^3$; 2. Current flight direction vector $\vec{d}, \|\vec{d}\| = 1$; - You can simply understand $\vec{d}$ as the direction the missile head is pointing.

Flight Performance Since a missile has no concept of up, down, left, or right, it has no pitch, roll, or yaw axes. Its performance in changing $\vec{d}$ in any direction is the same. This operation is collectively called "yaw." Combined with straight flight, it is called a "maneuver."

A missile's flight performance can be described by the following two parameters (for convenience, in this section, the parameters before a maneuver are $\vec{p} = (x, y, z), \vec{d}$, and the parameters after a maneuver are $\vec{p}' = (x', y', z'), \vec{d}'$): 1. Yaw rate $\theta_r \in (\frac{\pi}{4}, \frac{\pi}{2})$; - If the missile only performs a yaw maneuver, it must have $\vec{p} = \vec{p}'$; the time taken for one such maneuver is $\frac{\angle(\vec{d}, \vec{d}')}{\theta_r}$. 2. Maximum flight speed $v_m > 0$; - If the missile only performs straight flight, it must have $\vec{d} = \vec{d}'$; the time taken is $\frac{\|\vec{p}' - \vec{p}\|}{v_m}$.

Legal Displacement At each time, if a missile can move from flight state $\vec{p} = (x, y, z), \vec{d}$ by strictly following the order of yaw and straight flight to a new state $\vec{p}' = (x', y', z') \neq \vec{p}, \vec{d}'$, satisfying $\vec{d} // (\vec{p}' - \vec{p})$, and the sum of the time taken for each maneuver does not exceed 1, this is called a legal (missile) displacement. At this point, the missile moves in a straight line from $\vec{p}$ to $\vec{p}'$.

Other Parameters 1. Insurance distance $d_s > 0$ and activation status; - A missile is inactive immediately after launch. - At the end of each time, if a missile is inactive and the drone that launched it has been destroyed, or the distance to the launching drone is greater than $d_s$, it becomes active. From then on, it remains active and is called an active missile. 2. Airburst distance $d_p > 0$; - During each missile displacement, if an active missile is within distance $d_p$ of any drone (including the launching drone), it enters the airburst-capable state. - During each drone displacement, if a drone is within distance $d_p$ of an active missile, the missile also enters the airburst-capable state. 3. Maximum lock-on angle $\beta_s \in (\frac{\pi}{4}, \frac{\pi}{2})$; - At any time, a missile with state $\vec{p}, \vec{d}$ can lock onto a drone at $\vec{p}'$ if and only if $\vec{d} \cdot (\vec{p}' - \vec{p}) > 0$ and $\angle(\vec{d}, \vec{p}' - \vec{p}) \leq \beta_s$. 4. Guidance duration $t_z > 0$; - If a missile is launched at time $k$, it will explode immediately at the end of time $k + t_z$ if it has not already exploded.

Explosion, Disappearance, and Airburst A missile explodes and disappears immediately if: 1. Before the missile's displacement, it is in an active state; 2. One of the following conditions is met: - During the missile's displacement, there exists a drone at $\vec{q}$ such that $\min_{\lambda \in [0,1]} \|\lambda \vec{p} + (1 - \lambda) \vec{p}' - \vec{q}\| \leq d_p$, where $\vec{p}, \vec{p}'$ are the start and end points of the displacement. All such drones are destroyed. - During the drone's displacement, there exists a drone moving from $\vec{q}$ to $\vec{q}'$ such that $\min_{\lambda \in [0,1]} \|\lambda \vec{q} + (1 - \lambda) \vec{q}' - \vec{p}\| \leq d_p$, where $\vec{p}$ is the missile's position. All such drones are destroyed.

A missile will disappear at the end of the current time without exploding if: 1. The missile loses lock and was already active at the start of the current time; 2. The missile exceeds its guidance duration; 3. The missile is inactive and its position coincides with a drone after displacement; 4. The missile is inactive and a drone's position coincides with the missile after the drone's displacement.

Drone Vision, Radar Search, and Missile Lock-on

Drone Vision At any time, a drone with state $\vec{p}, \vec{d}, \vec{u}, \vec{l}$ can discover a drone at $\vec{p}'$ if and only if $\vec{d} \cdot (\vec{p}' - \vec{p}) > 0$.

Drone Radar Search Range A drone's radar scan range is described by horizontal scan range $L_x \in \mathbb{R}^+$ and vertical scan range $H_y \in \mathbb{R}^+$. A drone at $\vec{p}$ can scan a drone at $\vec{p}'$ if and only if $\vec{d} \cdot (\vec{p}' - \vec{p}) > 0$ and the projection of $\vec{p}'$ onto the plane defined by $\vec{p}$ and axes $\vec{l}, \vec{u}$ falls within $[-L_x, L_x] \times [-H_y, H_y]$.

Missile Lock Loss After a drone's displacement, if a missile's target has been destroyed or can no longer be locked onto, the missile loses lock. It will remain in the lock-lost state thereafter.

Drone Target Selection Strategy 1. If there are no enemy drones in the drone's vision, it has no target. 2. Otherwise, if the target selected in the previous time is still in vision, it remains the target. 3. Otherwise, if there is at least one enemy drone in the radar scan range, select the one closest to the drone; if there is a tie, select the one with the smallest ID. 4. Otherwise, for enemy drones in vision at $\vec{p}'$, let $\alpha = \alpha(\vec{p}; \vec{u}, \vec{l})$ and $\vec{r} = P(\vec{p}'; \alpha) = (r_x, r_y)$, select the one that minimizes $\min\{|r_x - L_x|, |r_x + L_x|\} + \min\{|r_y - H_y|, |r_y + H_y|\}$. If there is a tie, select the one with the smallest ID.

Flight Strategy

Drone Flight Strategy 1. If the drone has a target at $\vec{p}'$: - If the drone can legally move to a position such that $\vec{p}'$ is still in vision, it moves to a state $\vec{q}$ that keeps $\vec{p}'$ in vision and minimizes $\|\vec{p}' - \vec{q}\|$. - Otherwise, the drone moves to a position $\vec{q}$ that minimizes $\|\vec{q} - \vec{p} - v_m \vec{d}\|$. - Otherwise, the drone performs a Cobra maneuver.

Missile Flight Strategy If the missile was not in a lock-lost state at the end of the previous time, let $\vec{q}'$ be the position the target will move to in the next time. If the missile can legally move to $\vec{q}'$, it does so. Otherwise, it moves to a position $\vec{q}$ that keeps $\vec{q}'$ within the lock-on range and minimizes $\|\vec{q} - \vec{q}'\|$. If this is not possible, or if the missile has lost lock, it moves to a position $\vec{q}$ that minimizes $\|\vec{q} - \vec{p} - v_m \vec{d}\|$.

Drone Missile Launch Rules

At the start of each time, if the selected target is within the radar scan range and there is no missile launched by this drone that has not yet exploded (or disappeared), the drone launches an inactive missile toward the target with initial state $\vec{p}, \vec{d} = \frac{\vec{p}' - \vec{p}}{\|\vec{p}' - \vec{p}\|}$.

Event Order within the Same Time

1. All drones select targets and determine flight strategies.
2. All drones capable of launching missiles do so.
3. All missiles determine flight strategies and move; some drones may be destroyed.
4. All airburst-capable missiles explode and disappear.
5. All drones move according to their flight strategies; some drones may be destroyed.
6. All airburst-capable missiles explode and disappear.
7. All drones at the same position collide and are destroyed.
8. All missiles that exceeded guidance duration or lost lock and were active disappear.
9. All activatable missiles become active.

Input

The first line contains two positive integers $n, T$, representing $2n$ drones and $T$ time steps. The first $n$ drones belong to the $|\|$ country, and the next $n$ belong to the $()$ country. There are $2n$ groups of data, each describing drone $i$: - First line: three integers $\vec{p} \in \mathbb{Z}^3$. - Second line: six integers representing $\vec{d}, \vec{u} \in S_v$, where $S_v = \{(1, 0, 0), (-1, 0, 0), (0, 1, 0), (0, -1, 0), (0, 0, 1), (0, 0, -1)\}$. - Third line: six real numbers $\theta_u, \theta_d, \gamma, v_m, L_x, H_y$. - Fourth line: five real numbers and one positive integer $\theta_r, v_m, d_s, d_p, \beta_s, t_z$.

Output

Output $T$ groups of data, where the $i$-th group represents important events at time $i$. Each group contains: - First line: three non-negative integers $p_1, p_2, p_3$ (drones destroyed during missile movement, drones destroyed during drone movement, and groups of drones colliding at the end). - Next $p_1$ lines: $id_0 \ k \ id_1 \ id_2 \dots id_k$ (drone $id_0$ destroyed by $k$ missiles from $id_1, \dots, id_k$). - Next $p_2$ lines: $id_0 \ k \ id_1 \ id_2 \dots id_k$ (drone $id_0$ destroyed by $k$ missiles from $id_1, \dots, id_k$). - Next $p_3$ lines: $k \ id_1 \ id_2 \dots id_k$ (at the end, $k$ drones at the same position with IDs $id_1, \dots, id_k$).

Examples

Input 1

1 1 1
2 0 0 0
3 1 0 0 0 1
4 1 1 1 4 1 1
5 1 3 1 1 1 1
6 8 0 0
7 -1 0 0 0 1
8 1 1 1 4 1 1
9 1 3 1 1 1 1

Output 1

1 0 0 1
2 2 1 2

Note 1

At time 1, two aircraft collide at $(4, 0, 0)$.

Input 2

1 1 4
2 0 0 0
3 1 0 0 0 1
4 1 1 1 3 1 1
5 1 15 3 2 1 10
6 60 0 0
7 -1 0 0 0 1
8 1 1 1 3 1 1
9 1 15 3 2 1 10

Output 2

1 0 0 0
2 0 0 0
3 0 0 0
4 0 2 0
5 1 1 2
6 2 1 1

Note 2

At time 4, two missiles destroy enemy aircraft.