Sequence Modification Operations

You are given an array \(a\) of length \(n\) consisting of positive integers. You are also given \(m\) operations. In each operation, you are given two integers \(l\) and \(r\). For every index \(i\) with \(l \le i \le r\), update \(a_i\) as follows:

[ a_i = a_i + \lfloor \log_2 a_i \rfloor ]

After performing all \(m\) operations, output the final array \(a\). The indices are 1-indexed.

inputFormat

The first line contains two integers \(n\) and \(m\), representing the length of the array and the number of operations, respectively.

The second line contains \(n\) space-separated integers, the initial values of the array \(a\).

Each of the next \(m\) lines contains two integers \(l\) and \(r\), describing an operation.

outputFormat

Output a single line containing \(n\) space-separated integers, the final state of the array \(a\) after all operations.

sample

5 1
1 2 3 4 5
2 4

1 3 4 6 5