SillyDarkGK has two type of numbers:
type1. 2^x. (2, 4, 8, 16, …)
type2. -(2^x). (-2, -4, -8, -16, …)
He wants a new number S, for getting S, he should choose some numbers that the sum of them is S.
For example, if SillyDarkGK wants 5, he can use 2, 2, -1, -1, -1, 8 and -4 to get it. (He can use number arbitrary times.)
(S is very big, so we will give you a 01-string to describe it.)
Choosing is boring, so SillyDarkGK wants to choose numbers as fewer as possible. To increase the difficulty, SillyDarkGK can’t use some special numbers.
(We will also give you two 01-string to describe what you can’t use.)
it’s guaranted that there is at least one way to solve it and answer won’t exceed
1e9.