長さ\(N\)の正整数列 \((A_1,\ldots,A_N)\) が与えられます。 この数列 \(A\) を、\(M\) 個の連続する空でない部分列 \(B_1,B_2,\ldots,B_M\) に分割することを考えます。
部分列 \(B=(A_L,\ldots,A_R)\) のスコアを \[S(B) = \dfrac{A_L \mathbin{\mathrm{and}} A_{L+1} \mathbin{\mathrm{and}} \cdots \mathbin{\mathrm{and}} A_R}{A_L \mathbin{\mathrm{or}} A_{L+1} \mathbin{\mathrm{or}} \cdots \mathbin{\mathrm{or}} A_R}\] で定めます。ここで、\(x \mathbin{\mathrm{and}} y, \ x \mathbin{\mathrm{or}} y\) はそれぞれ \(x\) と \(y\) のビット単位AND、ビット単位ORを表します。
ある分割を決めたとき、各部分列のスコアとして \(M\) 個の値 \(S(B_1),\ldots,S(B_M)\) が得られますが、これらの値を降順に並べたときの \(K\) 番目の値を、分割のスコアとして定めます。 すべての分割を考えるとき、分割のスコアとしてあり得る最大値と最小値を求めてください。
\(1\) 行目に整数 \(N, M, K\) がこの順で与えられる。 (\(1 \leq K \leq M \leq N \leq 10^5\))
\(2\) 行目に \(N\) 個の整数 \(A_1,\ldots,A_N\) がこの順で与えられる。 (\( 1 \leq A_i \lt 2^{30} \ (1 \leq i \leq N)\))
\(2\) 行出力せよ。
最大値、最小値をそれぞれ\( \dfrac{p}{q}, \ \dfrac{r}{s} \ (p,r \geq 0, \ q,s \geq 1, \gcd(p,q) = \gcd(r,s) = 1)\)としたとき、 \(1\) 行目には \(p,q\) を、 \(2\) 行目には \(r,s\) を、この順で空白区切りで出力せよ。
5 3 36 5 7 3 2
2 3 1 7
5 1 13 1 4 1 5
0 1 0 1
9 5 3998 244 353 469 762 49 754 974 721
1 1 208 1023
\(1\) つ目のケースについて、\(B_1 = (6), \ B_2 = (5, 7), \ B_3 = (3, 2)\) と選ぶと、\(S(B_1) = 1, \ S(B_2) = \dfrac{5}{7}, \ S(B_3) = \dfrac{2}{3}\) であり、これらを降順に並べたときの \(3\) 番目の値は \(\dfrac{2}{3}\) です。
また、\(B_1 = (6), \ B_2 = (5,7,3), \ B_3 = (2)\) と選ぶと、\(S(B_1) = 1, \ S(B_2) = \dfrac{1}{7}, S(B_3) = 1\) であり、これらを降順に並べたときの \(3\) 番目の値は \(\dfrac{1}{7}\) です。
非負整数 \(x,y\) のビット単位 AND \(x \mathbin{\mathrm{and}} y\)、ビット単位OR \(x \mathbin{\mathrm{or}} y\) は以下のように定義されます。