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?


The input contains three lines.

  • The first line contains two integers nn (1n105)(1 \leq n \leq 10^5) and mm (1m24)(1 \leq m \leq 24).

  • The second line contains nn integers representing AA where the ii-th integer represents AiA_i (0Ai<224)(0 \leq A_i < 2^{24}).

  • The third line contains mm integers representing BB where the jj-th integer represents BjB_j (0Bj<224)(0 \leq B_j < 2^{24}).


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.


3 2
1 3 5
6 2
2 1
1 4


Login to submit.


0% Solution Ratio
Toph uses cookies. By continuing you agree to our Cookie Policy.