คุณได้รับลำดับของจำนวนเต็มบวก $(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$)