Universal Cup Judging System

Universal Cup

実行時間制限: 5.0 s メモリ制限: 1024 MB 満点: 100 ハック可能 ✓
統計

畀定一個長度為 $N$ 嘅正整數序列 $(A_1, \dots, A_N)$。考慮將呢個序列 $A$ 劃分成 $M$ 個連續而且非空嘅子序列 $B_1, B_2, \dots, B_M$。

對於一個子序列 $B = (A_L, \dots, A_R)$,定義佢嘅分數為 $$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}$$ 其中 $x \text{ and } y$ 同 $x \text{ or } y$ 分別代表 $x$ 同 $y$ 嘅按位元與(AND)同按位元或(OR)。

一旦固定咗一個劃分,我哋就會得到 $M$ 個數值 $S(B_1), \dots, S(B_M)$ 作為各個子序列嘅分數。將呢啲數值按降序排列,並定義呢個劃分嘅分數為該順序下嘅第 $K$ 個數值。考慮所有可能嘅劃分,搵出劃分分數嘅最大可能值同最小可能值。

Input

第一行按順序包含整數 $N, M, K$。($1 \le K \le M \le N \le 10^5$)

第二行按順序包含 $N$ 個整數 $A_1, \dots, A_N$。($1 \le A_i < 2^{30}\ (1 \le i \le N)$)

Output

印出 $2$ 行。

設最大值同最小值分別為 $\frac{p}{q}, \frac{r}{s}$,其中 $p, r \ge 0$,$q, s \ge 1$,$\gcd(p, q) = \gcd(r, s) = 1$。喺第一行印出 $p, q$,喺第二行印出 $r, s$,按呢個順序並以空格分隔。

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

對於第一個範例,如果我哋揀 $B_1 = (6)$、$B_2 = (5, 7)$、$B_3 = (3, 2)$,咁 $S(B_1) = 1$、$S(B_2) = \frac{5}{7}$、$S(B_3) = \frac{2}{3}$。當呢啲數值按降序排列嗰陣,第 $3$ 個數值係 $\frac{2}{3}$。

另外,如果我哋揀 $B_1 = (6)$、$B_2 = (5, 7, 3)$、$B_3 = (2)$,咁 $S(B_1) = 1$、$S(B_2) = \frac{1}{7}$、$S(B_3) = 1$。當呢啲數值按降序排列嗰陣,第 $3$ 個數值係 $\frac{1}{7}$。

非負整數 $x, y$ 嘅按位元與 $x \text{ and } y$ 同按位元或 $x \text{ or } y$ 定義如下。

  • 喺 $x \text{ and } y$ 嘅二進制表示入面,$2^k\ (k \ge 0)$ 位上面嘅數字係 $1$ 當且僅當 $x$ 同 $y$ 嘅二進制表示喺 $2^k$ 位上面嘅數字都係 $1$;否則係 $0$。
  • 喺 $x \text{ or } y$ 嘅二進制表示入面,$2^k\ (k \ge 0)$ 位上面嘅數字係 $1$ 當且僅當 $x$ 同 $y$ 嘅二進制表示喺 $2^k$ 位上面嘅數字至少有一個係 $1$;否則係 $0$。

例如,$3 \text{ and } 5 = 1$,$3 \text{ or } 5 = 7$(喺二進制入面,$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.