Gegeben ist eine Folge positiver ganzer Zahlen $(A_1, \dots, A_N)$ der Länge $N$. Betrachte eine Zerlegung dieser Folge $A$ in $M$ zusammenhängende, nichtleere Teilfolgen $B_1, B_2, \dots, B_M$.
Für eine Teilfolge $B = (A_L, \dots, A_R)$ ist ihr Wert definiert durch $$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}$$ wobei $x \text{ and } y$ bzw. $x \text{ or } y$ das bitweise UND (AND) bzw. das bitweise ODER (OR) von $x$ und $y$ bezeichnen.
Sobald eine Zerlegung festgelegt ist, erhalten wir $M$ Werte $S(B_1), \dots, S(B_M)$ als die Werte der Teilfolgen. Sortiere diese Werte in absteigender Reihenfolge und definiere den Wert der Zerlegung als den $K$-ten Wert in dieser Reihenfolge. Finde unter allen möglichen Zerlegungen den maximalen und den minimalen möglichen Wert der Zerlegung.
Input
Die erste Zeile enthält die ganzen Zahlen $N, M, K$ in dieser Reihenfolge. ($1 \le K \le M \le N \le 10^5$)
Die zweite Zeile enthält $N$ ganze Zahlen $A_1, \dots, A_N$ in dieser Reihenfolge. ($1 \le A_i < 2^{30}\ (1 \le i \le N)$)
Output
Gib $2$ Zeilen aus.
Seien der maximale und der minimale Wert $\frac{p}{q}, \frac{r}{s}$, wobei $p, r \ge 0$, $q, s \ge 1$, $\gcd(p, q) = \gcd(r, s) = 1$. Gib $p, q$ in der ersten Zeile und $r, s$ in der zweiten Zeile, jeweils durch Leerzeichen getrennt, in dieser Reihenfolge aus.
Examples
Input 1
5 3 3 6 5 7 3 2
Output 1
2 3 1 7
Input 2
5 1 1 3 1 4 1 5
Output 2
0 1 0 1
Input 3
9 5 3 998 244 353 469 762 49 754 974 721
Output 3
1 1 208 1023
Note
Wenn wir im ersten Beispiel $B_1 = (6)$, $B_2 = (5, 7)$, $B_3 = (3, 2)$ wählen, gilt $S(B_1) = 1$, $S(B_2) = \frac{5}{7}$, $S(B_3) = \frac{2}{3}$. Wenn diese absteigend sortiert werden, ist der $3$-te Wert $\frac{2}{3}$.
Wenn wir außerdem $B_1 = (6)$, $B_2 = (5, 7, 3)$, $B_3 = (2)$ wählen, gilt $S(B_1) = 1$, $S(B_2) = \frac{1}{7}$, $S(B_3) = 1$. Wenn diese absteigend sortiert werden, ist der $3$-te Wert $\frac{1}{7}$.
Das bitweise UND $x \text{ and } y$ und das bitweise ODER $x \text{ or } y$ nichtnegativer ganzer Zahlen $x, y$ sind wie folgt definiert:
- In der Binärdarstellung von $x \text{ and } y$ ist die Ziffer an der Stelle $2^k\ (k \ge 0)$ genau dann $1$, wenn die Ziffern an der Stelle $2^k$ in den Binärdarstellungen von sowohl $x$ als auch $y$ gleich $1$ sind; andernfalls ist sie $0$.
- In der Binärdarstellung von $x \text{ or } y$ ist die Ziffer an der Stelle $2^k\ (k \ge 0)$ genau dann $1$, wenn mindestens eine der Ziffern an der Stelle $2^k$ in den Binärdarstellungen von $x$ und $y$ gleich $1$ ist; andernfalls ist sie $0$.
Beispielsweise gilt $3 \text{ and } 5 = 1$, $3 \text{ or } 5 = 7$ (binär: $011 \text{ and } 101 = 1$, $011 \text{ or } 101 = 111$).