長さ $N$ の正の整数の数列 $(A_1, \dots, A_N)$ が与えられます。この数列 $A$ を $M$ 個の連続する空でない部分列 $B_1, B_2, \dots, B_M$ に分割することを考えます。

部分列 $B = (A_L, \dots, A_R)$ に対して、そのスコアを以下のように定義します。 $$S(B) = \frac{A_L \text{ and } A_{L+1} \text{ and } \dots \text{ and } A_R}{A_L \text{ or } A_{L+1} \text{ or } \dots \text{ or } A_R}$$ ここで、$x \text{ and } y$ および $x \text{ or } y$ はそれぞれ $x$ と $y$ のビットごとの AND およびビットごとの OR を表します。

分割が固定されると、$M$ 個の値 $S(B_1), \dots, S(B_M)$ が得られます。これらの値を降順に並べ替え、その順序における $K$ 番目の値をその分割のスコアと定義します。 可能なすべての分割について、分割スコアの最大値と最小値を求めてください。

入力

1 行目には、整数 $N, M, K$ がこの順で与えられます。$(1 \le K \le M \le N \le 10^5)$ 2 行目には、$N$ 個の整数 $A_1, \dots, A_N$ がこの順で与えられます。$(1 \le A_i < 2^{30} \ (1 \le i \le N))$

出力

2 行に出力してください。 最大値および最小値をそれぞれ $\frac{p}{q}, \frac{r}{s}$ （ただし $p, r \ge 0, q, s \ge 1, \gcd(p, q) = \gcd(r, s) = 1$）とします。1 行目に $p, q$ を、2 行目に $r, s$ を、それぞれスペース区切りで出力してください。

入出力例

入力 1

5 3 3
6 5 7 3 2

出力 1

2 3
1 7

入力 2

5 1 1
3 1 4 1 5

出力 2

0 1
0 1

入力 3

9 5 3
998 244 353 469 762 49 754 974 721

出力 3

1 1
208 1023

注記

最初の例において、$B_1 = (6), B_2 = (5, 7), B_3 = (3, 2)$ と選ぶと、$S(B_1) = 1, S(B_2) = \frac{5}{7}, S(B_3) = \frac{2}{3}$ となります。これらを降順に並べ替えると、3 番目の値は $\frac{2}{3}$ です。 また、$B_1 = (6), B_2 = (5, 7, 3), B_3 = (2)$ と選ぶと、$S(B_1) = 1, S(B_2) = \frac{1}{7}, S(B_3) = 1$ となります。これらを降順に並べ替えると、3 番目の値は $\frac{1}{7}$ です。

非負整数 $x, y$ のビットごとの AND $x \text{ and } y$ およびビットごとの OR $x \text{ or } y$ は以下のように定義されます。

• $x$ と $y$ の二進表現において、$2^k \ (k \ge 0)$ の位の桁は、$x$ と $y$ の両方の二進表現における $2^k$ の位の桁がともに 1 である場合に限り 1 となり、それ以外の場合は 0 となります。
• $x$ または $y$ の二進表現において、$2^k \ (k \ge 0)$ の位の桁は、$x$ と $y$ の二進表現における $2^k$ の位の桁の少なくとも一方が 1 である場合に限り 1 となり、それ以外の場合は 0 となります。

例えば、$3 \text{ and } 5 = 1, 3 \text{ or } 5 = 7$ です（二進数では $011 \text{ and } 101 = 001, 011 \text{ or } 101 = 111$）。