Se le da una secuencia de enteros positivos $(A_1, \dots, A_N)$ de longitud $N$. Considere particionar esta secuencia $A$ en $M$ subsecuencias contiguas no vacías $B_1, B_2, \dots, B_M$.

Para una subsecuencia $B = (A_L, \dots, A_R)$, defina su puntuación mediante $$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}$$ donde $x \text{ and } y$ y $x \text{ or } y$ denotan el AND bit a bit y el OR bit a bit de $x$ e $y$, respectivamente.

Una vez fijada una partición, obtenemos $M$ valores $S(B_1), \dots, S(B_M)$ como las puntuaciones de las subsecuencias. Ordene estos valores en orden descendente y defina la puntuación de la partición como el $K$-ésimo valor en ese orden. Considerando todas las particiones posibles, encuentre los valores máximo y mínimo posibles de la puntuación de la partición.

Entrada

La primera línea contiene los enteros $N, M, K$ en este orden. $(1 \le K \le M \le N \le 10^5)$

La segunda línea contiene $N$ enteros $A_1, \dots, A_N$ en este orden. $(1 \le A_i < 2^{30} \ (1 \le i \le N))$

Salida

Imprima 2 líneas.

Sean los valores máximo y mínimo $\frac{p}{q}$ y $\frac{r}{s}$, respectivamente, donde $p, r \ge 0$, $q, s \ge 1$, $\gcd(p, q) = \gcd(r, s) = 1$. Imprima $p, q$ en la primera línea, y $r, s$ en la segunda línea, separados por espacios, en este orden.

Ejemplos

Entrada 1

5 3 3
6 5 7 3 2

Salida 1

2 3
1 7

Entrada 2

5 1 1
3 1 4 1 5

Salida 2

0 1
0 1

Entrada 3

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

Salida 3

1 1
208 1023

Nota

Para el primer ejemplo, si elegimos $B_1 = (6)$, $B_2 = (5, 7)$, $B_3 = (3, 2)$, entonces $S(B_1) = 1$, $S(B_2) = \frac{5}{7}$, $S(B_3) = \frac{2}{3}$. Cuando estos se ordenan en orden descendente, el tercer valor es $\frac{2}{3}$.

Además, si elegimos $B_1 = (6)$, $B_2 = (5, 7, 3)$, $B_3 = (2)$, entonces $S(B_1) = 1$, $S(B_2) = \frac{1}{7}$, $S(B_3) = 1$. Cuando estos se ordenan en orden descendente, el tercer valor es $\frac{1}{7}$.

El AND bit a bit $x \text{ and } y$ y el OR bit a bit $x \text{ or } y$ de enteros no negativos $x, y$ se definen de la siguiente manera:

• En la representación binaria de $x \text{ and } y$, el dígito en la posición $2^k$ ($k \ge 0$) es 1 si y solo si los dígitos en la posición $2^k$ en las representaciones binarias tanto de $x$ como de $y$ son 1; de lo contrario, es 0.
• En la representación binaria de $x \text{ or } y$, el dígito en la posición $2^k$ ($k \ge 0$) es 1 si y solo si al menos uno de los dígitos en la posición $2^k$ en las representaciones binarias de $x$ e $y$ es 1; de lo contrario, es 0.

Por ejemplo, $3 \text{ and } 5 = 1$, $3 \text{ or } 5 = 7$ (en binario, $011 \text{ and } 101 = 001$, $011 \text{ or } 101 = 111$).