题目描述

给定长度为 $n$ 的序列 $a$，接下来 $m$ 次操作，每次操作形如：

• 给定 $l,r$，对于 $i \in [l,r]$，令 $a_i \leftarrow a_i + \lfloor \log_2 a_i \rfloor$。

$m$ 次操作后，输出 $a$ 序列。

输入格式

第一行两个正整数 $n$ 和 $m$。

接下来一行 $n$ 个正整数，第 $i$ 个表示 $a_i$。

接下来 $m$ 行，每行两个正整数 $l$ 和 $r$。

输出格式

一行 $n$ 个正整数，第 $i$ 个表示 $a_i$。相邻正整数间用空格分隔。

5 2
2 3 4 5 6
2 3
1 1

3 4 6 5 6

提示

本题目采用捆绑测试。

特殊性质 A：$a_i \le 100$。

对于 $100 \%$ 的数据，满足 $1 \le n,m \le 10^5$，$1 \le a_i \le 10^5$，$1 \le l \le r \le n$。