P17869 [FJCPC 2026] 青青草原扛把子

青青草原的羊村有一座正方形的围墙，左下角正对着大门口，边长正好是 $side(1\leq side\leq 5\times {10}^8)$ 个羊蹄印的距离。**围墙上**早就钉好了 $n(2\leq n\leq {10}^5)$ 根结实的木桩，每一根的位置已经用整数坐标 $(x_i, y_i)(1\leq i\leq n, 0\leq x_i, y_i\leq side)$ 标好，表示这根木桩可以从大门口往东走 $x_i$ 个羊蹄印的距离，再往北走 $y_i$ 个羊蹄印的距离得到。羊村初代村长软绵绵已经把所有木桩**修在了围墙的边沿上**。 **注意：不同木桩的坐标可能相同（即多个木桩可以钉在完全一样的位置，但它们仍然是各自独立的木桩，因此可以分别站一只羊）。** 又到了五年一度选"青青草原扛把子"的时候。按照传统，要从所有木桩里选出 $k(4\leq k\leq n)$ 个候选羊的站位，每只候选羊各自守在一个桩子上。为了保证各位扛把子候选人互不干扰、势力范围清晰，要求**任意两只候选羊之间的曼哈顿距离的最小值尽可能大**——毕竟草原上的羊儿走街串巷全凭横平竖直的草地小道，距离嘛，自然得按曼哈顿距离来算。 于是，慢羊羊村长把这个难题交给了你：给定木桩坐标，选出 $k$ 个桩子，使得两两之间最小的曼哈顿距离达到最大，并输出这个最优的最小距离。

第一行给出一个整数 $T(1\leq T\leq 2.5\times {10}^4)$，表示数据组数。 接下来有 $T$ 组数据，每组数据先输入三个整数 $side(1\leq side\leq 5\times{10}^8), k(4\leq k\leq 10^5), n(k\leq n\leq 10^5)$，表示正方形围墙的边长、候选羊的数量、木桩数。 接下来有 $n$ 行，每行输入两个整数 $x_i, y_i(1\leq i\leq n, 0\leq x_i, y_i\leq side)$，表示木桩的坐标。**保证木桩坐标均位于正方形围墙上**。 保证 $\sum n\leq 10^5$。

输出 $T$ 行，每行一个整数。 其中，第 $i(1\leq i\leq T)$ 行整数表示第 $i$ 组数据的最小曼哈顿距离最大值。