D 青蛙学分块

题目描述

学霸题，数分青蛙块。

青蛙们有一个长度为 $n$ 的排列 $\{1,2,...,n-1,n\}$，其中 $n$ 是 $2$ 的次幂。

青蛙要依次进行 $m$ 次操作：

• 第 $i$ 次操作时，青蛙会将排列分成 $\frac{n}{2^{i-1}}$ 个长度为 $2^{i-1}$ 个块，将第 $j$ 块和第 $(j+1)$ 块交换位置，其中 $1\leq j\leq \frac{n}{2^{i-1}}$，且 $j$ 为奇数。

青蛙一共要解决 $T$ 组询问，每次询问给定 $n,m,l,r$，求经过 $m$ 操作后的排列第 $l$ 到 $r$ 个数的和。

输入格式

第一行，一个正整数 $T$，代表询问组数。

接下来 $T$ 行，每行四个正整数 $n,m,l,r$．

输出格式

$T$ 行，每行一个正整数表示答案。

样例输入

2
8 1 2 4
8 2 2 4

样例输出

8
6

数据范围

• 对于前 $10\%$ 的数据：$m=0$；
• 对于另外 $20\%$ 的数据： $l=1,r=n$；
• 对于前 $40\%$ 的数据：$n\leq 10^5,T\leq 100$；
• 对于前 $60\%$ 的数据：$n\leq 10^5$；
• 对于 $100\%$ 的数据：$1\leq n\leq 2^{31},0\leq m\leq \log_2 n,1\leq l\leq r\leq n,1\leq T\leq 10^6$．