描述

模拟是计算机科学中的一个重要应用领域，涉及开发计算机模型以洞察现实世界的事件。模拟的种类繁多，包括（但不限于）离散事件模拟和时钟驱动模拟。模拟通常需要近似观察到的行为，以开发实用的方法。

本题涉及一个简化版弹球机的模拟。在弹球机中，一个钢球在平面上滚动，撞击各种物体（缓冲器）并累积分数，直到球从平面上“消失”。

你需要编写一个程序来模拟一个理想化的弹球机。该机器有一个平面，平面上有一些障碍物（缓冲器和墙壁）。平面被建模为一个 $m×n$ 的网格，原点位于左下角。每个缓冲器占据一个网格点。平面边缘的网格位置是墙壁。每次发射一个球（出现在网格上），球具有初始位置、方向和使用寿命。在此模拟中，所有位置均为整数，球的方向为以下之一：上、下、左或右。球在网格上弹跳，撞击缓冲器（累积分数）和墙壁（不增加分数）。撞击缓冲器所累积的分数是该缓冲器的分值。所有球的移动速度为每时间单位一个网格空间。

当球在某一时间单位内移动到缓冲器或墙壁的网格点时，视为“撞击”障碍物。撞击会导致球“反弹”，即顺时针旋转$90$度，且不会移动到障碍物上（仅方向改变）。注意，沿墙壁滑动不算作“撞击”墙壁。

球的使用寿命表示球在从平面上消失之前能存活的时间单位数。球每移动一个网格步长消耗一个时间单位寿命。撞击缓冲器或墙壁也会消耗一定的寿命，消耗量为该缓冲器或墙壁的成本。只要球在撞击缓冲器时寿命为正，就能获得该缓冲器的全部分值。注意，寿命为$1$的球将在下一次移动中“死亡”，因此无法在最后一次移动中因撞击缓冲器而获得分数。一旦寿命非正（小于或等于零），球将消失，游戏继续处理下一个球。

输入

你的程序应模拟一局弹球游戏。输入包含多行描述游戏的数据。第一行是两个整数 $m$ 和 $n$ ，用空格分隔，表示笛卡尔网格的范围为 $1 ≤ x ≤ m$ ， $1 ≤ y ≤ n$ ，游戏在此网格上进行。保证 $2 < m < 51$ 且 $2 < n < 51$ 。下一行是撞击墙壁的成本（整数）。接下来一行是缓冲器的数量 $p$ $（p ≥ 0）$ 。随后的 $p$ 行每行描述一个缓冲器，包含四个整数：$x$ 位置、$y$ 位置、分值和成本，用空格分隔。所有缓冲器的位置均在网格范围内，分值和成本可以是任意整数（可能为负；负成本会增加球的寿命）。

文件的剩余行表示球。每行描述一个球，包含四个整数：初始 $x$ 和 $y$ 位置、移动方向和使用寿命，用空格分隔。球的位置在网格范围内（且不会与任何缓冲器或墙壁重叠）。方向为四个值之一：$0$ 表示 $x$ 增加（右）， $1$ 表示 $y$ 增加（上）， $2$ 表示 $x$ 减少（左）， $3$ 表示 $y$ 减少（下）。寿命为正整数。

输出

每个球对应一行输出，表示该球累积的分数（按输入顺序）。最后输出所有球的总分。

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

0
0
1
2
2
5

来源

杜克大学互联网编程竞赛 1992，UVA 114