أُعطيت متتالية من الأعداد الصحيحة الموجبة $(A_1, \dots, A_N)$ بطول $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$ عمليتي AND البتية و OR البتية للعددين $x$ و $y$ على التوالي.
بمجرد تثبيت التجزئة، نحصل على $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}$.
تُعرَّف عملية AND البتية $x \text{ and } y$ وعملية OR البتية $x \text{ or } y$ للعددين الصحيحين غير السالبين $x, y$ كما يلي:
- في التمثيل الثنائي لـ $x \text{ and } y$، تكون الخانة في المنزلة $2^k\ (k \ge 0)$ مساوية لـ $1$ إذا وفقط إذا كانت الخانتان في المنزلة $2^k$ في التمثيلين الثنائيين لكل من $x$ و $y$ مساويتين لـ $1$؛ وإلا فإنها تكون $0$.
- في التمثيل الثنائي لـ $x \text{ or } y$، تكون الخانة في المنزلة $2^k\ (k \ge 0)$ مساوية لـ $1$ إذا وفقط إذا كانت إحدى الخانتين على الأقل في المنزلة $2^k$ في التمثيلين الثنائيين لـ $x$ و $y$ مساوية لـ $1$؛ وإلا فإنها تكون $0$.
على سبيل المثال، $3 \text{ and } 5 = 1$ و $3 \text{ or } 5 = 7$ (في النظام الثنائي، $011 \text{ and } 101 = 1$ و $011 \text{ or } 101 = 111$).