给定一个整数 $$$m$$$ ($$$2\leq m\leq 5\cdot 10^5$$$) 和一个由小于 $$$m$$$ 的非负整数组成的数组 $$$a$$$。
回答以下形式的询问:
- $$$1$$$ $$$i$$$ $$$x$$$: 赋值 $$$a_i := x$$$
- $$$2$$$ $$$k$$$:在一次操作中,您可以选择一个元素 $$$a_i$$$ 并分配 $$$a_i := (a_i + k) \pmod m$$$$$$^{\text{∗}}$$$ — 确定是否存在某种序列(可能为零)操作来生成 $$$a$$$非递减$$$^{\text{†}}$$$。
请注意,查询 $$$2$$$ 的实例是独立的;也就是说,没有发生任何实际操作。查询 $$$1$$$ 的实例是持久的。
$$$^{\text{*}}$$$$$a\pmod m$$$ 被定义为唯一整数 $$$b$$$,使得 $$$0\leq b \lt m$$$ 和 $$$a-b$$$ 是 $$$m$$$ 的整数倍。
$$$^{\text{†}}$$$大小为$$$n$$$的数组$$$a$$$被称为非递减当且仅当$$$a_i\leq a_{i+1}$$$对于所有$$$1\leq i \lt n$$$。
输入
第一行包含一个整数 $$$t$$$ ($$$1\leq t\leq 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含三个整数,$$$n$$$、$$$m$$$ 和 $$$q$$$ ($$$2\leq n \leq 10^5$$$, $$$2\leq m\leq 5\cdot10^5$$$, $$$1\leq q\leq 10^5$$$) - 的大小数组 $$$a$$$、整数 $$$m$$$ 和查询数量。
每个测试用例的第二行包含 $$$n$$$ 整数,$$$a_1,a_2,\dots,a_n$$$ ($$$0\leq a_i \lt m$$$)。
然后是 $$$q$$$ 行。每行具有以下形式之一:
- $$$1$$$ $$$i$$$ $$$x$$$ ($$$1\leq i\leq n$$$, $$$0\leq x \lt m$$$)
- $$$2$$$ $$$k$$$ ($$$1\leq k \lt m$$$)
保证所有测试用例的 $$$n$$$ 总和和 $$$q$$$ 总和不超过 $$$10^5$$$。
输出
对于查询 $$$2$$$ 的每个实例,在单行上输出“是“如果存在一些(可能为零)操作序列使$$$a$$$非递减,并且”NO”否则。
您可以在任何情况下输出答案(大写或小写)。例如,字符串“是", "是的", "是“,和”是”将被视为积极响应。
示例
输入复制
27 6 64 5 2 2 4 1 02 41 4 52 42 31 7 22 38 8 30 1 2 3 4 5 6 72 41 3 42 4
输出复制
YES NO NO YES YES NO
注意
在第一个示例中,数组最初为:
| 4 | 5 | 2 | 2 | 4 | 1 | 0 |
通过对 $$$a_1$$$ 应用操作两次,对 $$$a_2$$$ 应用操作两次,对 $$$a_5$$$ 应用操作一次,对 $$$a_6$$$ 应用操作两次,对 $$$a_7$$$ 应用操作一次,数组变为:
| 0 | 1 | 2 | 2 | 2 | 3 | 4 |
第二次查询后,数组变为:
| 4 | 5 | 2 | 5 | 4 | 1 | 0 |