1011. 今晚吃电脑配件

题目描述

白井黑子有 $n$ 个电脑配件，质量分别为 $x_1,x_2,\ldots,x_n$。

现在有一个秤，每次可以测出两个电脑配件的质量之和。也就是说，每次测量结果是一个方程：

$$x_i+x_j=2c.$$

由于食用了电脑配件，白井黑子的测量结果不一定准确。所以对于每次测量结果，你需要判断它此时是否有可能是正确的。

也就是说，如果存在一组实数 $x_1,x_2,\ldots,x_n$ 同时满足当前测量结果和之前被认为正确的全部测量结果，则认为该结果正确。被认为错误的测量结果不会对之后的询问产生任何影响。注意，因为电脑配件可能由奇异物质组成，所以 $x_i$ 可能是负的。

询问采用如下方式加密：在每组数据开始时，令 $k=0$，其中 $k$ 表示当前已经被保留的询问数。对于输入的一组整数 $a,b,d$，实际询问中的 $i,j,c$ 为

$$\begin{aligned} i&=(a+k-1)\bmod n+1,\\ j&=(b+k-1)\bmod n+1,\\ c&=(d+k)\bmod 10^9+1. \end{aligned}$$

如果此次询问的测量结果正确，则令 $k$ 增加 $1$；否则 $k$ 不变。这里，$u\bmod v$ 表示 $u$ 除以 $v$ 所得的非负余数。

输入格式

本题包含多组测试数据。

首先在第一行输入一个整数 $T$（$1\le T\le 10^6$）表示测试数据组数。

接下来对于每一组测试数据：

第一行包含两个整数 $n$ 和 $m$（$1\le n,m\le 10^6$），分别表示变量个数和询问次数。

接下来的 $m$ 行中的第 $q$（$1\le q\le m$）行包含三个整数 $a_q,b_q,d_q$（$1\le a_q,b_q\le n$，$0\le d_q<10^9$），表示一条经过加密的询问。解码方式见题目描述。

数据保证所有测试数据的 $n$ 之和与 $m$ 之和均不超过 $10^6$。

输出格式

对于每次询问输出一行。如果该询问被保留，输出 Yes；否则输出 No。

样例输入

1
3 5
1 2 2
1 2 3
2 1 999999999
1 1 999999997
1 3 999999998

样例输出

Yes
Yes
Yes
No
Yes

提示

样例中，解码后的前两次询问分别为 $x_1+x_2=6$ 和 $x_2+x_3=10$， 此时存在同时满足它们的一组实数，故它们均被保留。

第三次询问解码为 $x_1+x_3=4$，保留后可以推出 $x_1=0,x_2=6,x_3=4$。第四次询问解码为 $x_1+x_1=2$，由于它与已有测量结果矛盾，因此被跳过，$k$ 保持为 $3$。最后一次询问再次解码为 $x_1+x_3=4$，符合已有结果，因此被保留。

来源：2026杭电多校-测试专用（南外） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1235&pid=1011