Дана последовательность положительных целых чисел $(A_1, \dots, A_N)$ длины $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$ соответственно.

После того как разбиение зафиксировано, мы получаем $M$ значений $S(B_1), \dots, S(B_M)$ в качестве оценок подпоследовательностей. Отсортируем эти значения по убыванию и определим оценку разбиения как $K$-е значение в этом списке. Рассматривая все возможные разбиения, найдите максимально и минимально возможные значения оценки разбиения.

Входные данные

Первая строка содержит целые числа $N, M, K$ в указанном порядке. $(1 \le K \le M \le N \le 10^5)$

Вторая строка содержит $N$ целых чисел $A_1, \dots, A_N$ в указанном порядке. $(1 \le A_i < 2^{30} \text{ (} 1 \le i \le N \text{)})$

Выходные данные

Выведите 2 строки.

Пусть максимальное и минимальное значения равны $\frac{p}{q}$ и $\frac{r}{s}$ соответственно, где $p, r \ge 0$, $q, s \ge 1$, $\gcd(p, q) = \gcd(r, s) = 1$. Выведите $p, q$ в первой строке и $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 \text{ and } y$ и побитовое ИЛИ $x \text{ or } y$ неотрицательных целых чисел $x, y$ определяются следующим образом:

• В двоичном представлении $x \text{ and } y$ цифра в разряде $2^k$ ($k \ge 0$) равна 1 тогда и только тогда, когда цифры в разряде $2^k$ в двоичных представлениях обоих чисел $x$ и $y$ равны 1; в противном случае она равна 0.
• В двоичном представлении $x \text{ or } y$ цифра в разряде $2^k$ ($k \ge 0$) равна 1 тогда и только тогда, когда хотя бы одна из цифр в разряде $2^k$ в двоичных представлениях чисел $x$ и $y$ равна 1; в противном случае она равна 0.

Например, $3 \text{ and } 5 = 1$, $3 \text{ or } 5 = 7$ (в двоичном виде $011 \text{ and } 101 = 001$, $011 \text{ or } 101 = 111$).