P11894 "LAOI-9" Update

Given a sequence $a$ of length $n$, there are $m$ operations. Each operation is as follows: - Given $l, r$, for $i \in [l, r]$, set $a_i \leftarrow a_i + \lfloor \log_2 a_i \rfloor$. After all $m$ operations, output the sequence $a$.

The first line contains two positive integers $n$ and $m$. The next line contains $n$ positive integers, where the $i$-th number is $a_i$. The next $m$ lines each contain two positive integers $l$ and $r$.

Output one line with $n$ positive integers, where the $i$-th number is $a_i$. Adjacent integers are separated by spaces.

**This problem uses bundled testdata**. | Subtask ID | $n, m \le$ | Special Property | Score | | :-----: | :------: | :------: | :------: | | $1$ | $10^3$ | None | $30$ | | $2$ | $10^5$ | A | $20$ | | $3$ | $10^5$ | None | $50$ | Special property A: $a_i \le 100$. For $100\%$ of the testdata, $1 \le n, m \le 10^5$, $1 \le a_i \le 10^5$, and $1 \le l \le r \le n$. Translated by ChatGPT 5