Þér er gefin runa af jákvæðum heiltölum $(A_1, \dots, A_N)$ af lengd $N$. Skoðum skiptingu á þessari runu $A$ í $M$ samfelldar ótómar hlutrunur $B_1, B_2, \dots, B_M$.
Fyrir hlutrunu $B = (A_L, \dots, A_R)$, skilgreinum stig hennar sem $$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}$$ þar sem $x \text{ and } y$ og $x \text{ or } y$ tákna bitbundið OG (AND) og bitbundið EÐA (OR) á $x$ og $y$, í sömu röð.
Þegar skipting hefur verið ákveðin fáum við $M$ gildi $S(B_1), \dots, S(B_M)$ sem stig hlutrunanna. Röðum þessum gildum í minnkandi röð og skilgreinum stig skiptingarinnar sem $K$-ta gildið í þeirri röð. Ef allar mögulegar skiptingar eru skoðaðar, finndu hæsta og lægsta mögulega gildið á stigum skiptingarinnar.
Input
Fyrsta línan inniheldur heiltölurnar $N, M, K$ í þessari röð. ($1 \le K \le M \le N \le 10^5$)
Önnur línan inniheldur $N$ heiltölur $A_1, \dots, A_N$ í þessari röð. ($1 \le A_i < 2^{30}\ (1 \le i \le N)$)
Output
Prentaðu $2$ línur.
Látum hæsta og lægsta gildið vera $\frac{p}{q}, \frac{r}{s}$, í sömu röð, þar sem $p, r \ge 0$, $q, s \ge 1$, $\gcd(p, q) = \gcd(r, s) = 1$. Prentaðu $p, q$ á fyrstu línuna og $r, s$ á aðra línuna, aðskilin með bilum, í þessari röð.
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
Í fyrsta dæminu, ef við veljum $B_1 = (6)$, $B_2 = (5, 7)$, $B_3 = (3, 2)$, þá er $S(B_1) = 1$, $S(B_2) = \frac{5}{7}$, $S(B_3) = \frac{2}{3}$. Þegar þessum gildum er raðað í minnkandi röð er $3$-ja gildið $\frac{2}{3}$.
Einnig, ef við veljum $B_1 = (6)$, $B_2 = (5, 7, 3)$, $B_3 = (2)$, þá er $S(B_1) = 1$, $S(B_2) = \frac{1}{7}$, $S(B_3) = 1$. Þegar þessum gildum er raðað í minnkandi röð er $3$-ja gildið $\frac{1}{7}$.
Bitbundið OG $x \text{ and } y$ og bitbundið EÐA $x \text{ or } y$ fyrir óneikvæðar heiltölur $x, y$ eru skilgreind sem hér segir.
- Í tvíundarframsetningunni á $x \text{ and } y$ er tölustafurinn í sæti $2^k\ (k \ge 0)$ jafn $1$ þá og því aðeins að tölustafirnir í sæti $2^k$ í tvíundarframsetningum bæði $x$ og $y$ séu $1$; annars er hann $0$.
- Í tvíundarframsetningunni á $x \text{ or } y$ er tölustafurinn í sæti $2^k\ (k \ge 0)$ jafn $1$ þá og því aðeins að að minnsta kosti annar tölustafurinn í sæti $2^k$ í tvíundarframsetningum $x$ og $y$ sé $1$; annars er hann $0$.
Til dæmis er $3 \text{ and } 5 = 1$, $3 \text{ or } 5 = 7$ (í tvíundarkerfi, $011 \text{ and } 101 = 1$, $011 \text{ or } 101 = 111$).