Вам дано послідовність додатних цілих чисел $(A_1, \dots, A_N)$ довжини $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$ позначають побітове І (AND) та побітове АБО (OR) чисел $x$ і $y$ відповідно.
Коли розбиття зафіксовано, ми отримуємо $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 \text{ and } y$ та побітове АБО $x \text{ or } y$ невід'ємних цілих чисел $x, y$ визначаються таким чином:
- У двійковому поданні $x \text{ and } y$ цифра в розряді $2^k\ (k \ge 0)$ дорівнює $1$ тоді й лише тоді, коли цифри в розряді $2^k$ у двійкових поданнях і $x$, і $y$ дорівнюють $1$; інакше вона дорівнює $0$.
- У двійковому поданні $x \text{ or } y$ цифра в розряді $2^k\ (k \ge 0)$ дорівнює $1$ тоді й лише тоді, коли принаймні одна з цифр у розряді $2^k$ у двійкових поданнях $x$ та $y$ дорівнює $1$; інакше вона дорівнює $0$.
Наприклад, $3 \text{ and } 5 = 1$, $3 \text{ or } 5 = 7$ (у двійковій системі: $011 \text{ and } 101 = 1$, $011 \text{ or } 101 = 111$).