길이가 $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

입력 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

참고

첫 번째 예제에서 $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$의 비트 단위 AND $x \text{ and } y$와 비트 단위 OR $x \text{ or } y$는 다음과 같이 정의된다.

• $x$와 $y$의 이진 표현에서, $2^k (k \ge 0)$ 자릿수는 $x$와 $y$의 이진 표현 모두에서 $2^k$ 자릿수가 1일 때만 1이고, 그렇지 않으면 0이다.
• $x$ 또는 $y$의 이진 표현에서, $2^k (k \ge 0)$ 자릿수는 $x$와 $y$의 이진 표현 중 적어도 하나에서 $2^k$ 자릿수가 1이면 1이고, 그렇지 않으면 0이다.

예를 들어, $3 \text{ and } 5 = 1, 3 \text{ or } 5 = 7$이다 (이진수로 표현하면 $011 \text{ and } 101 = 001$, $011 \text{ or } 101 = 111$).