{"raw_statement":[{"iden":"statement","content":"A row of $10^9$ cigarettes are on the ground. They have never been touched by an angel before. Today the lives of those cigarettes are going to change. We index these $10^9$ cigarettes from $1$ to $10^9$.\n\n$10^9$ angels walk through the ground one-by-one. The first angel skips the first cigarette, touches the second, skips the third, touches the fourth and so on. After the first angel finishes, the second angel arrives. The second angel skips the first two cigarettes, touches the next two cigarettes and so on. The third angel arrives when the second angel finishes and so on. For $i = 1, \\\\dots, 10^9$, the $i$th angel skips the first $2^(i -1)$ cigarettes, touches the next $2^(i -1)$ cigarettes, skips the next $2^(i -1)$ cigarettes, and so on. Once the $i$th angel has touched or has skipped the last cigarette, he then leaves. After the last angel leaves, no other angel comes and the cigarettes are never touched by any angel again.\n\nBetween two cigarettes on the ground, the holier cigarette between them is the one which has been touched more times. If the two cigarettes we are comparing have been touched the same number of times, then the holier one between the two of them is the one which has been touched more recently.\n\nLet $L$ and $R$ be two integers, with $1 <= L <= R <= 10^9$. We can rank the set of cigarettes with indices $L, L + 1, \\\\dots, R$ according to holiness. We define the positive integer $r_k$ to be index of the $k$th holiest cigarette in this set. In other words, cigarette $r_k$ is the $k$th holiest in the set. Given two integers $a$ and $b$ with $a <= b$, find the sum of $r_a + r_{a + 1} + \\\\dots + r_b$.\n\nThe first line of input contains $T$, the number of test cases.\n\nEach test case consists of one line containing four space-separated integers $L$, $R$, $a$, $b$, respectively.\n\nFor each test case, output one line containing the answer to that test case.\n\n$1 <= T <= 5 times 10^4$\n\n$1 <= L <= R <= 10^9$\n\n$1 <= a <= b <= R -L + 1$\n\n*Subtask 1* (10 points):\n\n$R <= 100$\n\n*Subtask 2* (15 points):\n\n$R <= 2 times 10^5$\n\n$L$ will be the same across all test cases.\n\n$R$ will be the same across all test cases.\n\n*Subtask 3* (30 points):\n\n$L$ and $R$ are powers of 2.\n\n$a = b$\n\n*Subtask 4* (25 points):\n\n$a = b$\n\n*Subtask 5* (20 points):\n\nNo additional constraints.\n\nWe will examine the second sample test case.\n\nFor the first query, we are concerned with the cigarettes indexed 2 to 11. Then, if we were to sort _only these_ cigarettes according to their holiness, we must find the sum of the 6th holiest, 7th holiest, and 8th holiest cigarettes. You can verify that $r_6 = 4$, $r_7 = 9$, and $r_8 = 5$. We see that cigarette 4 is holier than cigarette 9, since cigarette 4 was touched by two angels while cigarette 9 was only touched by one angel. Meanwhile, cigarette 9 and cigarette 5 were both only touched by one angel. However, we can show that cigarette 9 was touched by the 4th angel, while cigarette 9 was touched by the 3rd angel, and so cigarette 9 must be the holier one since it was touched more recently. Thus, $r_6 + r_7 + r_8 = 4 + 9 + 5 = 18$.\n\nFor the second query, we can verify that no cigarette in the set was touched more than 3 times, and the only cigarette to be touched exactly 3 times is cigarette 8. Thus, the holiest cigarette in the set is equal to 8, and $r_1 = 8$.\n\nFor the third query, we consider a different set of cigarettes, and we can verify that $r_{12} = 17$, $r_{13} = 9$, and $r_{14} = 5$, so $r_{12} + r_{13} + r_{14} = 17 + 9 + 5 = 31$. Notice that since the set of cigarettes is different, the ranks of cigarette 9 and cigarette 5 are different from what they were in the first query.\n\n"},{"iden":"input","content":"The first line of input contains $T$, the number of test cases.Each test case consists of one line containing four space-separated integers $L$, $R$, $a$, $b$, respectively."},{"iden":"output","content":"For each test case, output one line containing the answer to that test case."},{"iden":"scoring","content":"$1 <= T <= 5 times 10^4$$1 <= L <= R <= 10^9$$1 <= a <= b <= R -L + 1$*Subtask 1* (10 points):$R <= 100$*Subtask 2* (15 points):$R <= 2 times 10^5$$L$ will be the same across all test cases.$R$ will be the same across all test cases.*Subtask 3* (30 points):$L$ and $R$ are powers of 2.$a = b$*Subtask 4* (25 points):$a = b$*Subtask 5* (20 points):No additional constraints."},{"iden":"examples","content":"Input1\n1 1 1 1\nOutput1\nInput3\n2 11 6 8\n2 11 1 1\n2 17 12 14\nOutput18\n8\n31\n"},{"iden":"note","content":"We will examine the second sample test case.For the first query, we are concerned with the cigarettes indexed 2 to 11. Then, if we were to sort _only these_ cigarettes according to their holiness, we must find the sum of the 6th holiest, 7th holiest, and 8th holiest cigarettes. You can verify that $r_6 = 4$, $r_7 = 9$, and $r_8 = 5$. We see that cigarette 4 is holier than cigarette 9, since cigarette 4 was touched by two angels while cigarette 9 was only touched by one angel. Meanwhile, cigarette 9 and cigarette 5 were both only touched by one angel. However, we can show that cigarette 9 was touched by the 4th angel, while cigarette 9 was touched by the 3rd angel, and so cigarette 9 must be the holier one since it was touched more recently. Thus, $r_6 + r_7 + r_8 = 4 + 9 + 5 = 18$.For the second query, we can verify that no cigarette in the set was touched more than 3 times, and the only cigarette to be touched exactly 3 times is cigarette 8. Thus, the holiest cigarette in the set is equal to 8, and $r_1 = 8$.For the third query, we consider a different set of cigarettes, and we can verify that $r_(12) = 17$, $r_(13) = 9$, and $r_(14) = 5$, so $r_(12) + r_(13) + r_(14) = 17 + 9 + 5 = 31$. Notice that since the set of cigarettes is different, the ranks of cigarette 9 and cigarette 5 are different from what they were in the first query."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N = 10^9 $.  \nFor each cigarette at position $ x \\in \\{1, 2, \\dots, N\\} $, let $ f(x) $ denote the number of angels that touched it.  \nFor each angel $ i \\in \\{1, 2, \\dots, N\\} $, it touches cigarettes at positions $ x $ such that:  \n$$\n\\left\\lfloor \\frac{x - 1}{2^{i-1}} \\right\\rfloor \\equiv 1 \\pmod{2}\n$$  \nEquivalently, $ x $ lies in a block of length $ 2^{i-1} $ starting at position $ k \\cdot 2^i + 2^{i-1} + 1 $ for some integer $ k \\geq 0 $.  \n\nLet $ t(x) $ denote the index of the **last** angel that touched cigarette $ x $ (i.e., the most recent touch).  \n\n**Holiness Ordering**  \nFor two cigarettes $ x, y \\in \\{1, \\dots, N\\} $:  \n- $ x $ is holier than $ y $ if:  \n  1. $ f(x) > f(y) $, or  \n  2. $ f(x) = f(y) $ and $ t(x) > t(y) $.  \n\n**Given**  \nFor a query $ (L, R, a, b) $:  \nLet $ S = \\{L, L+1, \\dots, R\\} $.  \nSort $ S $ by holiness (descending), breaking ties by more recent touch (descending).  \nLet $ r_k $ be the index of the $ k $-th holiest cigarette in $ S $.  \n\n**Objective**  \nCompute:  \n$$\n\\sum_{k=a}^{b} r_k\n$$","simple_statement":"Given $10^9$ cigarettes indexed 1 to $10^9$, and $10^9$ angels that each touch cigarettes in a pattern: angel $i$ skips $2^{i-1}$ cigarettes, then touches $2^{i-1}$, skips $2^{i-1}$, touches $2^{i-1}$, etc.\n\nEach cigarette gets a “touch count” (how many angels touched it) and a “last touched time” (the angel index that last touched it).\n\nA cigarette is “holier” than another if:\n- It was touched more times, OR\n- If tied in touch count, it was touched more recently (higher angel index).\n\nGiven a range $[L, R]$ of cigarette indices, sort them by holiness (highest to lowest), and let $r_k$ be the index of the $k$-th holiest cigarette in this range.\n\nFor each test case, given $L, R, a, b$, compute the sum $r_a + r_{a+1} + \\dots + r_b$.\n\nYou are given $T$ test cases.","has_page_source":false}