← 返回题目列表

Codeforces · 2220/B

B. OIE 游览

中文机器翻译题面 查看原题

Hector 正在参加西班牙信息学奥林匹克竞赛,访问拉科鲁尼亚,但他非常想偷偷去见他的朋友 Gustavo、Esomer 和 Dani。为此,他必须穿过一条由 $$$n$$$ 志愿者守卫的道路,这些志愿者排成一排,编号从 $$$1$$$ 到 $$$n$$$;第 $$$i$$$ 位志愿者看守位置 $$$i$$$。

每个志愿者都有一个内部计时器。最初(在第二个 $$$0$$$ 处),第 $$$i$$$ 个志愿者的计时器的值为 $$$a_i$$$。每秒,所有计时器都会增加 $$$1$$$。一旦计时器达到 $$$m$$$,它就会回到 $$$0$$$。具体来说,在第二个$$$x$$$时,第$$$i$$$个志愿者的计时器显示值$$$(a_i + x)\pmod m$$$。

第 $$$i$$$ 位志愿者仅在计时器恰好为 $$$0$$$ 时监视位置 $$$i$$$。在其他任何时候,他们都会分心,不会注意到赫克托。

Hector 从位置 $$$0$$$ 开始,位于所有志愿者的左侧。为了逃脱,他必须到达位置$$$n+1$$$。在 结束 每一秒,赫克托可以选择留在当前位置、向左移动一个位置或向右移动一个位置。请注意,Hector 不能走到 $$$0$$$ 位置的左侧。

赫克托被抓住当且仅当, 开始 一秒,他位于位置$$$i$$$ ($$$1 \le i \le n$$$),第$$$i$$$个志愿者的计时器为$$$0$$$。

确定赫克托是否存在一种策略,可以通过所有志愿者并逃脱而不被抓住。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例由两行组成:

  • 第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$2 \le m \le 10^9$$$) — 志愿者数量和计时器的周期长度。
  • 第二行包含$$$n$$$整数$$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \lt m$$$),其中$$$a_i$$$表示第$$$i$$$个志愿者的计时器在$$$t=0$$$时的初始值。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印一行包含“是“或”NO”,代表赫克托能否逃脱。您可以在任何情况下输出答案(上限或下限)。例如,字符串“是", "是的", "是“,和”是”将被视为积极响应。

示例

输入
复制

6
8 5
0 4 0 2 1 0 0 3
6 2
1 0 1 0 1 0
6 2
1 1 1 1 0 1
2 10
6 9
2 2
0 1
5 1000000000
1 2 3 4 999999999

输出
复制

YES
YES
NO
YES
YES
YES

注意

  • 情况 1:Hector 可以每秒向右移动,而无需等待或向左移动并逃脱,因为不存在 $$$i$$$ 使得 $$$(a_i + i) \pmod m = 0$$$。

  • 情况2:一种可能的策略是在起始位置等待一秒钟,然后每秒向右移动一次,不再进一步等待或向左移动。