[AdditionalFile6993.zip](file://AdditionalFile6993.zip?type=additional_file)

#6993. 「ICPC World Finals 2025」藏宝图

标签: 传统 | 时间限制: 4000 ms | 内存限制: 2048 MiB |

题目描述

经过多年的搜寻，你终于找到了黑胡子船长的旧地图，上面标示着他失落已久的宝藏藏匿在深海海底的位置。这张地图曾经是一张测深地图。也就是说，它显示了宝藏周围区域的海洋深度。但许多深度标记随着时间的流逝已经褪色，不再清晰可辨。

具体来说，这张地图覆盖了一片矩形的海洋区域，被细分为一个 $(n-1) \times(m-1)$ 的单位正方形矩形网格。地图最初显示了每个整数坐标点 $p=(x, y)$ $(1 \leq x \leq n, 1 \leq y \leq m)$ 的海洋深度 $d(p)$。该区域内没有小岛。换句话说，已知所有点的深度 $d(p) \geq 0$。

对黑胡子来说，制作这张地图一定相当费劲，因为对于非整数坐标点的深度，没有一种唯一的、自然的插值方法。考虑网格上的一个单位正方形，其角点按顺时针顺序为 $A, B, C, D$，并且每个角点 $p \in\{A, B, C, D\}$ 都存储了一个深度值 $d(p)$。一种自然的插值方法是在三角形 $ABC$ 内进行线性插值，同样地在 $CDA$ 内进行线性插值。另一种同样自然的方法是在 $BCD$ 内进行线性插值，同样地在 $DAB$ 内进行线性插值。通常，这两种插值方法的结果是不同的。例如，如果 $d(A)=d(B)=d(C)=0$ 且 $d(D)=1$，第一种方法会导致整个 $ABC$ 区域的深度都等于零（图 K.1 左），而第二种方法则会导致整个正方形内部的深度都为正（右）。

然而，黑胡子既残酷又固执，他不会让这种讨厌的模糊性阻止他。为了给他的宝藏找到完美的藏匿点，他搜遍了七大洋，寻找一片海洋区域，使得对于每个单位正方形，上述两种方法都能得出相同的结果（或者，也许他强迫他的一些海盗做了一些地形改造工作来实现这一点——学者们对此有不同看法）。

回到现在，你正在准备一次寻宝探险，并想弄清楚宝藏可能被埋在多深的地方。具体来说，给定地图上剩余的深度数据，你应该计算出宝藏位置可能的最小深度。

输入格式

输入的第一行包含五个整数 $n, m, k, t_{x}, t_{y}$，其中 $n$ 和 $m$ $(2 \leq n, m \leq 3 \cdot 10^{5})$ 表示网格的最大坐标，$k$ $(1 \leq k \leq 3 \cdot 10^{5})$ 是已知深度的数量，而 $(t_{x}, t_{y})$ $(1 \leq t_{x} \leq n; 1 \leq t_{y} \leq m)$ 是宝藏的位置。接下来的 $k$ 行每行包含三个整数 $x, y, d$ $(1 \leq x \leq n; 1 \leq y \leq m; 0 \leq d \leq 10^{9})$，表示网格坐标 $(x, y)$ 处的深度等于 $d$。输入中每对 $(x, y)$ 最多出现一次。

输出格式

如果所提供的数据点可以扩展为一张有效的地图（即，对于每个单位正方形，两种插值方法都得出相同的结果，并且所有点的深度都为非负），则输出一个整数：$(t_{x}, t_{y})$ 处的最小可能深度——可以证明这个值总是一个整数。否则，输出 impossible。

样例 1

输入

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

输出

3

样例 2

输入

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

输出

1

样例 3

输入

3 3 3 3 3
2 3 1
2 1 2
1 2 4

输出

0

样例 4

输入

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

输出

impossible

样例 5

输入

3 3 3 2 2
3 2 0
2 2 1
2 3 0

输出

impossible

尽管输入中给出了 $(2,2)$ 的深度，但所提供的数据点无法扩展为一张有效的地图，因此正确答案是 impossible。