Медузе даны целые неотрицательные числа \(a\), \(b\), \(c\), \(d\) и \(m\). Первоначально \((x,y)=(a,b)\). Медуза хочет выполнить несколько операций так, чтобы получилось \((x,y)=(c,d)\).
Одна операция заключается в выполенении одного из следующих действий:
- \(x := x\,\&\,y\),
- \(x := x\,|\,y\),
- \(y := x \oplus y\),
- \(y := y \oplus m\).
Здесь \(\&\) обозначает побитовую операцию И, \(|\) обозначает побитовую операцию ИЛИ, \(\oplus\) обозначает побитовое исключающее ИЛИ.
Медуза хочет узнать минимальное количество операций, после которого можно получить \((x,y)=(c,d)\).
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное количество операций. Если требуемые значения не достижимы, то вместо этого выведите \(-1\).
Примечание
В первом наборе входных данных мы можем выполнить операцию \(y = x \oplus y\).
Во втором наборе входных данных получить \((x,y)=(1,2)\) с помощью какой-либо последовательности операций невозможно.
В третьем наборе входных данных можно выполнить операцию \(x = x\,\&\,y\), а после \(y = y \oplus m\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10
1 0 1 1 1
3 3 1 2 1
1 6 0 7 1
2 4 4 9 8
21 4 0 17 28
50 50 0 0 39
95 33 1 33 110
138 202 174 64 108
78 340 68 340 461
457 291 491 566 766
|
1
-1
2
-1
-1
2
1
4
1
3
|