# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Give Me My Vector

By upobir · Limits 5s, 512 MB

I am in a hurry. I have $n$ 2D vectors. And I have created all possible subsets of these $n$ vectors. For each of these subsets, I have determined the sum of the vectors in that set. Now, I have $2^n$ vectors in front of me. I am not really interested in all of them. I just want to lexicographically sort all these vectors and then pick the $k$th smallest one. As I am in a rush, you will have to do this task for me.

Please note that we consider the sum of vectors for an empty set to be the vector $(0, 0)$. To lexicographically compare $(a, b)$ and $(c, d)$ we first compare $a$ and $c$, if $a < c$ then $(a, b)$ is lexicographically smaller, if $a > c$ then $(c, d)$ is lexicographically smaller, if $a=c$ then we compare $b, d$ and the smaller number among $b$ and $d$ belongs to the lexicographically smaller vector.

## Input

The first line of the input will contain a positive integer $T$, the number of testcases.

The first line of each testcase will contain two positive integers $n$ and $k$. Next $n$lines will contain the vectors. The $i$th line will contain two integers $x_i$, $y_i$, the coordinates of the $i$th vector.

$1 \leq T \leq 5$

$1 \leq n \leq 40$

$1 \leq k \leq 2^n$

$|x_i| \leq 10^9, |y_i| \leq 10^9$

## Output

For each test case output in a line two integers $x$ and $y$, coordinates of the lexicographically $k$th sum.

## Sample

InputOutput
2
3 4
1 2
5 -1
2 0
3 5
1 -1
-2 3
-2 5

3 2
-1 2


In the first test case suppose $a = (1 , 2)$, $b = (5, -1)$, $c = (2, 0)$. then the $8$ created vectors are

1. empty set $\to$ $(0, 0)$

2. $a$ $\to$ $(1, 2)$

3. $b$ $\to$ $(5, -1)$

4. $c$ $\to$ $(2, 0)$

5. $a, b$ $\to$ $(6, 1)$

6. $b, c$ $\to$ $(7, -1)$

7. $a, c$ $\to$ $(3, 2)$

8. $a, b, c$ $\to$ $(8, 1)$

### Statistics

50% Solution Ratio

ArcturusEarliest, 1M ago

ArcturusFastest, 2.7s

ArcturusLightest, 51 MB

ArcturusShortest, 4065B