XOR Racer

Points: 1

Time limit: 1.0s

Memory limit: 256M

Author:

oree

Problem type

Allowed languages

C, C++, Java, Python

James is the XOR Racer — the man who flies around space on a motorbike that is powered by integers. Specifically, he feeds integers into his engine, which XORs them together. The engine requires multiple specific types of integer to move, and James is running dangerously low...

James has made a crash landing on a strange planet, where he finds a bunch of random integers. For each of the integers his engine requires, can you tell him if its possible for him to feed some subset of these integers to his engine in order to power it and fly off this planet? In other words, for each query integer, is there some subset of the input integers that XOR together to create the target value?

Input

The first line contains two space-separated integers $n$ ~n~ and $q$ ~q~, with $n$ ~n~ $(1 \leq n \leq 500)$ ~(1 \leq n \leq 500)~ representing the amount of integers found by James and $q$ ~q~ $(1 \leq q \leq 10^4)$ ~(1 \leq q \leq 10^4)~ representing the target integers required by James's engine.

The next line contains $n$ ~n~ space-separated integers $a_i$ ~a_i~ $(1 \leq a_i \leq 10^4)$ ~(1 \leq a_i \leq 10^4)~, each of the integers encountered by James. James is a smart fella and he has been attending AUCPL workshops, so he knows the properties of XOR. Thus, James has logged the integers such that each $a_i$ ~a_i~ is unique in the input. These integers form the set $A=\{a_i\mid i=1,\dots,n\}$ ~A=\{a_i\mid i=1,\dots,n\}~.

The following line contains $q$ ~q~ space-separated integers $k_i\ (1 \leq k_i \leq 10^4)$ ~k_i\ (1 \leq k_i \leq 10^4)~, the value of each of the target integers that should be created by XORing together subsets of the input values.

Output

For each $k_i$ ~k_i~, if it is possible to select a subset $X\subseteq A$ ~X\subseteq A~ with elements $x_1,\dots,x_m$ ~x_1,\dots,x_m~ such that $\bigoplus_{i=1}^m x_i=k_i$ ~\bigoplus_{i=1}^m x_i=k_i~ (the elements of subset $X$ ~X~ all XOR'd together gives $k_i$ ~k_i~), output "Yeehaw". Otherwise, output "Aw damn".

Clarifications

We define that any subset can produce any of its elements through XOR, i.e., the set $\{2\}$ ~\{2\}~ can produce $2$ ~2~ as an output. Although XOR is a binary operation, you can effectively imagine that the unit $0$ ~0~ is in every set.