Nihonbashi Simulator 是一款以虚构国家 R 的铁路公司 X 为经营对象的回合制模拟游戏。你是这款游戏的忠实粉丝，目标是将公司经营得利润丰厚。通过合理建设铁路和车站，帮助 R 国居民通勤，将 X 培养成最棒的铁路公司吧！

R 国被划分为 $N$ 行 $N$ 列的网格区域。第 $i$ 行（$0 \leq i < N$）和第 $j$ 列（$0 \leq j < N$）的区域记作 $(i, j)$。每个区域可以是空地、铁路或车站之一：

• 空地
  • 不与其他区域相连。
  • 可以支付费用建设车站或铁路。
• 铁路
  • 最多与上下左右的非空地区域中的 2 个区域相连。根据连接方式有 6 种类型，编号如下图所示。
  • 可以支付费用将其替换为车站。
• 车站
  • 最多与上下左右的 4 个非空地区域相连。

R 国有 $M$ 名居民。第 $c$ 个人的家在 $(i_{c,s}, j_{c,s})$，工作地点在 $(i_{c,t}, j_{c,t})$，他们需要在两地通勤。

游戏开始时，铁路公司 X 拥有 $K$ 资金，所有区域均为空地。游戏共进行 $T$ 回合。

游戏流程

每回合依次执行建设阶段和收款阶段。

建设阶段

在建设阶段，你可以选择以下三种操作之一：铺设铁路、建设车站或等待。不能进行导致资金为负的操作（在收款阶段前判断）。

• 铺设铁路：选择一个空地，将其变为 6 种铁路之一。资金减少 100。
• 建设车站：选择一个空地或铁路，将其变为车站。资金减少 5000。
• 等待：区域和资金均不变。

收款阶段

R 国居民同时进行通勤。对于第 $c$ 个人，若存在区域 $(i_p, j_p)$ 和 $(i_q, j_q)$ 满足以下条件，则他会使用铁路公司 X 的铁路并支付费用。每当居民使用铁路时，公司资金增加 $|i_{c,s} - i_{c,t}| + |j_{c,s} - j_{c,t}|$。

• 区域 $(i_p, j_p)$ 和 $(i_q, j_q)$ 均为车站。
• 从 $(i_p, j_p)$ 出发，经过若干相连的车站或铁路（可为 0 个），可以到达 $(i_q, j_q)$。
• $|i_{c,s} - i_p| + |j_{c,s} - j_p| \leq 2$
• $|i_{c,t} - i_q| + |j_{c,t} - j_q| \leq 2$

请在 $T$ 回合结束时，使资金尽可能多。

输入通过标准输入给出，格式如下：

N M K T
i_{0, s} j_{0, s} i_{0, t} j_{0, t}
i_{1, s} j_{1, s} i_{1, t} j_{1, t}
⋮
i_{M-1, s} j_{M-1, s} i_{M-1, t} j_{M-1, t}

• 第 1 行为 4 个整数 $N, M, K, T$，以空格分隔。
  • $N$：区域的行数和列数，$N = 50$。
  • $M$：R 国居民人数，$50 \leq M \leq 1600$。
  • $K$：铁路公司 X 的初始资金，$11000 \leq K \leq 20000$。
  • $T$：游戏回合数，$T = 800$。
• 接下来的 $M$ 行，每行 4 个整数，描述居民的通勤信息。第 $c$ 个人的家在 $(i_{c,s}, j_{c,s})$，工作在 $(i_{c,t}, j_{c,t})$。$0 \leq i_{c,s}, i_{c,t} < N, 0 \leq j_{c,s}, j_{c,t} < N, |i_{c,s} - i_{c,t}| + |j_{c,s} - j_{c,t}| > 4$。

请输出 $T$ 行，每行描述第 $t$ 回合建设阶段的操作，格式如下：

• 铺设铁路
  在区域 $(i, j)$ 建设类型为 $p$ 的铁路时，输出：p i j（以空格分隔）。铁路类型编号见题面说明。
• 建设车站
  在区域 $(i, j)$ 建设车站时，输出：0 i j。
• 等待
  输出 -1。

得分

每个测试用例，$T$ 回合结束时的资金为绝对得分，相对评价得分为 $\text{round}(10^9 \times \left(\frac{\text{自身绝对得分}}{\text{全体参赛者最大绝对得分}}\right))$，所有测试用例的相对得分之和为最终得分。若某测试用例全体参赛者最大绝对得分为 $0$，则 AC 的所有参赛者该测试用例得分为 $10^9$。

若输出不合法，判为 WA，包括：

• 在已有车站或铁路的区域铺设铁路
• 在已有车站的区域建设车站
• 资金为负的操作
• 铁路类型或区域指定不合法
• 输出操作数不是 $T$ 行

最终排名以系统测试（2000 个测试用例）得分为准，仅以最后一次非 CE 提交为准。

输入生成方法

• $M = \mathrm{round}(50 \times 2^{\mathrm{rand\_double}(0,5)})$
• 居民家和工作地点的坐标通过混合高斯分布生成，具体见原文。
• $K = \mathrm{rand}(\max(10, d) \times 100, 2 \times N \times 100) + 10000$，$d$ 为所有居民家与工作地点曼哈顿距离的最小值。

其它说明

• 可在输出中包含以 # 开头的注释行，评测时会忽略。
• 参见题面提供的样例程序和可视化工具。

输入格式

N M K T
i_{0, s} j_{0, s} i_{0, t} j_{0, t}
i_{1, s} j_{1, s} i_{1, t} j_{1, t}
⋮
i_{M-1, s} j_{M-1, s} i_{M-1, t} j_{M-1, t}

• 第 1 行：4 个整数 $N, M, K, T$，以空格分隔。
• 接下来的 $M$ 行：每行 4 个整数，描述第 $c$ 个人的家和工作地点坐标。

输出格式

输出 $T$ 行，每行描述第 $t$ 回合的操作：

• 铺设铁路：p i j（$p$ 为铁路类型编号，$i, j$ 为坐标）
• 建设车站：0 i j
• 等待：-1

提示

• 题目为模拟与优化题，目标是最大化 $T$ 回合结束时的资金。
• 具体铁路类型编号、连接规则、输入生成方法等详见题面说明。
• 可在输出中添加注释行，评测时会忽略。
• 参见题面提供的样例程序与可视化工具。

由 ChatGPT 4.1 翻译