All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Recently Chef invented a new structure that he has called Xor Grid. It is an infinitely large grid G filled with numbers based on these three rules:
- G[1, c] = 1 for all c ≥ 1
- G[r, 1] = r for all r ≥ 1
- G[r, c] = G[r - 1, c] xor G[r, c - 1] for all r > 1 and c > 1
Now Chef is wondering, what are the xor sums of all the numbers within some specific rectangles of the Xor Grid?
NoteXor sum refers to successive xor operations on integers. For example, xor sum of integers x1, x2, x3, ..., xn will be (..((x1 xor x2) xor x3)... xor xn).
The first line of the input contains an integer T denoting the number of test cases.
For each test case, the only line of input contains four integers r1, r2, c1 and c2, where (r1, c1), (r2, c2) denotes the coordinates of top left and bottom right cells of the rectangle.
OutputFor each test case, output a single integer ― the xor sum of all the numbers within G[r1..r2, c1..c2].
- 1 ≤ T ≤ 10 000
- 1 ≤ r1 ≤ r2 ≤ 1018
- 1 ≤ c1 ≤ c2 ≤ 1018
Input: 5 1 1 71 93 23959042 23959042 1 1 1 2 1 2 2 7 3 6 5 8 5 8 Output: 1 23959042 1 6 4
ExplanationExample case 1. First row is filled with ones, so our rectangle contains 23 ones and their xor sum is one. Example case 2. Here we have a rectangle that consists of one cell G[23959042, 1] = 23959042. Example case 3. The rectangle contains four numbers: 1 1 2 3 and their xor sum is 1.
|Tags||alex_2oo8, bitwise-operatn, cook78, easy-medium, fractals, maths|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.