Universal Cup Judging System

Universal Cup

Time Limit: 5.0 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

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$).

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1524EditorialOpen题解jianglyView

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.