Minimum Cost Transformation

You are given three integers \( n, s, t \) with \(0 \le s,t < 2^n\). You can perform a sequence of operations to transform s into t.

In each operation, you choose a nonnegative integer \( x \) and set \( s = x \) subject to the following conditions:

• \( x < 2^n \).
• \( s \lor x = 2^n - 1 \), where \( \lor \) denotes the bitwise OR operation.
• You pay a cost of \( s \oplus x \), where \( \oplus \) denotes the bitwise XOR operation.

Determine the minimum total cost needed to transform \( s \) into \( t \). It is guaranteed that it is always possible to make \( s \) equal to \( t \) using a sequence of valid operations.

Explanation:

The key observation is that the condition \( s \lor x = 2^n-1 \) forces every bit that is 0 in s to become 1 in x. Thus, for each bit position, if it is 0 in the current value, it must be flipped to 1 in the next step. Later, if you need that bit to be 0 in the final answer, you have to flip it from 1 to 0 (which is allowed only when the current bit is 1). Therefore, the minimal cost can be determined independently for each bit as follows:

• If the \( i\)-th bit is 0 in s and 1 in t, the only option is to flip it from 0 to 1 (cost = \(2^i\)).
• If the \( i\)-th bit is 1 in s and 1 in t, no change is needed (cost = 0).
• If the \( i\)-th bit is 1 in s and 0 in t, you can flip it directly from 1 to 0 (cost = \(2^i\)).
• If the \( i\)-th bit is 0 in s and 0 in t, you must first flip it from 0 to 1 (cost = \(2^i\)) and then later flip it back from 1 to 0 (cost = \(2^i\)), totaling \(2\cdot2^i\).

The overall minimum cost is the sum of the costs for each bit position from \(i = 0\) to \(n-1\).

The following implementation computes the answer by iterating over each bit and summing the corresponding costs.

inputFormat

The input consists of a single line containing three space-separated integers: \( n\), \( s\), and \( t \).

\(0 \le s,t < 2^n\).

outputFormat

Output a single integer representing the minimum total cost required to transform \( s \) into \( t \) using the allowed operations.

sample

2 0 2

4