Dany jest ciąg dodatnich liczb całkowitych $(A_1, \dots, A_N)$ o długości $N$. Rozważmy podział tego ciągu $A$ na $M$ spójnych, niepustych podciągów $B_1, B_2, \dots, B_M$.

Dla podciągu $B = (A_L, \dots, A_R)$ definiujemy jego wynik jako: $$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}$$ gdzie $x \text{ and } y$ oraz $x \text{ or } y$ oznaczają odpowiednio bitowe AND oraz bitowe OR liczb $x$ i $y$.

Po ustaleniu podziału otrzymujemy $M$ wartości $S(B_1), \dots, S(B_M)$ jako wyniki podciągów. Sortujemy te wartości w porządku malejącym i definiujemy wynik podziału jako $K$-tą wartość w tym porządku. Rozważając wszystkie możliwe podziały, znajdź maksymalną i minimalną możliwą wartość wyniku podziału.

Wejście

W pierwszej linii znajdują się liczby całkowite $N, M, K$ w tej kolejności. ($1 \le K \le M \le N \le 10^5$)

W drugiej linii znajduje się $N$ liczb całkowitych $A_1, \dots, A_N$ w tej kolejności. ($1 \le A_i < 2^{30}$ dla $1 \le i \le N$)

Wyjście

Wypisz 2 linie.

Niech wartością maksymalną będzie $\frac{p}{q}$, a minimalną $\frac{r}{s}$, gdzie $p, r \ge 0$, $q, s \ge 1$, $\gcd(p, q) = \gcd(r, s) = 1$. Wypisz $p, q$ w pierwszej linii oraz $r, s$ w drugiej linii, oddzielone spacjami, w podanej kolejności.

Przykład

Wejście 1

5 3 3
6 5 7 3 2

Wyjście 1

2 3
1 7

Wejście 2

5 1 1
3 1 4 1 5

Wyjście 2

0 1
0 1

Wejście 3

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

Wyjście 3

1 1
208 1023

Uwagi

Dla pierwszego przykładu, jeśli wybierzemy $B_1 = (6)$, $B_2 = (5, 7)$, $B_3 = (3, 2)$, to $S(B_1) = 1$, $S(B_2) = \frac{5}{7}$, $S(B_3) = \frac{2}{3}$. Po posortowaniu ich w porządku malejącym, trzecią wartością jest $\frac{2}{3}$.

Jeśli natomiast wybierzemy $B_1 = (6)$, $B_2 = (5, 7, 3)$, $B_3 = (2)$, to $S(B_1) = 1$, $S(B_2) = \frac{1}{7}$, $S(B_3) = 1$. Po posortowaniu ich w porządku malejącym, trzecią wartością jest $\frac{1}{7}$.

Bitowe AND $x \text{ and } y$ oraz bitowe OR $x \text{ or } y$ nieujemnych liczb całkowitych $x, y$ definiuje się następująco:

• W reprezentacji binarnej $x \text{ and } y$, cyfra na pozycji $2^k$ ($k \ge 0$) jest równa 1 wtedy i tylko wtedy, gdy cyfry na pozycji $2^k$ w reprezentacjach binarnych zarówno $x$, jak i $y$ są równe 1; w przeciwnym razie jest równa 0.
• W reprezentacji binarnej $x \text{ or } y$, cyfra na pozycji $2^k$ ($k \ge 0$) jest równa 1 wtedy i tylko wtedy, gdy co najmniej jedna z cyfr na pozycji $2^k$ w reprezentacjach binarnych $x$ lub $y$ jest równa 1; w przeciwnym razie jest równa 0.

Na przykład $3 \text{ and } 5 = 1$, $3 \text{ or } 5 = 7$ (binarnie $011 \text{ and } 101 = 001$, $011 \text{ or } 101 = 111$).