Farewell

Limits 3s, 1.0 GB

Alice has found an array AA containing nn non-negative integers, where the ii-th element is named AiA_i. But she only likes an array if all elements of it are equal.

In order to make Alice happy, Bob has come up with an idea. He has a small array BB with mm non-negative integers, where the jj-th element is named BjB_j. Bob can do the following operation any number of times (possibly zero):

  1. Select any integer kk where 1kn1 \leq k \leq n.

  2. Select any subset SS containing kk distinct indices of AA. Let S={s1,s2,s3,...,sk}S = \{s_1, s_2, s_3, ..., s_k\}.

  3. Select any integer xBx \in B.

  4. For each element siSs_i \in S, assign Asi:=AsixA_{s_i} := A_{s_i} \oplus x.

However, because doing this operation requires so much energy, Bob asked you to determine the minimum number of operations required to make all elements of AA equal or report if it is impossible. Can you make both Alice and Bob happy?

Input

The input contains three lines.

Output

Print an integer in a single line denoting the minimum number of operations required to make all elements of AA equal if it is possible, otherwise print 1-1.

Samples

InputOutput
3 2
1 3 5
6 2
2
InputOutput
2 1
1 4
2
-1