题目描述

请注意本题的空间限制为 16MiB。

扶苏在一款开放世界冒险游戏里承包了一个地块，她想在这个地块上建造刷石机。

扶苏承包的地块是一个 $n$ 行 $m$ 列的方格阵。我们用 $(i,j)$ 表示第 $i$ 行第 $j$ 列的方格。特别的，如果 $i < 1$ 或 $i > n$ 或 $j < 1$ 或 $j > m$，称格子 $(i,j)$ 不存在。

方格 $(i,j)$ 和如下四个方格相邻：$(i-1,j), (i+1,j), (i,j-1), (i,j+1)$。

初始时（第 $1$ 秒时），有一个格子 $(x_a, y_a)$ 上有熔岩，另一个格子 $(x_b, y_b)$ 上有水，其余格子为空地。如果水和熔岩相遇，会生成圆石。我们将在接下来具体叙述圆石的生成。

地图会按秒更新，自第二秒起，对于每一秒，对每个格子 $(i,j)$（如果存在）做如下检查：

• 如果 $(i,j)$ 上一秒是圆石，则这一秒 $(i,j)$ 的内容更新为空地。
• 如果 $(i,j)$ 上一秒是水或熔岩，则这一秒 $(i,j)$ 的内容保持不变，仍然为水或熔岩。
• 如果 $(i,j)$ 是空地，考察与 $(i,j)$ 相邻且存在的格子里：
  • 如果上一秒与 $(i,j)$ 相邻且存在的格子中有熔岩且没有水，则 $(i,j)$ 这一秒变为熔岩。
  • 如果上一秒与 $(i,j)$ 相邻且存在的格子中有水且没有熔岩，则 $(i,j)$ 这一秒变为水。
  • 如果上一秒与 $(i,j)$ 相邻且存在的格子中有熔岩也有水，则 $(i,j)$ 这一秒变为圆石。
  • 如果上一秒与 $(i,j)$ 相邻且存在的格子中没有熔岩也没有水，则 $(i,j)$ 这一秒保持空地不变。

现在，你要回答扶苏的 $q$ 次询问，每次询问的内容是：在第 $t$ 秒的格子 $(x,y)$ 的内容是什么？

输入格式

第一行是四个整数，表示地图的大小 $n,m$、询问的次数 $q$ 和询问的最大秒数 $T$。
第二行有两个整数，表示初始时熔岩的坐标 $(x_a, y_a)$。
第三行有两个整数，表示初始时水的坐标 $(x_b, y_b)$。
接下来 $q$ 行，每行三个整数 $t,x,y$ 表示一次询问。

输出格式

为了避免输出过大，你只需要输出一行四个整数，依次表示：

• 答案为空地的询问数量。
• 答案为水的询问数量。
• 答案为熔岩的询问数量。
• 答案为圆石的询问数量。

输出的整数之间用单个空格隔开。

5 5 3 3
1 1
3 3
1 1 1
3 3 1
2 5 5

1 0 1 1

解释 #1

• 第一次询问回答是熔岩。
• 第二次询问的回答是圆石。
• 第三次询问的回答是空地。

数据范围

• 对 $30\%$ 的测试点，$1 \leq n, m, q, T \leq 10$。
• 另有 $20\%$ 的测试点，$T = 1$。
• 另有 $30\%$ 的测试点，$q=1$。
• 对 $100\%$ 的测试点，保证 $1 \leq n, m,q\leq 1000$，$1 \leq x_a, x_b,x \leq n$，$1 \leq y_a, y_b,y \leq m$，$1 \leq t \leq T \leq 100$，$(x_a,y_a)$ 和 $(x_b, y_b)$ 不是同一个格子。