This is an interactive optimization problem. Instead of having to find the best answer, each solution will get score according to its efficiency. As the problem is interactive, during the testing process, the jury program and your solution will exchange messages via standard input and output streams. After printing a message, remember to flush the output buffer to ensure that the message is fully sent. For example, you can use _fflush(stdout)_ in C++, _System.out.flush()_ in Java, _flush(output)_ in Pascal, and _stdout.flush()_ in Python.
Your task is to automate the next generation taxi service, BuberPool. Each Buber car may transport up to four passengers at a time. The cars have to drive to passengers' locations, pick them up and drive them to their destinations. Additionally, unlike a traditional taxi, each car can process up to four orders simultaneously. For example, when driving a passenger to the destination, a car can pick up an additional passenger, or make a detour to drop off another passenger.
We will use the following simplified discrete model for this real-life problem.
Consider a city as a rectangular grid of $w$ streets and $h$ avenues with $w \times h$ crossroads. The streets are numbered from $1$ to $w$, and the avenues from $1$ to $h$. We will consider non-negative integer moments of time. Actions are performed in ticks: intervals of time between consecutive moments. At any moment, each car is located at some crossroads $(x, y)$, where $1 \le x \le w$ and $1 \le y \le h$. Any number of cars can be at the same crossroads simultaneously. During one tick, each car can either remain on the same crossroads or change exactly one of its coordinates, the street or the avenue, by one.
At moment $0$, you are given starting locations of $k$ cars: $(x_1, y_1)$, $(x_2, y_2)$, $\ldots$, $(x_k, y_k)$. The number of cars is equal to $k$ and does not change during the simulation.
Additionally, your solution will be given the clients' orders. In this problem, each order is made by a single passenger, so a car can process up to four orders at the same time. To further simplify the problem, the moments of orders are all distinct, and the orders are given in chronological order. So, each $j$\-th order is described by five integers: the moment $t_j$, the pick up location $(sx_j, sy_j)$, and the drop-off location $(tx_j, ty_j)$.
On tick $0$, and also right after receiving each order, you can give instruction sets to the car drivers. Each time you can give instruction sets to any number of cars (more on restrictions later). Instruction sets for different cars are given separately. An instruction set is a sequence of triples $(cx_1, cy_1, a_1)$, $(cx_2, cy_2, a_2)$, $\ldots$, $(cx_m, cy_m, a_m)$, where $m$ is number of instructions in the set. The meaning of these numbers is as follows:
* A car should first drive to $(cx_1, cy_1)$, then to $(cx_2, cy_2)$, $\ldots$, and at last to $(cx_m, cy_m)$. Each location $(cx_i, cy_i)$ may be any crossroads in the city, not necessarily a pickup or drop-off location. While driving from one location to another, a car always first changes its first coordinate until it is equal to the first coordinate of the destination, and only then the second coordinate. This way, while driving from $(p_1, q_1)$ to $(p_2, q_2)$, a car will first move $(p_1, q_1) \rightarrow (p_2, q_1)$, and then $(p_2, q_1) \rightarrow (p_2, q_2)$. In each tick while moving, a car changes exactly one of its coordinates by one.
* Values $a_i$ encode actions. If $a_i = 0$, the car just drives to $(cx_i, cy_i)$ and doesn't do anything special. If $a_i > 0$, the car drives to $(cx_i, cy_i)$ and picks up passenger number $a_i$ there (the passenger's pickup location should be equal to $(cx_i, cy_i)$, and the passenger should still be waiting there). If $a_i < 0$, the car moves to $(cx_i, cy_i)$ and drops off passenger number $-a_i$ (the passenger's drop-off location should be equal to $(cx_i, cy_i)$, and the passenger should be in this car). Picking up and dropping off passengers are instant.
When you give instruction set to a car, its previous instruction set is replaced with the new one. This way, a car only performs at most one instruction set at a time. If there are no instructions, or all of them are completed, the car is waiting at its last location. Instructions are performed in the given order.
For each order, first, all the cars perform their current instruction sets until the moment of the order comes, then the order is given to your program, and after that, your program prints new instruction sets for some of the cars. The cars which don't get new instruction sets continue performing their old ones.
So, the overall testing strategy looks like this:
1. Your solution reads the city dimensions, the number of cars, and their initial coordinates.
2. The solution prints instruction sets for some cars, and the cars start performing the instructions.
3. The solution reads an integer $t_j$, the moment of the next order (if $t_j = -1$, your program should print the final instruction sets and exit normally).
4. The solution reads integers $sx_j$, $sy_j$, $tx_j$, $ty_j$, the pickup and drop-off locations for $j$\-th order.
5. The solution prints the next instruction sets for the cars.
6. Go to step 3.
After your program exits in step 3, first, all instructions will be completely performed, and only after that the simulation will end.
The score your solution gets for a test is the average score for all orders, rounded to the nearest integer. The score for an order equals $\alpha \cdot (100 + w_0)$, where $w_0$ is time the order takes in the ideal case, which is just the time to get from $(sx_j, sy_j)$ to $(tx_j, ty_j)$ (so, $w_0 = |sx_j - tx_j| + |sy_j - ty_j|$), and $\alpha$ is a real value between $0$ and $1$ which characterizes the passenger's satisfaction with the ride. The value $\alpha$ is calculated by the formula:
\\alpha = \\frac{10^7 - min(d_1^2 + d_2^2, 10^7)}{10^7}\\text{,}
where $d_1$ is the waiting time before pickup (the number of ticks between the time of the order and pickup time), and $d_2$ is the difference between actual and ideal travel time (the ideal travel time is $w_0$). If the order was not completed, $\alpha = 0$.
The score your solution gets is just the sum of scores for each test.
## Input
The first line of input contains integers $w$ and $h$ ($300 \le w, h \le 3000$), the dimensions of the rectangular city. The second line contains an integer $k$ ($1 \le k \le 40$), the number of cars. Next $k$ lines contain integer coordinates $x_i$ and $y_i$ ($1 \le x_i \le w$, $1 \le y_i \le h$), the initial locations of cars. Recall that any number of cars can share the same location.
After reading this data, your program should output the initial instruction set for the cars (see output format), and then process the orders.
Each order is given on its own line and is described by five integers $t_j$, $sx_j$, $sy_j$, $tx_j$, $ty_j$ ($1 \le t_j \le 86\,400$, $1 \le sx_j, tx_j \le w$, $1 \le sy_j, ty_j \le h$), where $t_j$ is the moment of the order, $(sx_j, sy_j)$ is the passenger's pickup location and $(tx_j, ty_j)$ is the passenger's drop-off location. Orders are sorted by strictly increasing $t_j$. In each order, the pickup and drop-off locations are different.
After all orders, your program is given a line with five integers $-1$. In other words, if after reading another order, $t_j = -1$, it means that there are no more orders. It is guaranteed that the number of orders is between $1$ and $500$.
After reading each order, print the instruction sets for cars. Also, print the instruction sets after reaching the line with five integers $-1$. So, if the input contains $q$ orders, then the number of times to print instruction sets for cars is $q + 2$ (the initial one, one after each order, and the final one).
Remember that simulation is implemented in such a way that, for each order, first, all the cars perform their current instruction sets until the moment of the order comes, then the order is given to your program, and after that, your program prints new instruction sets for some of the cars. The cars which don't get new instruction sets continue performing their old ones.
During main part of the contest your solution will be tested on preliminary testset of 40 tests. Half of these tests (tests with odd numbers) are available for download at this url: [https://assets.codeforces.com/rounds/927/tests.zip](https://assets.codeforces.com/rounds/927/tests.zip). There is a test generated with each generation method prepared by the jury among the published tests.
After the round, last solution that has positive score on preliminary test will be used for testing. Other solutions will be ignored. All chosen solutions will be tested on secret testset, that is generated the same way (same generation methods), as preliminary tests. Jury will try to save test types and not to change statistic parameters a lot.
## Output
The output of your solution is instruction sets for the cars. Carefully read the problem statement and input format to understand the simulation process. Each of the $q + 2$ messages you print should be a sequence of integers on a single line.
Each message starts with a number $f$ ($0 \le f \le k$), that number of cars that will receive new instructions. It should be followed by $f$ space separated blocks.
Each block corresponds to an instruction set for a single car. A block starts with a pair of integers $c$ and $m$ ($1 \le c \le k$), the number of the car and the length of the instruction sequence for this car. Next there should be $m$ instructions: integer triples $cx, cy, a$ ($1 \le cx \le w$, $1 \le cy \le h$, $-q \le a \le q$), where a triple means that the car should drive to location $(cx, cy)$ and perform action $a$ (read the main part of the statement). Here, $q$ is the number of orders received so far.
There should be no more than $10^6$ instructions in all of the output of your program.
After printing the instruction sets, but before waiting for the next input, remember to flush the output buffer to ensure that the message is fully sent. For example, you can use _fflush(stdout)_ in C++, _System.out.flush()_ in Java, _flush(output)_ in Pascal, and _stdout.flush()_ in Python.
[samples]
这是一个交互式优化问题。与必须找到最佳答案不同，每个解决方案将根据其效率获得分数。由于这是一个交互式问题，在测试过程中，裁判程序和你的解决方案将通过标准输入和输出流交换消息。在打印一条消息后，请记得刷新输出缓冲区以确保消息被完全发送。例如，在 C++ 中可以使用 _fflush(stdout)_，在 Java 中使用 _System.out.flush()_，在 Pascal 中使用 _flush(output)_，在 Python 中使用 _stdout.flush()_。
你的任务是自动化下一代出租车服务 BuberPool。每辆 Buber 车最多可同时搭载四名乘客。车辆需要行驶至乘客的上车地点，接载他们并将其运送至目的地。此外，与传统出租车不同，每辆车可以同时处理多达四个订单。例如，在运送一名乘客前往目的地的过程中，车辆可以接载另一名乘客，或绕道送另一名乘客下车。
我们将使用以下简化的离散模型来模拟这一现实问题。
将城市视为一个由 $w$ 条街道和 $h$ 条大道组成的矩形网格，共有 $w \times h$ 个交叉路口。街道编号从 $1$ 到 $w$，大道编号从 $1$ 到 $h$。我们考虑非负整数时刻。动作在“滴答”（ticks）中执行：即连续时刻之间的间隔。在任意时刻，每辆车位于某个交叉路口 $(x, y)$，其中 $1 \lt.eq x \lt.eq w$ 且 $1 \lt.eq y \lt.eq h$。多个车辆可以同时位于同一交叉路口。在一次滴答中，每辆车要么保持在原交叉路口，要么恰好改变其一个坐标（街道或大道）一个单位。
在时刻 $0$，你将获得 $k$ 辆车的初始位置：$(x_1, y_1)$, $(x_2, y_2)$, $\dots.h$, $(x_k, y_k)$。车辆数量为 $k$，在模拟过程中保持不变。
此外，你的解决方案将收到客户的订单。在本问题中，每个订单由一名乘客发出，因此一辆车最多可同时处理四个订单。为简化问题，订单发生的时刻互不相同，且订单按时间顺序给出。因此，第 $j$ 个订单由五个整数描述：时刻 $t_j$、上车位置 $(s x_j, s y_j)$ 和下车位置 $(t x_j, t y_j)$。
在滴答 $0$，以及每次接收订单后，你可以向司机下达指令集。每次你可以向任意数量的车辆下达指令（有关限制请见下文）。不同车辆的指令集分别下达。一个指令集是一系列三元组 $(c x_1, c y_1, a_1)$, $(c x_2, c y_2, a_2)$, $\dots.h$, $(c x_m, c y_m, a_m)$，其中 $m$ 是指令集中的指令数量。这些数值的含义如下：
当你向一辆车下达指令集时，其之前的指令集将被新指令集替换。因此，一辆车在同一时间最多只执行一个指令集。如果没有指令，或所有指令已完成，车辆将停留在其最后的位置。指令按给定顺序执行。
对于每个订单，首先，所有车辆执行其当前指令集，直到订单发生的时刻；然后，订单被传递给你的程序；之后，你的程序为部分车辆打印新的指令集。未收到新指令集的车辆将继续执行其旧指令集。
因此，整体测试策略如下：
在步骤 3 中你的程序退出后，首先所有指令将被完全执行，然后模拟才会结束。
你的解决方案在某个测试用例中获得的分数是所有订单的平均分数，四舍五入到最接近的整数。某个订单的分数等于 $\alpha \dot.op (100 + w_0)$，其中 $w_0$ 是该订单在理想情况下的耗时，即从 $(s x_j, s y_j)$ 到 $(t x_j, t y_j)$ 所需的时间（因此 $w_0 = | s x_j - t x_j | + | s y_j - t y_j |$），而 $\alpha$ 是一个介于 $0$ 和 $1$ 之间的实数，表示乘客对乘车体验的满意度。$\alpha$ 的计算公式为：
$$\alpha = \frac{10^7 - \min(d_1^2 + d_2^2, 10^7)}{10^7}\text{,}$$
其中 $d_1$ 是上车前的等待时间（订单时刻与上车时刻之间的滴答数），$d_2$ 是实际旅行时间与理想旅行时间的差值（理想旅行时间为 $w_0$）。如果订单未完成，则 $\alpha = 0$。
你的解决方案获得的分数是每个测试用例得分的总和。
输入的第一行包含两个整数 $w$ 和 $h$（$300 \lt.eq w, h \lt.eq 3000$），表示矩形城市的尺寸。第二行包含一个整数 $k$（$1 \lt.eq k \lt.eq 40$），表示车辆数量。接下来 $k$ 行包含整数坐标 $x_i$ 和 $y_i$（$1 \lt.eq x_i \lt.eq w$，$1 \lt.eq y_i \lt.eq h$），表示车辆的初始位置。注意，多个车辆可以位于同一位置。
读取这些数据后，你的程序应输出车辆的初始指令集（见输出格式），然后处理订单。
每个订单单独占一行，由五个整数 $t_j$, $s x_j$, $s y_j$, $t x_j$, $t y_j$ 描述（$1 \lt.eq t_j \lt.eq 86 \, 400$，$1 \lt.eq s x_j, t x_j \lt.eq w$，$1 \lt.eq s y_j, t y_j \lt.eq h$），其中 $t_j$ 是订单时刻，$(s x_j, s y_j)$ 是乘客的上车位置，$(t x_j, t y_j)$ 是下车位置。订单按严格递增的 $t_j$ 排序。每个订单的上车和下车位置均不同。
在所有订单之后，你的程序会收到一行包含五个整数 $-1$ 的输入。换句话说，如果在读取另一个订单后 $t_j = -1$，则表示没有更多订单了。保证订单数量在 $1$ 到 $500$ 之间。
在读取每个订单后，打印车辆的指令集。在读取包含五个整数 $-1$ 的行后，也需打印指令集。因此，如果输入包含 $q$ 个订单，则打印车辆指令集的次数为 $q + 2$（初始一次，每个订单后一次，最后再一次）。
请注意，模拟的实现方式是：对于每个订单，首先所有车辆执行其当前指令集直至订单发生的时刻，然后订单被传递给你的程序，之后你的程序为部分车辆打印新的指令集。未收到新指令集的车辆将继续执行其旧指令集。
在竞赛主要阶段，你的解决方案将在包含 40 个测试用例的预测试集中进行测试。其中一半测试用例（奇数编号的测试）可在以下网址下载：https://assets.codeforces.com/rounds/927/tests.zip。发布的测试集中包含了由裁判准备的每种生成方法生成的测试用例。
竞赛结束后，将在预测试集中获得正分的最后一个解决方案用于最终测试。其他解决方案将被忽略。所有被选中的解决方案将在秘密测试集上进行测试，该测试集使用与预测试相同的生成方法生成。裁判将尽量保持测试类型不变，不大幅改变统计参数。
你的解决方案的输出是车辆的指令集。请仔细阅读问题描述和输入格式以理解模拟过程。你打印的每个 $q + 2$ 条消息都应为一行整数序列。
每条消息以一个数字 $f$（$0 \lt.eq f \lt.eq k$）开头，表示将接收新指令的车辆数量。其后跟随 $f$ 个空格分隔的块。
每个块对应一辆车的指令集。一个块以一对整数 $c$ 和 $m$（$1 \lt.eq c \lt.eq k$）开头，分别表示车辆编号和该车指令序列的长度。接下来应有 $m$ 个指令：整数三元组 $c x, c y, a$（$1 \lt.eq c x \lt.eq w$，$1 \lt.eq c y \lt.eq h$，$-q \lt.eq a \lt.eq q$），其中三元组表示车辆应驶向位置 $(c x, c y)$ 并执行动作 $a$（详见主描述部分）。此处 $q$ 是到目前为止接收的订单数量。
你的程序输出的指令总数不得超过 $10^6$ 条。
在打印指令集后、等待下一次输入前，请记得刷新输出缓冲区以确保消息被完全发送。例如，在 C++ 中可以使用 _fflush(stdout)_，在 Java 中使用 _System.out.flush()_，在 Pascal 中使用 _flush(output)_，在 Python 中使用 _stdout.flush()_。
## Input
输入的第一行包含两个整数 $w$ 和 $h$（$300 \lt.eq w, h \lt.eq 3000$），表示矩形城市的尺寸。第二行包含一个整数 $k$（$1 \lt.eq k \lt.eq 40$），表示车辆数量。接下来 $k$ 行包含整数坐标 $x_i$ 和 $y_i$（$1 \lt.eq x_i \lt.eq w$，$1 \lt.eq y_i \lt.eq h$），表示车辆的初始位置。注意，多个车辆可以位于同一位置。读取这些数据后，你的程序应输出车辆的初始指令集（见输出格式），然后处理订单。
每个订单单独占一行，由五个整数 $t_j$, $s x_j$, $s y_j$, $t x_j$, $t y_j$ 描述（$1 \lt.eq t_j \lt.eq 86 \, 400$，$1 \lt.eq s x_j, t x_j \lt.eq w$，$1 \lt.eq s y_j, t y_j \lt.eq h$），其中 $t_j$ 是订单时刻，$(s x_j, s y_j)$ 是乘客的上车位置，$(t x_j, t y_j)$ 是下车位置。订单按严格递增的 $t_j$ 排序。每个订单的上车和下车位置均不同。
在所有订单之后，你的程序会收到一行包含五个整数 $-1$ 的输入。换句话说，如果在读取另一个订单后 $t_j = -1$，则表示没有更多订单了。保证订单数量在 $1$ 到 $500$ 之间。
在读取每个订单后，打印车辆的指令集。在读取包含五个整数 $-1$ 的行后，也需打印指令集。因此，如果输入包含 $q$ 个订单，则打印车辆指令集的次数为 $q + 2$（初始一次，每个订单后一次，最后再一次）。
请注意，模拟的实现方式是：对于每个订单，首先所有车辆执行其当前指令集直至订单发生的时刻，然后订单被传递给你的程序，之后你的程序为部分车辆打印新的指令集。未收到新指令集的车辆将继续执行其旧指令集。
在竞赛主要阶段，你的解决方案将在包含 40 个测试用例的预测试集中进行测试。其中一半测试用例（奇数编号的测试）可在以下网址下载：https://assets.codeforces.com/rounds/927/tests.zip。发布的测试集中包含了由裁判准备的每种生成方法生成的测试用例。
竞赛结束后，将在预测试集中获得正分的最后一个解决方案用于最终测试。其他解决方案将被忽略。所有被选中的解决方案将在秘密测试集上进行测试，该测试集使用与预测试相同的生成方法生成。裁判将尽量保持测试类型不变，不大幅改变统计参数。
## Output
你的解决方案的输出是车辆的指令集。请仔细阅读问题描述和输入格式以理解模拟过程。你打印的每个 $q + 2$ 条消息都应为一行整数序列。
每条消息以一个数字 $f$（$0 \lt.eq f \lt.eq k$）开头，表示将接收新指令的车辆数量。其后跟随 $f$ 个空格分隔的块。
每个块对应一辆车的指令集。一个块以一对整数 $c$ 和 $m$（$1 \lt.eq c \lt.eq k$）开头，分别表示车辆编号和该车指令序列的长度。接下来应有 $m$ 个指令：整数三元组 $c x, c y, a$（$1 \lt.eq c x \lt.eq w$，$1 \lt.eq c y \lt.eq h$，$-q \lt.eq a \lt.eq q$），其中三元组表示车辆应驶向位置 $(c x, c y)$ 并执行动作 $a$（详见主描述部分）。此处 $q$ 是到目前为止接收的订单数量。
你的程序输出的指令总数不得超过 $10^6$ 条。
在打印指令集后、等待下一次输入前，请记得刷新输出缓冲区以确保消息被完全发送。例如，在 C++ 中可以使用 _fflush(stdout)_，在 Java 中使用 _System.out.flush()_，在 Pascal 中使用 _flush(output)_，在 Python 中使用 _stdout.flush()_。
[samples]
**Definitions**
Let $ w, h \in \mathbb{Z}^+ $ be the dimensions of the city grid, with crossroads at integer coordinates $ (x, y) $ where $ 1 \le x \le w $, $ 1 \le y \le h $.
Let $ k \in \mathbb{Z}^+ $ be the number of cars, with initial positions $ (x_i^0, y_i^0) \in [1, w] \times [1, h] $ for $ i \in \{1, \dots, k\} $.
Let $ \mathcal{O} = \{(t_j, s x_j, s y_j, t x_j, t y_j) \mid j \in \{1, \dots, q\}\} $ be the sequence of $ q \in [1, 500] $ orders, ordered by strictly increasing $ t_j \in [1, 86400] $, where:
- $ t_j $: time of order arrival,
- $ (s x_j, s y_j) $: pickup location,
- $ (t x_j, t y_j) $: drop-off location,
with $ (s x_j, s y_j) \ne (t x_j, t y_j) $.
Let $ \mathcal{C}_i^t $ denote the position of car $ i $ at time $ t $, and $ \mathcal{I}_i^t $ its current instruction set at time $ t $.
**Constraints**
1. Each car moves in one of four directions (up, down, left, right) or stays, per tick.
2. Each car can carry up to 4 simultaneous orders.
3. At time $ t_j $, all cars complete their current instructions up to time $ t_j $, then the order is revealed.
4. After each order (and initially), the solver may assign a new instruction set to any subset of cars (possibly empty).
5. Instruction sets are sequences of triples $ (c x, c y, a) $, meaning: move to $ (c x, c y) $ via Manhattan path, then perform action $ a $ (interpreted as order assignment/drop-off).
6. Action $ a \in \mathbb{Z} $, $ |a| \le q $, encodes order index or neutral.
7. Total number of instructions across all outputs $ \le 10^6 $.
8. After last order ($ t_j = -1 $), one final instruction set must be output.
**Objective**
Maximize total score:
$$
\text{Score} = \sum_{j=1}^{q} \text{Score}_j, \quad \text{Score}_j = \alpha_j \cdot (100 + w_0^j)
$$
where:
- $ w_0^j = |s x_j - t x_j| + |s y_j - t y_j| $: ideal travel time,
- $ d_1^j = \text{pickup time}_j - t_j $: waiting time before pickup,
- $ d_2^j = \text{actual travel time}_j - w_0^j $: extra travel time,
- $ \alpha_j = \begin{cases}
\frac{10^7 - \min(d_1^j{}^2 + d_2^j{}^2, 10^7)}{10^7} & \text{if order completed} \\
0 & \text{otherwise}
\end{cases} $
**Output Format**
For each of the $ q + 2 $ output events (initial + after each order + final):
- Print $ f $: number of cars receiving new instructions ($ 0 \le f \le k $).
- For each such car $ c \in \{1, \dots, k\} $:
- Print $ c $ (car index) and $ m $ (number of instructions in set).
- Print $ m $ triples $ (c x, c y, a) $, specifying destination and action.
- Flush output after each line.