Logarithmic Transformation Sum Queries

Log Master, also known as Log 大侠, is famous for his mastery over logarithms with base 2. One day, his friend drd comes to him with a sequence of integers and a set of transformation queries. For each query, drd selects a subarray of the sequence (using 1-indexed positions) and asks Log Master to transform every number x in this subarray into

\( \lfloor\log_2(x) + 1\rfloor \),

where \( \lfloor \cdot \rfloor \) denotes the floor function. After each transformation, you are required to output the sum of the current sequence.

Note: The operation is performed sequentially, updating the sequence for subsequent queries.

inputFormat

The first line contains two integers \( n \) and \( q \) representing the length of the sequence and the number of queries.

The second line contains \( n \) space-separated integers representing the initial sequence.

Each of the next \( q \) lines contains two integers \( l \) and \( r \) (1-indexed) which represent the bounds of the subarray to be transformed.

outputFormat

For each query, output a single line containing the sum of the sequence after performing that query.

sample

3 1
3 4 2
1 3

7