Bạn được cho một dãy các số nguyên dương $(A_1, \dots, A_N)$ có độ dài $N$. Hãy xem xét việc phân hoạch dãy $A$ này thành $M$ dãy con liên tiếp không rỗng $B_1, B_2, \dots, B_M$.

Với một dãy con $B = (A_L, \dots, A_R)$, định nghĩa điểm số của nó là $$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}$$ trong đó $x \text{ and } y$ và $x \text{ or } y$ lần lượt biểu thị phép toán bitwise AND và bitwise OR của $x$ và $y$.

Sau khi một cách phân hoạch được cố định, ta thu được $M$ giá trị $S(B_1), \dots, S(B_M)$ là điểm số của các dãy con. Sắp xếp các giá trị này theo thứ tự giảm dần và định nghĩa điểm số của cách phân hoạch là giá trị lớn thứ $K$ trong thứ tự đó.

Xét tất cả các cách phân hoạch có thể, hãy tìm giá trị lớn nhất và nhỏ nhất có thể của điểm số phân hoạch.

Dữ liệu vào

Dòng đầu tiên chứa các số nguyên $N, M, K$ theo thứ tự đó. $(1 \le K \le M \le N \le 10^5)$

Dòng thứ hai chứa $N$ số nguyên $A_1, \dots, A_N$ theo thứ tự đó. $(1 \le A_i < 2^{30} (1 \le i \le N))$

Dữ liệu ra

In ra 2 dòng.

Gọi giá trị lớn nhất và nhỏ nhất lần lượt là $\frac{p}{q}$ và $\frac{r}{s}$, trong đó $p, r \ge 0, q, s \ge 1$, $\gcd(p, q) = \gcd(r, s) = 1$. In ra $p, q$ trên dòng đầu tiên, và $r, s$ trên dòng thứ hai, cách nhau bởi dấu cách, theo thứ tự đó.

Ví dụ

Dữ liệu vào 1

5 3 3
6 5 7 3 2

Dữ liệu ra 1

2 3
1 7

Dữ liệu vào 2

5 1 1
3 1 4 1 5

Dữ liệu ra 2

0 1
0 1

Dữ liệu vào 3

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

Dữ liệu ra 3

1 1
208 1023

Ghi chú

Với ví dụ đầu tiên, nếu ta chọn $B_1 = (6), B_2 = (5, 7), B_3 = (3, 2)$, thì $S(B_1) = 1, S(B_2) = \frac{5}{7}, S(B_3) = \frac{2}{3}$. Khi các giá trị này được sắp xếp theo thứ tự giảm dần, giá trị thứ 3 là $\frac{2}{3}$.

Ngoài ra, nếu ta chọn $B_1 = (6), B_2 = (5, 7, 3), B_3 = (2)$, thì $S(B_1) = 1, S(B_2) = \frac{1}{7}, S(B_3) = 1$. Khi các giá trị này được sắp xếp theo thứ tự giảm dần, giá trị thứ 3 là $\frac{1}{7}$.

Phép toán bitwise AND $x \text{ and } y$ và bitwise OR $x \text{ or } y$ của các số nguyên không âm $x, y$ được định nghĩa như sau:

• Trong biểu diễn nhị phân của $x$ và $y$, chữ số tại vị trí $2^k$ ($k \ge 0$) là 1 nếu và chỉ nếu các chữ số tại vị trí $2^k$ trong biểu diễn nhị phân của cả $x$ và $y$ đều là 1; ngược lại, nó là 0.
• Trong biểu diễn nhị phân của $x \text{ or } y$, chữ số tại vị trí $2^k$ ($k \ge 0$) là 1 nếu và chỉ nếu ít nhất một trong các chữ số tại vị trí $2^k$ trong biểu diễn nhị phân của $x$ và $y$ là 1; ngược lại, nó là 0.

Ví dụ, $3 \text{ and } 5 = 1, 3 \text{ or } 5 = 7$ (trong hệ nhị phân, $011 \text{ and } 101 = 1, 011 \text{ or } 101 = 111$).