Anda diberikan sebuah barisan bilangan bulat positif $(A_1, \dots, A_N)$ dengan panjang $N$. Tinjau pemartisian barisan $A$ ini menjadi $M$ subbarisan berurutan tak kosong $B_1, B_2, \dots, B_M$.
Untuk sebuah subbarisan $B = (A_L, \dots, A_R)$, definisikan skornya dengan $$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}$$ di mana $x \text{ and } y$ serta $x \text{ or } y$ masing-masing menyatakan operasi bitwise AND dan bitwise OR dari $x$ dan $y$.
Setelah sebuah partisi ditetapkan, kita memperoleh $M$ nilai $S(B_1), \dots, S(B_M)$ sebagai skor dari subbarisan-subbarisan tersebut. Urutkan nilai-nilai ini dalam urutan menurun, dan definisikan skor dari partisi tersebut sebagai nilai ke-$K$ dalam urutan itu. Dengan meninjau semua partisi yang mungkin, carilah nilai maksimum dan minimum yang mungkin dari skor partisi.
Input
Baris pertama berisi bilangan bulat $N, M, K$ sesuai urutan tersebut. ($1 \le K \le M \le N \le 10^5$)
Baris kedua berisi $N$ bilangan bulat $A_1, \dots, A_N$ sesuai urutan tersebut. ($1 \le A_i < 2^{30}\ (1 \le i \le N)$)
Output
Cetak $2$ baris.
Misalkan nilai maksimum dan minimum masing-masing adalah $\frac{p}{q}, \frac{r}{s}$, di mana $p, r \ge 0$, $q, s \ge 1$, $\gcd(p, q) = \gcd(r, s) = 1$. Cetak $p, q$ pada baris pertama, dan $r, s$ pada baris kedua, dipisahkan oleh spasi, sesuai urutan tersebut.
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
Untuk contoh pertama, jika kita memilih $B_1 = (6)$, $B_2 = (5, 7)$, $B_3 = (3, 2)$, maka $S(B_1) = 1$, $S(B_2) = \frac{5}{7}$, $S(B_3) = \frac{2}{3}$. Ketika nilai-nilai ini diurutkan dalam urutan menurun, nilai ke-$3$ adalah $\frac{2}{3}$.
Selain itu, jika kita memilih $B_1 = (6)$, $B_2 = (5, 7, 3)$, $B_3 = (2)$, maka $S(B_1) = 1$, $S(B_2) = \frac{1}{7}$, $S(B_3) = 1$. Ketika nilai-nilai ini diurutkan dalam urutan menurun, nilai ke-$3$ adalah $\frac{1}{7}$.
Operasi bitwise AND $x \text{ and } y$ dan bitwise OR $x \text{ or } y$ dari bilangan bulat tak negatif $x, y$ didefinisikan sebagai berikut.
- Dalam representasi biner dari $x \text{ and } y$, digit pada posisi $2^k\ (k \ge 0)$ bernilai $1$ jika dan hanya jika digit pada posisi $2^k$ dalam representasi biner dari kedua $x$ dan $y$ bernilai $1$; jika tidak, nilainya adalah $0$.
- Dalam representasi biner dari $x \text{ or } y$, digit pada posisi $2^k\ (k \ge 0)$ bernilai $1$ jika dan hanya jika setidaknya salah satu digit pada posisi $2^k$ dalam representasi biner dari $x$ dan $y$ bernilai $1$; jika tidak, nilainya adalah $0$.
Sebagai contoh, $3 \text{ and } 5 = 1$, $3 \text{ or } 5 = 7$ (dalam biner, $011 \text{ and } 101 = 1$, $011 \text{ or } 101 = 111$).