Boolean Extremes

Given a set of non-negative integers (A = {a_1, a_2, ..., a_n}), we need to select a non-empty subset of numbers (a_i1, a_i2, ..., a_ik) and perform the bitwise "and" operation on all of them, i.e., compute (a_i1 & a_i2 & ...& a_ik).

Your task is to determine the minimum and maximum values that can be obtained by selecting a subset for the bitwise "and" operation. Additionally, find the minimum and maximum values for the bitwise "or" (|) and "exclusive or" (^) operations.

Input

The first line of the input contains an integer (n) ((1 $\le$ n $\le$ 500)). The second line contains the elements of the set (A): (a_1, a_2, ..., a_n) ((0 $\le$ a_i < 2^63)).

Output

On the first line of the output, print the minimum and maximum values for the "and" operation. On the second line, print the minimum and maximum values for the "or" operation. On the third line, print the minimum and maximum values for the "exclusive or" operation.

Examples