C. Ohara's Bits
time limit per test
3.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Nix has stumbled upon the legendary quest of Ohara. There are two arrays of numbers, of length $$$N$$$ and $$$M$$$ respectively. For each number from the first array, Ohara wants to know what is the lowest and highest value of an Ohara match. An Ohara match is defined as follows:

  • For each number from the first array, we consider its binary representation without leading zeros. This representation, altered by flipping ($$$0 \rightarrow 1\ or\ 1 \rightarrow 0$$$) at most one bit, is called an Ohara number.
  • Consider the concatenation of the binary representations, without leading zeroes, of each number from the second array (from position $$$1$$$ to position $$$M$$$). The string obtained is called the Ohara string.
  • A match appears when there exists a substring $$$[s_i, s_{i + 1},\dots\ s_j]$$$ in the Ohara string, that is equal to an Ohara number K from the first set.
  • If $$$K$$$ was obtained without altering the original number from the first array, the value of an Ohara match is $$$0$$$.
  • If $$$K$$$ was obtained by altering the original number, by flipping a single bit, then consider the substring from the Ohara string that corresponds to an Ohara match. Now consider the number from the second array, that the flipped bit is part of, in that substring. The value of the Ohara match is equal to the power of $$$2$$$ corresponding to the flipped bit, in that number (see examples if unclear).

Nix finds this quest rather challenging, so she asks for your help in finding the answer.

Input

The first line of the input contains the numbers $$$N$$$ and $$$M$$$, the length of the first and second array of numbers. The second line contains $$$N$$$ integers $$$a_1, a_2,\dots\ a_N$$$ ($$$1 \leq N \leq 10^5,\ 1 \leq a_i \lt 2^{21}$$$), the numbers from the first array. The third line contains $$$M$$$ integers $$$b_1, b_2,\dots\ b_M$$$ ($$$1 \leq b_i \leq 10^9)$$$, the numbers from the second array. It is also guaranteed that the length of the Ohara string is at most $$$10^5$$$.

Output

The output will contain $$$N$$$ lines. The $$$i^{th}$$$ line will contain a pair of integers: the smallest and highest value of an Ohara match for the $$$i^{th}$$$ number in the first array. If there is no Ohara match for that number output -1 -1.

Examples
Input
1 2
5
4 1
Output
1 2
Input
1 2
13
3 6
Output
4 4
Note

In the first example we get the lowest value matching by transforming 101 into 100and matching on firstbit of 4 from the second array, thus 20= 1. The highest value matching is obtained by transforming101 into001 and matching on the second bit of 4 from the second array, thus 21= 2.