注意如果 $x$ 是二次剩余则 $x^{(p-1)/2}\equiv 1\pmod p$，否则 $x^{(p-1)/2}\equiv -1\pmod p$。

令 $g(x)=x^{(p-1)/2}$，那么 $w_i=w_j=w_k$ 的条件可以写成 $(g(i)g(j)+g(j)g(k)+g(i)g(k)+1)/4$（如果认为 $g(x)$ 的值是 $\pm 1$ 的话）。

我们先枚举 $d=j-i$，然后对上式的每一项分别算。例如 $g(i)g(j)$ 的和就是 $\sum_{1\le i< p-2d}g(i)g(i+d)$。我们先忽略 $i< p-2d$ 的限制，变成 $1\le i< p$，并且我们认为 $g(0)=0$。那么 $g(i)g(i+d)\equiv (i(i+d))^{(p-1)/2}\pmod p$，这是一个关于 $i$ 的 $p-1$ 次多项式。而因为是对于 $1\le i< p$ 求和，所有小于 $p-1$ 次的部分的总和其实是 $0$，所以 $\sum_{1\le i< p}g(i)g(i+d)\equiv -1\pmod p$。因为每一项的绝对值不超过 $1$，并且至少有一项是 $0$，所以这个求和的值不可能是 $p-1$，只可能是 $-1$。

现在我们需要减去多算的值，注意到多算的值只依赖于 $g(-2t),\ldots,g(2t)$ 的值，我们可以先预处理出这些值。要减去的项形如 $g(i)g(i+d)$ 或 $g(i)g(i+2d)$，枚举 $i$ 之后，可能的 $d$ 是一个区间，可以预处理前缀和后 $O(1)$ 求值。

总时间复杂度 $O(t\log p)$。瓶颈在于计算 $g(-2t),\ldots,g(2t)$ 的值，注意到 $g(-x)$ 的值可以由 $g(x)$ 的值求出，可以减少一半的常数。也可以用素数筛做到 $O(t\log p/\log t)$ 的复杂度，但因为是多组数据，最坏情况下仍然是 $(\sum t)\log p$。