Ti viene data una sequenza di interi positivi $(A_1, \dots, A_N)$ di lunghezza $N$. Considera di partizionare questa sequenza $A$ in $M$ sottosequenze contigue non vuote $B_1, B_2, \dots, B_M$.
Per una sottosequenza $B = (A_L, \dots, A_R)$, definisci il suo punteggio come $$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}$$ dove $x \text{ and } y$ e $x \text{ or } y$ indicano rispettivamente l'AND bit a bit e l'OR bit a bit di $x$ e $y$.
Una volta fissata una partizione, otteniamo $M$ valori $S(B_1), \dots, S(B_M)$ come punteggi delle sottosequenze. Ordina questi valori in ordine decrescente e definisci il punteggio della partizione come il $K$-esimo valore in tale ordine. Considerando tutte le possibili partizioni, trova il valore massimo e il valore minimo possibili del punteggio della partizione.
Input
La prima riga contiene gli interi $N, M, K$ in questo ordine. ($1 \le K \le M \le N \le 10^5$)
La seconda riga contiene $N$ interi $A_1, \dots, A_N$ in questo ordine. ($1 \le A_i < 2^{30}\ (1 \le i \le N)$)
Output
Stampa $2$ righe.
Siano il valore massimo e il valore minimo rispettivamente $\frac{p}{q}, \frac{r}{s}$, dove $p, r \ge 0$, $q, s \ge 1$, $\gcd(p, q) = \gcd(r, s) = 1$. Stampa $p, q$ sulla prima riga e $r, s$ sulla seconda riga, separati da spazi, in questo ordine.
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
Per il primo esempio, se scegliamo $B_1 = (6)$, $B_2 = (5, 7)$, $B_3 = (3, 2)$, allora $S(B_1) = 1$, $S(B_2) = \frac{5}{7}$, $S(B_3) = \frac{2}{3}$. Quando questi valori vengono ordinati in ordine decrescente, il $3$-o valore è $\frac{2}{3}$.
Inoltre, se scegliamo $B_1 = (6)$, $B_2 = (5, 7, 3)$, $B_3 = (2)$, allora $S(B_1) = 1$, $S(B_2) = \frac{1}{7}$, $S(B_3) = 1$. Quando questi valori vengono ordinati in ordine decrescente, il $3$-o valore è $\frac{1}{7}$.
L'AND bit a bit $x \text{ and } y$ e l'OR bit a bit $x \text{ or } y$ di interi non negativi $x, y$ sono definiti come segue.
- Nella rappresentazione binaria di $x \text{ and } y$, la cifra nella posizione $2^k\ (k \ge 0)$ è $1$ se e solo se le cifre nella posizione $2^k$ nelle rappresentazioni binarie sia di $x$ che di $y$ sono $1$; altrimenti è $0$.
- Nella rappresentazione binaria di $x \text{ or } y$, la cifra nella posizione $2^k\ (k \ge 0)$ è $1$ se e solo se almeno una delle cifre nella posizione $2^k$ nelle rappresentazioni binarie di $x$ e $y$ è $1$; altrimenti è $0$.
Ad esempio, $3 \text{ and } 5 = 1$, $3 \text{ or } 5 = 7$ (in binario, $011 \text{ and } 101 = 1$, $011 \text{ or } 101 = 111$).