Сізге ұзындығы $N$ болатын оң бүтін сандар тізбегі $(A_1, \dots, A_N)$ берілген. Осы $A$ тізбегін бос емес $M$ іргелес ішкі тізбекке $B_1, B_2, \dots, B_M$ бөлуді қарастырайық.
$B = (A_L, \dots, A_R)$ ішкі тізбегі үшін оның ұпайын былайша анықтайық: $$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}$$ мұндағы $x \text{ and } y$ және $x \text{ or } y$ сәйкесінше $x$ пен $y$ сандарының биттік ЖӘНЕ (AND) мен биттік НЕМЕСЕ (OR) амалдарын білдіреді.
Бөліктеу бекітілгеннен кейін, ішкі тізбектердің ұпайлары ретінде $M$ мәнді $S(B_1), \dots, S(B_M)$ аламыз. Осы мәндерді кему ретімен сұрыптап, бөліктеудің ұпайын сол реттегі $K$-шы мән ретінде анықтайық. Барлық мүмкін бөліктеулерді қарастыра отырып, бөліктеу ұпайының ең үлкен және ең кіші мүмкін мәндерін табыңыз.
Input
Бірінші жолда осы ретпен $N, M, K$ бүтін сандары берілген. ($1 \le K \le M \le N \le 10^5$)
Екінші жолда осы ретпен $N$ бүтін сан $A_1, \dots, A_N$ берілген. ($1 \le A_i < 2^{30}\ (1 \le i \le N)$)
Output
$2$ жол шығарыңыз.
Ең үлкен және ең кіші мәндер сәйкесінше $\frac{p}{q}, \frac{r}{s}$ болсын, мұндағы $p, r \ge 0$, $q, s \ge 1$, $\gcd(p, q) = \gcd(r, s) = 1$. Бірінші жолға $p, q$ сандарын, ал екінші жолға $r, s$ сандарын бос орынмен бөліп, осы ретпен шығарыңыз.
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
Бірінші мысал үшін, егер $B_1 = (6)$, $B_2 = (5, 7)$, $B_3 = (3, 2)$ деп таңдасақ, онда $S(B_1) = 1$, $S(B_2) = \frac{5}{7}$, $S(B_3) = \frac{2}{3}$. Оларды кему ретімен сұрыптағанда, $3$-ші мән $\frac{2}{3}$ болады.
Сондай-ақ, егер $B_1 = (6)$, $B_2 = (5, 7, 3)$, $B_3 = (2)$ деп таңдасақ, онда $S(B_1) = 1$, $S(B_2) = \frac{1}{7}$, $S(B_3) = 1$. Оларды кему ретімен сұрыптағанда, $3$-ші мән $\frac{1}{7}$ болады.
Теріс емес $x, y$ бүтін сандарының биттік ЖӘНЕ $x \text{ and } y$ және биттік НЕМЕСЕ $x \text{ or } y$ амалдары келесідей анықталады.
- $x \text{ and } y$ санының екілік жазылуында $2^k\ (k \ge 0)$ орнындағы цифр тек $x$ пен $y$ екеуінің де екілік жазылуындағы $2^k$ орнындағы цифрлар $1$ болғанда ғана $1$-ге тең; әйтпесе ол $0$-ге тең.
- $x \text{ or } y$ санының екілік жазылуында $2^k\ (k \ge 0)$ орнындағы цифр тек $x$ пен $y$ сандарының екілік жазылуындағы $2^k$ орнындағы цифрлардың кемінде біреуі $1$ болғанда ғана $1$-ге тең; әйтпесе ол $0$-ге тең.
Мысалы, $3 \text{ and } 5 = 1$, $3 \text{ or } 5 = 7$ (екілік жүйеде $011 \text{ and } 101 = 1$, $011 \text{ or } 101 = 111$).