We are given a 64-bit unsigned integer x. Number its binary bits from least significant to most significant as positions 0, 1, 2, ..., 63.

For a given positive integer k, we define the answer for the pair (x, k) as follows:

• If, in the binary representation of x, there exists a k-th 1 bit when scanning from least significant bit to most significant bit, then the answer is the position of that 1 bit;
• Otherwise (if x has fewer than k bits set to 1), the answer is 64.

You must generate many pairs (x, k) according to the given rules, compute the answer for each pair, and output the sum of all answers.

Input

The input consists of two integers: the number of queries $n$ and the pseudo-random seed $seed$. You must generate all queries from the seed. The generation process is given in the reference code below.

Output

Output a single non-negative integer: the sum of the answers over all $n$ queries.

Sample

Input

2048 60576

Output

100000

Reference Code

You may base your solution on the following code; you only need to complete the query function. You are also allowed to modify the code in any way if you wish.

#include <iostream>
int n;
using u64 = unsigned long long;
u64 seed, ans = 0;

u64 next(u64 &x) {
    x ^= x << 13;
    x ^= x >> 17;
    x ^= x << 5;
    return x;
}

int query(u64 x, int k) {
    // TODO: implement this function
}

int main() {
    std::cin >> n >> seed;
    for (int i = 0; i < n; ++i) {
        u64 x = next(seed);
        int k = (next(seed) & 63) + 1;
        ans += query(x, k);
    }
    std::cout << ans << '\n';
}

Subtasks

• Subtask 1 (0 points): $1 \le n \le 10^5$
• Subtask 2 (1 point): $1 \le n \le 10^8$
• Subtask 3 (7 points): $1 \le n \le 2\times 10^8$
• Subtask 4 (8 points): $1 \le n \le 3\times 10^8$
• Subtask 5 (9 points): $1 \le n \le 4\times 10^8$
• Subtask 6 (10 points): $1 \le n \le 5\times 10^8$
• Subtask 7 (11 points): $1 \le n \le 6\times 10^8$
• Subtask 8 (12 points): $1 \le n \le 7\times 10^8$
• Subtask 9 (13 points): $1 \le n \le 8\times 10^8$
• Subtask 10 (14 points): $1 \le n \le 9\times 10^8$
• Subtask 11 (15 points): $1 \le n \le 10^9$