Universal Cup Judging System

Universal Cup

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

Sinulle annetaan positiivisten kokonaislukujen jono $(A_1, \dots, A_N)$, jonka pituus on $N$. Tarkastellaan tämän jonon $A$ osittamista $M$:ään yhtenäiseen epätyhjään osajonoon $B_1, B_2, \dots, B_M$.

Osajonolle $B = (A_L, \dots, A_R)$ määritellään sen pistemäärä kaavalla $$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}$$ missä $x \text{ and } y$ ja $x \text{ or } y$ tarkoittavat lukujen $x$ ja $y$ bittikohtaista JA-operaatiota (AND) ja bittikohtaista TAI-operaatiota (OR).

Kun ositus on kiinnitetty, saamme osajonojen pistemäärinä $M$ arvoa $S(B_1), \dots, S(B_M)$. Järjestetään nämä arvot laskevaan järjestykseen ja määritellään osituksen pistemääräksi $K$-s arvo tässä järjestyksessä. Kun huomioidaan kaikki mahdolliset ositukset, etsi osituksen pistemäärän suurin ja pienin mahdollinen arvo.

Input

Ensimmäinen rivi sisältää kokonaisluvut $N, M, K$ tässä järjestyksessä. ($1 \le K \le M \le N \le 10^5$)

Toinen rivi sisältää $N$ kokonaislukua $A_1, \dots, A_N$ tässä järjestyksessä. ($1 \le A_i < 2^{30}\ (1 \le i \le N)$)

Output

Tulosta $2$ riviä.

Olkoot suurin ja pienin arvo $\frac{p}{q}, \frac{r}{s}$, missä $p, r \ge 0$, $q, s \ge 1$, $\gcd(p, q) = \gcd(r, s) = 1$. Tulosta $p, q$ ensimmäiselle riville ja $r, s$ toiselle riville välilyönneillä erotettuina tässä järjestyksessä.

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

Ensimmäisessä esimerkissä, jos valitsemme $B_1 = (6)$, $B_2 = (5, 7)$, $B_3 = (3, 2)$, niin $S(B_1) = 1$, $S(B_2) = \frac{5}{7}$, $S(B_3) = \frac{2}{3}$. Kun nämä järjestetään laskevaan järjestykseen, $3$. arvo on $\frac{2}{3}$.

Lisäksi, jos valitsemme $B_1 = (6)$, $B_2 = (5, 7, 3)$, $B_3 = (2)$, niin $S(B_1) = 1$, $S(B_2) = \frac{1}{7}$, $S(B_3) = 1$. Kun nämä järjestetään laskevaan järjestykseen, $3$. arvo on $\frac{1}{7}$.

Ei-negatiivisten kokonaislukujen $x, y$ bittikohtainen JA $x \text{ and } y$ ja bittikohtainen TAI $x \text{ or } y$ määritellään seuraavasti.

  • Luvun $x \text{ and } y$ binääriesityksessä kohdan $2^k\ (k \ge 0)$ numero on $1$, jos ja vain jos sekä luvun $x$ että luvun $y$ binääriesityksessä kohdan $2^k$ numero on $1$; muuten se on $0$.
  • Luvun $x \text{ or } y$ binääriesityksessä kohdan $2^k\ (k \ge 0)$ numero on $1$, jos ja vain jos vähintään toisessa lukujen $x$ ja $y$ binääriesityksistä kohdan $2^k$ numero on $1$; muuten se on $0$.

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