You are given a sequence of positive integers $(A_1, \dots, A_N)$ of length $N$. Consider partitioning this sequence $A$ into $M$ contiguous non-empty subsequences $B_1, B_2, \dots, B_M$.
For a subsequence $B = (A_L, \dots, A_R)$, define its score by $$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}$$ where $x \text{ and } y$ and $x \text{ or } y$ denote the bitwise AND and bitwise OR of $x$ and $y$, respectively.
Once a partition is fixed, we obtain $M$ values $S(B_1), \dots, S(B_M)$ as the scores of the subsequences. Sort these values in descending order, and define the score of the partition as the $K$-th value in that order. Considering all possible partitions, find the maximum and minimum possible values of the partition score.
Input
The first line contains integers $N, M, K$ in this order. ($1 \le K \le M \le N \le 10^5$)
The second line contains $N$ integers $A_1, \dots, A_N$ in this order. ($1 \le A_i < 2^{30}\ (1 \le i \le N)$)
Output
Print $2$ lines.
Let the maximum and minimum values be $\frac{p}{q}, \frac{r}{s}$, respectively, where $p, r \ge 0$, $q, s \ge 1$, $\gcd(p, q) = \gcd(r, s) = 1$. Print $p, q$ on the first line, and $r, s$ on the second line, separated by spaces, in this order.
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 the first example, if we choose $B_1 = (6)$, $B_2 = (5, 7)$, $B_3 = (3, 2)$, then $S(B_1) = 1$, $S(B_2) = \frac{5}{7}$, $S(B_3) = \frac{2}{3}$. When these are sorted in descending order, the $3$-rd value is $\frac{2}{3}$.
Also, if we choose $B_1 = (6)$, $B_2 = (5, 7, 3)$, $B_3 = (2)$, then $S(B_1) = 1$, $S(B_2) = \frac{1}{7}$, $S(B_3) = 1$. When these are sorted in descending order, the $3$-rd value is $\frac{1}{7}$.
The bitwise AND $x \text{ and } y$ and bitwise OR $x \text{ or } y$ of non-negative integers $x, y$ are defined as follows.
- In the binary representation of $x \text{ and } y$, the digit at the $2^k\ (k \ge 0)$ place is $1$ if and only if the digits at the $2^k$ place in the binary representations of both $x$ and $y$ are $1$; otherwise, it is $0$.
- In the binary representation of $x \text{ or } y$, the digit at the $2^k\ (k \ge 0)$ place is $1$ if and only if at least one of the digits at the $2^k$ place in the binary representations of $x$ and $y$ is $1$; otherwise, it is $0$.
For example, $3 \text{ and } 5 = 1$, $3 \text{ or } 5 = 7$ (in binary, $011 \text{ and } 101 = 1$, $011 \text{ or } 101 = 111$).