Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Xenon is a great alchemist. Recently, he has decided to perform a special type of transmutation. But to make that happen, he needs a lot of rhodium, the most precious metal in the world. After a huge exploration, he has found a vault of rhodium on a far island. The vault has a strange mechanism. There is a keypad outside the vault. Anyone can insert a decimal number into the vault using that keypad. If a number $X$ is inserted, the following happens:

The number $X$ is converted into a binary number. The converted binary number does not have any leading zeros.

In the converted binary number, for any $i^{th}$ digit from the left, if there exists $(i+1)^{th}$ digit:

Xenon gets $a$ amount of rhodium if the $i^{th}$ digit is $0$ and the $(i+1)^{th}$ digit is $0$.

Xenon gets $b$ amount of rhodium if the $i^{th}$ digit is $0$ and the $(i+1)^{th}$ digit is $1$.

Xenon gets $c$ amount of rhodium if the $i^{th}$ digit is $1$ and the $(i+1)^{th}$ digit is $0$.

Xenon gets $d$ amount of rhodium if the $i^{th}$ digit is $1$ and the $(i+1)^{th}$ digit is $1$.

For example, if Xenon inserts $14$ into the vault, the binary form will be $1110$. So, Xenon will receive $d$ amounts of rhodium for “$11$“ twice as “$11$“ occurs two times in the binary. He will also receive $c$ amount of rhodium for “$10$” in the binary. So, the total amount of rhodium Xenon will receive is = $d+d + c$.

Now, Xenon wants to know what is the total amount of rhodium he can get if he inserts all the numbers between $L$ and $R$ inclusive.

The first line contains an integer $T(1\leq T\leq 5\times10^5)$, the number of the test cases.

In each test case, the first line contains two space-separated integers $L(1\leq L\leq 10^{15})$ and $R(L\leq R\leq 10^{15})$. The next line contains four space-separated integers $a, b, c, d (0\leq a, b, c, d \leq 100)$ described in the statement.

In each test case, print an integer in a line containing the total amount of rhodium Xenon can get if he inserts all the numbers between $L$ and $R$ inclusive.

Input | Output |
---|---|

2 1 2 5 1 3 2 2 5 4 12 3 3 | 3 28 |

71% Solution Ratio

YouKnowWhoEarliest,

Wojciech.324122Fastest, 0.5s

Wojciech.324122Lightest, 10 MB

tanzim_bnShortest, 873B

Login to submit

At first, let’s simplify the problem a little bit. If we know the answer ARA_RAR for [1,R][1, R][1,...

Toph uses cookies. By continuing you agree to our Cookie Policy.