Coin Flip Transformation

There is a row of coins on the table. Each coin shows either heads or tails. The head is represented by * and the tail by o (the letter o, not the digit zero). For example, a possible arrangement is **oo***oooo. In one move, you can flip two adjacent coins simultaneously. Flipping a coin means converting * to o and o to *.

Given an initial state and a target state, determine the minimum number of moves required to transform the initial state into the target state, if it is possible at all. If it is impossible to achieve the target configuration using the allowed moves, output -1.

The effect of each move on the coins can be described by the following system over \(\mathbb{F}_2\). Let the state be represented as an array \(s_1, s_2, \dots, s_n\) where \(s_i=1\) if the coin is heads (*) and \(0\) if the coin is tails (o). Define \(d_i=1\) if the coin differs between the target and initial state, and \(d_i=0\) otherwise. For each move flipping coins \(i\) and \(i+1\), denote \(x_i\) as a binary variable indicating whether a flip was performed at that pair. Then the transformation satisfies: \[ x_1 = d_1, \quad x_{i-1}+x_i = d_i \quad (2 \le i \le n-1), \quad x_{n-1}=d_n. \] The minimal number of moves is \(\sum_{i=1}^{n-1} x_i\) if a solution exists, otherwise -1. Note that when \(n=1\), no move is allowed so the answer is 0 if the coins are already the same and -1 otherwise.

inputFormat

The input consists of two lines. The first line contains a string representing the initial state, and the second line contains a string representing the target state. Both strings have the same length and contain only the characters * and o.

outputFormat

Output a single integer which is the minimum number of moves required to transform the initial state to the target state, or -1 if it is impossible.

sample

**oo***oooo
oooo***oooo

1