Sinulle annetaan positiivisten kokonaislukujen jono $(A_1, \dots, A_N)$, jonka pituus on $N$. Tarkastellaan tämän jonon $A$ osittamista $M$:ään yhtenäiseen epätyhjään osajonoon $B_1, B_2, \dots, B_M$.
Osajonolle $B = (A_L, \dots, A_R)$ määritellään sen pistemäärä kaavalla $$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}$$ missä $x \text{ and } y$ ja $x \text{ or } y$ tarkoittavat lukujen $x$ ja $y$ bittikohtaista JA-operaatiota (AND) ja bittikohtaista TAI-operaatiota (OR).
Kun ositus on kiinnitetty, saamme osajonojen pistemäärinä $M$ arvoa $S(B_1), \dots, S(B_M)$. Järjestetään nämä arvot laskevaan järjestykseen ja määritellään osituksen pistemääräksi $K$-s arvo tässä järjestyksessä. Kun huomioidaan kaikki mahdolliset ositukset, etsi osituksen pistemäärän suurin ja pienin mahdollinen arvo.
Input
Ensimmäinen rivi sisältää kokonaisluvut $N, M, K$ tässä järjestyksessä. ($1 \le K \le M \le N \le 10^5$)
Toinen rivi sisältää $N$ kokonaislukua $A_1, \dots, A_N$ tässä järjestyksessä. ($1 \le A_i < 2^{30}\ (1 \le i \le N)$)
Output
Tulosta $2$ riviä.
Olkoot suurin ja pienin arvo $\frac{p}{q}, \frac{r}{s}$, missä $p, r \ge 0$, $q, s \ge 1$, $\gcd(p, q) = \gcd(r, s) = 1$. Tulosta $p, q$ ensimmäiselle riville ja $r, s$ toiselle riville välilyönneillä erotettuina tässä järjestyksessä.
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
Ensimmäisessä esimerkissä, jos valitsemme $B_1 = (6)$, $B_2 = (5, 7)$, $B_3 = (3, 2)$, niin $S(B_1) = 1$, $S(B_2) = \frac{5}{7}$, $S(B_3) = \frac{2}{3}$. Kun nämä järjestetään laskevaan järjestykseen, $3$. arvo on $\frac{2}{3}$.
Lisäksi, jos valitsemme $B_1 = (6)$, $B_2 = (5, 7, 3)$, $B_3 = (2)$, niin $S(B_1) = 1$, $S(B_2) = \frac{1}{7}$, $S(B_3) = 1$. Kun nämä järjestetään laskevaan järjestykseen, $3$. arvo on $\frac{1}{7}$.
Ei-negatiivisten kokonaislukujen $x, y$ bittikohtainen JA $x \text{ and } y$ ja bittikohtainen TAI $x \text{ or } y$ määritellään seuraavasti.
- Luvun $x \text{ and } y$ binääriesityksessä kohdan $2^k\ (k \ge 0)$ numero on $1$, jos ja vain jos sekä luvun $x$ että luvun $y$ binääriesityksessä kohdan $2^k$ numero on $1$; muuten se on $0$.
- Luvun $x \text{ or } y$ binääriesityksessä kohdan $2^k\ (k \ge 0)$ numero on $1$, jos ja vain jos vähintään toisessa lukujen $x$ ja $y$ binääriesityksistä kohdan $2^k$ numero on $1$; muuten se on $0$.
Esimerkiksi $3 \text{ and } 5 = 1$, $3 \text{ or } 5 = 7$ (binäärinä $011 \text{ and } 101 = 1$, $011 \text{ or } 101 = 111$).