题目描述
有一个非负整数序列 $a_1,a_2\cdots a_n$,你需要维护两种操作:
给定正整数 $k$,把所有 $a_i$ 赋值为 $a_i+k$
给定正整数 $k$,把所有 $a_i$ 赋值为 $a_i\bmod k$
问所有操作结束时每个位置的值。
输入格式
第一行两个整数 $n,q$。
第二行 $n$ 个整数,表示数列 $a$ 的初始值。
接下来 $q$ 行,每行两个树 $opt,k$。其中 $opt=1$ 时为加法操作,$opt=2$ 时为取模操作。
输出格式
一行 $n$ 个整数表示 $a$ 最后的值。
样例
下发四个样例,分别满足子任务 $1,2,3,4$ 的限制。
数据范围
共十个 subtask,每个 10 分。
对于所有数据 $a_i\leq 10^9$,记 $\max(n,q)=N$。
对于 $Subtask1:\ n\leq 5\times 10^3$。
对于 $Subtask2-4:\ n\leq 5\times 10^4$。
对于 $Subtask5-7:\ n\leq 10^5$。
对于 $Subtask8-10:\ n\leq 2\times 10^5$。
对于 $Subtask2,5,8$ 保证 $opt=2$。
对于 $Subtask3,6,9$ 保证 $a_i=i$。
数据有合理的子任务依赖。