Du får en talföljd av positiva heltal $(A_1, \dots, A_N)$ av längd $N$. Betrakta en uppdelning (partitionering) av denna talföljd $A$ i $M$ sammanhängande icke-tomma delföljder $B_1, B_2, \dots, B_M$.
För en delföljd $B = (A_L, \dots, A_R)$, definiera dess poäng som $$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}$$ där $x \text{ and } y$ och $x \text{ or } y$ betecknar bitvis OCH (AND) respektive bitvis ELLER (OR) av $x$ och $y$.
När en partition är fastställd får vi $M$ värden $S(B_1), \dots, S(B_M)$ som delföljdernas poäng. Sortera dessa värden i fallande ordning och definiera partitionens poäng som det $K$:te värdet i den ordningen. Om man betraktar alla möjliga partitioner, bestäm det största och det minsta möjliga värdet på partitionens poäng.
Input
Den första raden innehåller heltalen $N, M, K$ i denna ordning. ($1 \le K \le M \le N \le 10^5$)
Den andra raden innehåller $N$ heltal $A_1, \dots, A_N$ i denna ordning. ($1 \le A_i < 2^{30}\ (1 \le i \le N)$)
Output
Skriv ut $2$ rader.
Låt det största och det minsta värdet vara $\frac{p}{q}, \frac{r}{s}$, där $p, r \ge 0$, $q, s \ge 1$, $\gcd(p, q) = \gcd(r, s) = 1$. Skriv ut $p, q$ på den första raden och $r, s$ på den andra raden, åtskilda av mellanslag, i denna ordning.
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
För det första exemplet, om vi väljer $B_1 = (6)$, $B_2 = (5, 7)$, $B_3 = (3, 2)$, så är $S(B_1) = 1$, $S(B_2) = \frac{5}{7}$, $S(B_3) = \frac{2}{3}$. När dessa sorteras i fallande ordning är det $3$:e värdet $\frac{2}{3}$.
Om vi väljer $B_1 = (6)$, $B_2 = (5, 7, 3)$, $B_3 = (2)$, så är $S(B_1) = 1$, $S(B_2) = \frac{1}{7}$, $S(B_3) = 1$. När dessa sorteras i fallande ordning är det $3$:e värdet $\frac{1}{7}$.
Bitvis OCH $x \text{ and } y$ och bitvis ELLER $x \text{ or } y$ för icke-negativa heltal $x, y$ definieras enligt följande.
- I den binära representationen av $x \text{ and } y$ är siffran på position $2^k\ (k \ge 0)$ lika med $1$ om och endast om siffrorna på position $2^k$ i de binära representationerna av både $x$ och $y$ är $1$; annars är den $0$.
- I den binära representationen av $x \text{ or } y$ är siffran på position $2^k\ (k \ge 0)$ lika med $1$ om och endast om minst en av siffrorna på position $2^k$ i de binära representationerna av $x$ och $y$ är $1$; annars är den $0$.
Till exempel är $3 \text{ and } 5 = 1$, $3 \text{ or } 5 = 7$ (binärt: $011 \text{ and } 101 = 1$, $011 \text{ or } 101 = 111$).