Update

Hydro 时限太小，TLE 了……

---

好，管理员开大时限了，现在可以通过。

---

看起来很牛逼的题目。

但是 $x>\!\!>\!\!>k$ 是什么迷惑行为啊。

以下 $x$ 均对 $k$ 取模。

---

你要从 ${\rm Z}_k^d$ 中指定的 $n$ 个向量 ${\bf x}_1,{\bf x}_2,\dots,{\bf x}_n$ 中，取出两个不同向量 ${\bf a},{\bf b}$，使 ${\bf a}^{\operatorname T}{\bf b}=\overline0$，其中 $k\in\{2,3\}$。

你要思索。

设 $A=\begin{bmatrix}{\bf x}_1&{\bf x}_2&\dots&{\bf x}_n\end{bmatrix}$。

则 ${\bf x}_i^{\operatorname T}{\bf x}_j=0\Leftrightarrow(A^{\operatorname{T}}A)_{ij}=\overline0$。

设 $B=A^{\operatorname{T}}A$，我们只用找到一个不在其对角线上的零点。

如何尝试找到一行在某个非对角线位置取 $0$？

不为左了，参考了 Luogu 题解。

---

$k=2$

随机取 ${\bf y}\in{\rm Z}_2^n$，计算 ${\bf p}=B{\bf y}$，这个可以在 $O(nd)$ 内实现。

设 ${\bf q}=B(\overline1,\overline1,\dots,\overline1)$。

若 $\exist_a,{\bf q}_a-{\bf p}_a\neq(1-{\bf y}_a)(1-B_{i,i})+\operatorname{cnt}_0({\bf y})$，则导出矛盾，直接对着 $a$ 枚举另一半就好了。

成功率不多分析，可以通过就是了，应该还蛮高的。

---

$k=3$

这个太牛了，上面那个我还能自己发明，下面这个平方则根本就想不到啊！！！

设 ${\bf p}_i=\sum_jB_{ij}^2{\bf y}_j$，那么 $1,2$ 都变为 $1$。

则 ${\bf p}_i=\sum_jB_{ij}{\bf y}_jB_{ji}$。（$B$ 为对称矩阵）

即 ${\bf p}_i=(B\operatorname{diag}\{{\bf y}_1,{\bf y}_2,\dots,{\bf y}_n\}B)_{ii}$。

对这个如何快速计算？

$$(B\operatorname{diag}\{{\bf y}_1,{\bf y}_2,\dots,{\bf y}_n\}B)_{ii} \\=(A'(A\operatorname{diag}\{{\bf y}_1,{\bf y}_2,\dots,{\bf y}_n\}A')A)_{ii} $$

可以在 $O(nd^2)$ 时间内算出 $\bf p$ 的每一项。

类似的，定义 $\bf y,p,q$。

若 $\exist_a,{\bf q}_a-{\bf p}_a\neq(1-{\bf y}_a)(1-B_{i,i}^2)+\operatorname{cnt}_0({\bf y})$，则导出矛盾。