时空限制

1S/512M

题目描述

给定一个长度为 $n$ 的数组 $A$ 和 $Q$ 次操作。操作有两种类型：

1. $1\ x$：对于数组 $A$ 中当前是奇数的每个数字，将它的值加上 $x$。
2. $2\ x$：对于数组 $A$ 中当前是偶数的每个数字，将它的值加上 $x$。

在执行完所有 $Q$ 次操作后，输出整个数组 $A$。

格式

输入格式

输入的第一行包含两个整数 $n, Q$，分别表示数组的长度和操作的次数。

第二行包含 $n$ 个整数 $A_1, A_2, \ldots, A_n$，表示数组的初始元素。

接下来 $Q$ 行，每行包含两个整数 type x，描述一次操作。type 为 $1$ 或 $2$，分别对应题目描述中的两种操作类型。

输出格式

输出一行，包含 $n$ 个整数，用空格隔开，表示执行完所有操作后最终的数组。

样例

样例输入 #1

5 3
1 2 3 4 5
1 3
1 5
2 10

样例输出 #1

14 12 16 14 18

样例解释 #1

初始数组为 $[1, 2, 3, 4, 5]$。

1. 第一次操作 $1 \; 3$：

   • 当前数组中的奇数是 $1, 3, 5$。
   • 它们分别加上 $3$，变为 $4, 6, 8$。
   • 数组变为 $[4, 2, 6, 4, 8]$。注意，此时数组中所有数都变成了偶数。

2. 第二次操作 $1 \; 5$：

   • 当前数组 $[4, 2, 6, 4, 8]$ 中没有奇数。
   • 所以这次操作不会改变任何元素。
   • 数组仍然是 $[4, 2, 6, 4, 8]$。

3. 第三次操作 $2 \; 10$：

   • 当前数组中的偶数是 $4, 2, 6, 4, 8$。
   • 它们都加上 $10$。
   • 数组变为 $[14, 12, 16, 14, 18]$。

所有操作结束后，最终的数组为 $[14, 12, 16, 14, 18]$。

数据规模

对于 $40\%$ 的数据，$1 \leq n, Q \leq 2 \times 10^3$。

对于 $100\%$ 的数据，$1 \leq n, Q \leq 2 \times 10^5$，$1 \leq A_i, x \leq 10^9$，操作类型 type 一定是 $1$ 或 $2$。