Product Bo

Problem Description

Given $N$ real numbers $a_1,a_2,\ldots,a_N$. Consider a subsequence of $a$: $1 \leq s_1 < s_2 < \ldots < s_M \leq N$. Define $f(s) = \prod_{i=1}^{M} a_{s_i}$. Your task is to figure out the $K$-th largest value of $f(s)$ among all the $\binom{N}{M}$ subsequences of length $M$ (same values count multiple times). It is known to all that multiplication of big numbers is troublesome. Therefore, we represent numbers in this format: first, a character '+', '-' or '0', indicating positive, negative, or zero respectively. If it's nonzero, then there follows a space and an integer in $[-10^9,+10^9]$, indicating the logarithm of the absolute value of this number to some fixed base which $\geq 1$.

Input

Multiple test cases. For each test case, the first line contains three integers $N,M,K$. Then follows $N$ lines, the $i$-th of which indicates $a_i$ in the format described above. The input ends with a line $0~0~0$. It is guaranteed that $1 \leq M \leq N, ~ 1 \leq K \leq \binom{N}{M}, ~ N,K \leq 2 \times 10^5$.

Output

For each test case print the answer in the format described above.

Sample Input

3 2 2
+ 3
+ 7
- 2
3 2 2
+ -1
0
0
0 0 0

Sample Output

- 5
0

Author

绍兴一中

Source

2016 Multi-University Training Contest 3