Du får oppgitt en følge av positive heltall $(A_1, \dots, A_N)$ med lengde $N$. Betrakt en oppdeling (partisjonering) av denne følgen $A$ i $M$ sammenhengende ikke-tomme delfølger $B_1, B_2, \dots, B_M$.
For en delfølge $B = (A_L, \dots, A_R)$, definer poengsummen dens ved $$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}$$ der $x \text{ and } y$ og $x \text{ or } y$ betegner henholdsvis bitvis OG (AND) og bitvis ELLER (OR) av $x$ og $y$.
Når en partisjon er fastsatt, får vi $M$ verdier $S(B_1), \dots, S(B_M)$ som poengsummene til delfølgene. Sorter disse verdiene i synkende rekkefølge, og definer poengsummen til partisjonen som den $K$-te verdien i den rekkefølgen. Når alle mulige partisjoner tas i betraktning, finn den maksimale og minimale mulige verdien for partisjonens poengsum.
Input
Den første linjen inneholder heltallene $N, M, K$ i denne rekkefølgen. ($1 \le K \le M \le N \le 10^5$)
Den andre linjen inneholder $N$ heltall $A_1, \dots, A_N$ i denne rekkefølgen. ($1 \le A_i < 2^{30}\ (1 \le i \le N)$)
Output
Skriv ut $2$ linjer.
La maksimums- og minimumsverdiene være henholdsvis $\frac{p}{q}, \frac{r}{s}$, der $p, r \ge 0$, $q, s \ge 1$, $\gcd(p, q) = \gcd(r, s) = 1$. Skriv ut $p, q$ på den første linjen, og $r, s$ på den andre linjen, adskilt med mellomrom, i denne rekkefølgen.
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
For det første eksempelet, hvis vi velger $B_1 = (6)$, $B_2 = (5, 7)$, $B_3 = (3, 2)$, så er $S(B_1) = 1$, $S(B_2) = \frac{5}{7}$, $S(B_3) = \frac{2}{3}$. Når disse sorteres i synkende rekkefølge, er den $3$-dje verdien $\frac{2}{3}$.
Videre, hvis vi velger $B_1 = (6)$, $B_2 = (5, 7, 3)$, $B_3 = (2)$, så er $S(B_1) = 1$, $S(B_2) = \frac{1}{7}$, $S(B_3) = 1$. Når disse sorteres i synkende rekkefølge, er den $3$-dje verdien $\frac{1}{7}$.
Bitvis OG $x \text{ and } y$ og bitvis ELLER $x \text{ or } y$ av ikke-negative heltall $x, y$ er definert som følger.
- I den binære representasjonen av $x \text{ and } y$ er sifferet på plass $2^k\ (k \ge 0)$ lik $1$ hvis og bare hvis sifrene på plass $2^k$ i de binære representasjonene av både $x$ og $y$ er $1$; ellers er det $0$.
- I den binære representasjonen av $x \text{ or } y$ er sifferet på plass $2^k\ (k \ge 0)$ lik $1$ hvis og bare hvis minst ett av sifrene på plass $2^k$ i de binære representasjonene av $x$ og $y$ er $1$; ellers er det $0$.
For eksempel er $3 \text{ and } 5 = 1$, $3 \text{ or } 5 = 7$ (i binær, $011 \text{ and } 101 = 1$, $011 \text{ or } 101 = 111$).