給定一個長度為 $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$ 個值。考慮所有可能的分割方式，求出該分割分數的最大值與最小值。

輸入格式

第一行包含整數 $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))$

輸出格式

輸出 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$，並以空格分隔。

範例

輸入格式 1

5 3 3
6 5 7 3 2

輸出格式 1

2 3
1 7

說明

對於第一個範例，若我們選擇 $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}$。

輸入格式 2

5 1 1
3 1 4 1 5

輸出格式 2

0 1
0 1

輸入格式 3

9 5 3
998 244 353 469 762 49 754 974 721

輸出格式 3

1 1
208 1023

說明

非負整數 $x, y$ 的位元 AND ($x \text{ and } y$) 與位元 OR ($x \text{ or } y$) 定義如下：

• 在 $x$ 與 $y$ 的二進位表示中，$2^k$ ($k \ge 0$) 位上的數字為 1，若且唯若 $x$ 與 $y$ 二進位表示中 $2^k$ 位上的數字皆為 1；否則為 0。
• 在 $x$ 或 $y$ 的二進位表示中，$2^k$ ($k \ge 0$) 位上的數字為 1，若且唯若 $x$ 與 $y$ 二進位表示中 $2^k$ 位上的數字至少有一個為 1；否則為 0。

例如，$3 \text{ and } 5 = 1, 3 \text{ or } 5 = 7$（二進位下，$011 \text{ and } 101 = 001 = 1, 011 \text{ or } 101 = 111 = 7$）。