P12389 COmPoUNdS

小 S 因为某些原因对区间加区间取模情有独钟，他造了一些这样的题但是基本上都不会做。有一天小 S 误食了一点冰红茶突然灵感迸发把所有题都秒了，于是趁着药效他随便选了一道题造了数据，然而药效过了后他也不知道怎么做了，所以请你帮他写一下标程，事成送你一瓶冰红茶。

给定正整数 $n,k,q$ 和一个长度为 $n$ 的序列 $a$，$q$ 次操作或询问： - `1 l r c`，对于每个 $i\in[l,r]$，令 $a_i\gets(a_i+c)\bmod k$。 - `2 l1 r1 l2 r2`，判断 $a$ 的两个长度相同的子段 $a_{l_1\cdots r_1},a_{l_2\cdots r_2}$ 是否相等。

无

无

**本题采用捆绑测试及子任务依赖。** | 子任务编号 | 分值 | 特殊限制 | 依赖子任务 | 时间限制 | | :---: | :---: | :---: | :---: | :---: | | $1$ | $10$ | $n,q\le 10^3$ | | $\text{1.5 s}$ | $2$ | $20$ | $k=2$ | | $\text{2.5 s}$ | $3$ | $20$ | $n\le10^5$ | $1$ | $\text{1.5 s}$ | $4$ | $50$ | 无特殊限制 | $1,2,3$ | $\text{2.5 s}$ 对于全部数据，$1\le n,q\le 10^6$，$2\le k\le 10^6$，$0\le a_i,c