题目描述

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

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