Logo Universal Online Judge

UOJ

时间限制:2 s 空间限制:512 MB
Statistics

题目描述

有一个非负整数序列 $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$。

数据有合理的子任务依赖。