C. Partition AND/OR Aggregation
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a sequence of positive integers $$$(A_1,\ldots,A_N)$$$ of length $$$N$$$. Consider partitioning this sequence $$$A$$$ into $$$M$$$ contiguous non-empty subsequences $$$B_1,B_2,\ldots,B_M$$$.

For a subsequence $$$B=(A_L,\ldots,A_R)$$$, define its score by $$$$$$S(B) = \dfrac{A_L \mathbin{\mathrm{and}} A_{L+1} \mathbin{\mathrm{and}} \cdots \mathbin{\mathrm{and}} A_R}{A_L \mathbin{\mathrm{or}} A_{L+1} \mathbin{\mathrm{or}} \cdots \mathbin{\mathrm{or}} A_R}$$$$$$ where $$$x \mathbin{\mathrm{and}} y$$$ and $$$x \mathbin{\mathrm{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),\ldots,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 \leq K \leq M \leq N \leq 10^5$$$)

The second line contains $$$N$$$ integers $$$A_1,\ldots,A_N$$$ in this order. ($$$ 1 \leq A_i \lt 2^{30} \ (1 \leq i \leq N)$$$)

Output

Print $$$2$$$ lines.

Let the maximum and minimum values be $$$\frac{p}{q}$$$, $$$\frac{r}{s}$$$, respectively, where $$$p,r \geq 0$$$, $$$\ q,s \geq 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
5 3 3
6 5 7 3 2
Output
2 3
1 7
Input
5 1 1
3 1 4 1 5
Output
0 1
0 1
Input
9 5 3
998 244 353 469 762 49 754 974 721
Output
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 \mathbin{\mathrm{and}} y$$$ and bitwise OR $$$x \mathbin{\mathrm{or}} y$$$ of non-negative integers $$$x,y$$$ are defined as follows.

  • In the binary representation of $$$x \mathbin{\mathrm{and}} y$$$, the digit at the $$$2^k \ (k \geq 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 \mathbin{\mathrm{or}} y$$$, the digit at the $$$2^k \ (k \geq 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 \mathbin{\mathrm{and}} 5 = 1, \ 3 \mathbin{\mathrm{or}} 5 = 7$$$ (in binary, $$$011 \mathbin{\mathrm{and}} 101 = 1, \ 011 \mathbin{\mathrm{or}} 101 = 111$$$).