Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3845
Fixed Point

Time Limit: 2 Seconds      Memory Limit: 65536 KB

In mathematics, a fixed point (sometimes shortened to fixpoint, also known as an invariant point) of a function is an element of the function's domain that is mapped to itself by the function. A set of fixed points is sometimes called a fixed set. That is to say, c is a fixed point of the function f(x) if and only if f(c) = c. This means f(f(...f(c)...)) = fn(c) = c, an important terminating consideration when recursively computing f. For example, if f is defined on the real numbers by f(x) = x2 - 3x + 4, then 2 is a fixed point of f, because f(2) = 2.

Bob has three funtions define on nonegative integers, A(x) = cx, E(x) = cx, and O(x) = cx, where ∧ means bitwise AND operation, ⊕ means bitwise XOR operation, ∨ means bitwise OR operation and c is an integer constant.

Bob wants to know the number of fixed points for each function which satisfy the following conditions:

  1. x is no less than L and x is also no greater than R.
  2. Let c0 be the number of 0-bit in x's binary representation and c1 be the number of 1-bit in x's binary representation. Then we have |c0 - c1| ≤ k.

You are given three integers L, R and k, please tell Bob the answer.

Note: x is a 32-bit integer, that is x's binary representation only has 32 bits.


The first line of input contain an integer T (T ≤ 10000), which is the number of cases.

Then next T line, each line contain four integers L, R, c and k (0 ≤ LR < 232, 0 ≤ c < 232, 0 ≤ k ≤ 32), separated by spaces.


For each test case, print a line containing the test case number (beginning with 1) followed by three integers, indicating the number of fixed points for function A(x), E(x) and O(x), separated by one space.

Sample Input

1 10 1 32
1 100 43 32
1 200 43 20

Sample Output

Case 1: 1 0 5
Case 2: 15 0 4
Case 3: 0 0 7

Author: LIN, Xi
Source: ZOJ Monthly, January 2015
Submit    Status