Vous disposez d'une séquence d'entiers positifs $(A_1, \dots, A_N)$ de longueur $N$. Considérez une partition de cette séquence $A$ en $M$ sous-séquences contiguës non vides $B_1, B_2, \dots, B_M$.

Pour une sous-séquence $B = (A_L, \dots, A_R)$, définissez son score par $$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}$$ où $x \text{ and } y$ et $x \text{ or } y$ désignent respectivement le ET bit à bit et le OU bit à bit de $x$ et $y$.

Une fois la partition fixée, nous obtenons $M$ valeurs $S(B_1), \dots, S(B_M)$ comme scores des sous-séquences. Triez ces valeurs par ordre décroissant et définissez le score de la partition comme étant la $K$-ième valeur dans cet ordre. En considérant toutes les partitions possibles, trouvez les valeurs maximale et minimale possibles du score de la partition.

Entrée

La première ligne contient les entiers $N, M, K$ dans cet ordre. $(1 \le K \le M \le N \le 10^5)$

La deuxième ligne contient $N$ entiers $A_1, \dots, A_N$ dans cet ordre. $(1 \le A_i < 2^{30} \text{ pour } 1 \le i \le N)$

Sortie

Imprimez 2 lignes.

Soient les valeurs maximale et minimale $\frac{p}{q}$ et $\frac{r}{s}$ respectivement, où $p, r \ge 0$, $q, s \ge 1$, $\gcd(p, q) = \gcd(r, s) = 1$. Imprimez $p, q$ sur la première ligne, et $r, s$ sur la deuxième ligne, séparés par des espaces, dans cet ordre.

Exemples

Entrée 1

5 3 3
6 5 7 3 2

Sortie 1

2 3
1 7

Remarque

Pour le premier exemple, si nous choisissons $B_1 = (6)$, $B_2 = (5, 7)$, $B_3 = (3, 2)$, alors $S(B_1) = 1$, $S(B_2) = \frac{5}{7}$, $S(B_3) = \frac{2}{3}$. Lorsqu'elles sont triées par ordre décroissant, la 3-ième valeur est $\frac{2}{3}$.

De même, si nous choisissons $B_1 = (6)$, $B_2 = (5, 7, 3)$, $B_3 = (2)$, alors $S(B_1) = 1$, $S(B_2) = \frac{1}{7}$, $S(B_3) = 1$. Lorsqu'elles sont triées par ordre décroissant, la 3-ième valeur est $\frac{1}{7}$.

Entrée 2

5 1 1
3 1 4 1 5

Sortie 2

0 1
0 1

Entrée 3

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

Sortie 3

1 1
208 1023

Le ET bit à bit $x \text{ and } y$ et le OU bit à bit $x \text{ or } y$ d'entiers non négatifs $x, y$ sont définis comme suit :

• Dans la représentation binaire de $x \text{ and } y$, le chiffre à la position $2^k$ ($k \ge 0$) est 1 si et seulement si les chiffres à la position $2^k$ dans les représentations binaires de $x$ et $y$ sont tous deux 1 ; sinon, il est 0.
• Dans la représentation binaire de $x \text{ or } y$, le chiffre à la position $2^k$ ($k \ge 0$) est 1 si et seulement si au moins l'un des chiffres à la position $2^k$ dans les représentations binaires de $x$ et $y$ est 1 ; sinon, il est 0.

Par exemple, $3 \text{ and } 5 = 1$, $3 \text{ or } 5 = 7$ (en binaire, $011 \text{ and } 101 = 001$, $011 \text{ or } 101 = 111$).