畀定一個長度為 $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$ 個數值。考慮所有可能嘅劃分,搵出劃分分數嘅最大可能值同最小可能值。
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, y$ 嘅按位元與 $x \text{ and } y$ 同按位元或 $x \text{ or } y$ 定義如下。
- 喺 $x \text{ and } y$ 嘅二進制表示入面,$2^k\ (k \ge 0)$ 位上面嘅數字係 $1$ 當且僅當 $x$ 同 $y$ 嘅二進制表示喺 $2^k$ 位上面嘅數字都係 $1$;否則係 $0$。
- 喺 $x \text{ or } 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 = 1$,$011 \text{ or } 101 = 111$)。