A. Squid Game
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the Squid Game competition, each game requires different abilities to succeed. Unfortunately, you are player '$$$0$$$' and you have no abilities, and you must choose your teammates wisely to maximize your chances of winning. Each teammate will bring a set of abilities to the table, and your goal is to ensure that every one of your teammates has at least one ability required for a game.

For each game, you are given a number $$$x$$$ representing the abilities required for this game. The task is to determine how many people among $$$n$$$ players can join your team for that game, and whether it is guaranteed that your team will win.

Your team is guaranteed to win a game if, for every ability required by the game, at least one of your teammates possesses that ability.

A set of abilities isrepresented by a number . A number $$$a$$$ means a player has certain abilities, where the $$$j^{th}$$$ bit of $$$a$$$ in its binary representation is $$$1$$$ if the player masters the $$$j^{th}$$$ ability and $$$0$$$ otherwise.

Every player has at most 6 different abilities.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n,q \leq 2.10^5$$$), the number of players numbered from $$$1$$$ to $$$n$$$ and the number of games.

The second line contains $$$n$$$ integers $$$a_{1},a_{2},...,a_{n-1},a_{n}$$$ ($$$0 \leq a_{i} \leq 2^{20}-2^{14}$$$), where $$$a_{i}$$$ is the set of abilities of player $$$i$$$.

The next q line contains an integer $$$x$$$ ($$$0 \leq x \leq 2^{20}$$$), representing the abilities required for this game.

It's guaranteed that every player has at most 6 different abilities.

Output

For each game, print two integers:

  • The number of players that can join you for the game(have at least one of the abilities required for the game).
  • $$$1$$$ if it's guaranteed to win (for each required ability there is at least one of your teammates that has that ability) or $$$0$$$ otherwise.
Examples
Input
7 2
0 1 2 3 2 1 0
1
3
Output
3 1
5 1
Input
8 2
1 2 3 4 5 6 7 2
2
5
Output
5 1
6 1