Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
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.

#### Input

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.

#### Output

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

3
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