给定一个长度为 $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$ 的按位与运算和按位或运算。

一旦划分确定，我们得到 $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$ 的按位与 $x \text{ and } y$ 和按位或 $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, 011 \text{ or } 101 = 111$）。