נתונה לכם סדרה של מספרים שלמים חיוביים $(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$).