Problem Description

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$.

Input Format

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 Format

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

5 2
2 3 4 5 6
2 3
1 1

3 4 6 5 6

Hint

This problem uses bundled testdata.

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