To enter the spaceship security system, the astromechanical droid R2-D2 uses a secret cryptographic algorithm, one step of which solves the following problem:

Consider a thin paper strip with n = 2^k cells located in one row. The cells are numbered 0 through n - 1. Fold the strip in half, the right half under the left one, so that the cell numbered 2^k - 1 - j will be above the cell numbered 2^k - 1 + j - 1 for all j from 1 to 2^k - 1. Then fold the resulting strip, which has how length 2^k - 1, again and again in the same way until the length of the strip is one. In the resulting folded strip, the cells are placed above each other in some order. Let the sequence a₀, a₁, ..., a_n - 1 be the numbers of the cells from top to bottom.

When the droid connects to the spaceship system, it is given an integer n, and after that, it is asked several queries to get verified. Each query is a segment [l, r] (0 ≤ l ≤ r < n) for which the droid must compute the following expression, in which operations  +  and alternate:

R2-D2 argued with C-3PO that the latter couldn't solve this problem. C-3PO is a protocol droid, it knows six million forms of communication, but nothing about cryptography. Help him to solve the problem in order to surprise R2-D2.

In order to emulate a security system, R2-D2 suggested an algorithm for choosing the segments [l, r]. He also suggested to check only the results of hashing F(l, r), but not the values F(l, r) themselves. Let the queries be numbered 0 through m - 1. Then these values are computed as follows:

• ;
• ;
• .

Here, h is the value of the hash function, and h₀ = 0. Your task is to compute the final hash value h_m.