Universal Cup Judging System

Universal Cup

Límite de tiempo: 5.0 s Límite de memoria: 1024 MB Puntuación total: 100 Hackeable ✓
Estadísticas

Gegeben ist eine Folge positiver ganzer Zahlen $(A_1, \dots, A_N)$ der Länge $N$. Betrachte eine Zerlegung dieser Folge $A$ in $M$ zusammenhängende, nichtleere Teilfolgen $B_1, B_2, \dots, B_M$.

Für eine Teilfolge $B = (A_L, \dots, A_R)$ ist ihr Wert definiert durch $$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}$$ wobei $x \text{ and } y$ bzw. $x \text{ or } y$ das bitweise UND (AND) bzw. das bitweise ODER (OR) von $x$ und $y$ bezeichnen.

Sobald eine Zerlegung festgelegt ist, erhalten wir $M$ Werte $S(B_1), \dots, S(B_M)$ als die Werte der Teilfolgen. Sortiere diese Werte in absteigender Reihenfolge und definiere den Wert der Zerlegung als den $K$-ten Wert in dieser Reihenfolge. Finde unter allen möglichen Zerlegungen den maximalen und den minimalen möglichen Wert der Zerlegung.

Input

Die erste Zeile enthält die ganzen Zahlen $N, M, K$ in dieser Reihenfolge. ($1 \le K \le M \le N \le 10^5$)

Die zweite Zeile enthält $N$ ganze Zahlen $A_1, \dots, A_N$ in dieser Reihenfolge. ($1 \le A_i < 2^{30}\ (1 \le i \le N)$)

Output

Gib $2$ Zeilen aus.

Seien der maximale und der minimale Wert $\frac{p}{q}, \frac{r}{s}$, wobei $p, r \ge 0$, $q, s \ge 1$, $\gcd(p, q) = \gcd(r, s) = 1$. Gib $p, q$ in der ersten Zeile und $r, s$ in der zweiten Zeile, jeweils durch Leerzeichen getrennt, in dieser Reihenfolge aus.

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

Wenn wir im ersten Beispiel $B_1 = (6)$, $B_2 = (5, 7)$, $B_3 = (3, 2)$ wählen, gilt $S(B_1) = 1$, $S(B_2) = \frac{5}{7}$, $S(B_3) = \frac{2}{3}$. Wenn diese absteigend sortiert werden, ist der $3$-te Wert $\frac{2}{3}$.

Wenn wir außerdem $B_1 = (6)$, $B_2 = (5, 7, 3)$, $B_3 = (2)$ wählen, gilt $S(B_1) = 1$, $S(B_2) = \frac{1}{7}$, $S(B_3) = 1$. Wenn diese absteigend sortiert werden, ist der $3$-te Wert $\frac{1}{7}$.

Das bitweise UND $x \text{ and } y$ und das bitweise ODER $x \text{ or } y$ nichtnegativer ganzer Zahlen $x, y$ sind wie folgt definiert:

  • In der Binärdarstellung von $x \text{ and } y$ ist die Ziffer an der Stelle $2^k\ (k \ge 0)$ genau dann $1$, wenn die Ziffern an der Stelle $2^k$ in den Binärdarstellungen von sowohl $x$ als auch $y$ gleich $1$ sind; andernfalls ist sie $0$.
  • In der Binärdarstellung von $x \text{ or } y$ ist die Ziffer an der Stelle $2^k\ (k \ge 0)$ genau dann $1$, wenn mindestens eine der Ziffern an der Stelle $2^k$ in den Binärdarstellungen von $x$ und $y$ gleich $1$ ist; andernfalls ist sie $0$.

Beispielsweise gilt $3 \text{ and } 5 = 1$, $3 \text{ or } 5 = 7$ (binär: $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.