In the distant country of HX, there lives a traveler named Little L who wishes to travel across the country by bicycle. In this country, there are $n$ cities, each with a unique ID from $1$ to $n$. Some cities do not have any attractions that Little L wants to visit, while others have exactly one. Every city falls into one of these two categories. Little L loves informatics, so he wrote a program to arrange a shortest route to visit all the attractions he wants to see (the cities on the travel route are in a specific order): the city he visits $1$st is $a_1$, the city he visits $i$-th is $a_i$, and he ends his trip at city $a_n$. Little L wants to complete this trip in exactly $m$ months ($m < n$), so he needs to create a rational travel plan.

When he arrives at a city, if it has an attraction he wants to visit, he gains $1$ point of happiness; however, if the city has no such attraction, he gains $1$ point of fatigue due to the exhaustion of travel. One month is enough time for him to visit any number of cities, but he also wants to set aside some time to rest. He always rests in the last city he visits each month (if this city has an attraction, Little L will visit it before resting). Of course, Little L wants to have a certain amount of travel tasks each month. Even if the cities he visits in a month do not contain any attractions he wants, he will visit at least one new city each month.

Little L cannot arrange the travel plan himself, so he asks for your help. You need to provide him with a sequence:

$$x_1, x_2, \ldots, x_m$$

$x_i$ represents the ID of the city where Little L rests in the $i$-th month. Since he must complete his trip in the last month, $x_m$ must be equal to $a_n$. For example, if $n=5$ and $m=3$, and the sequence of cities visited is $(a_1, a_2, a_3, a_4, a_5) = (3, 2, 4, 1, 5)$, then $(x_1, x_2, x_3) = (2, 1, 5)$ means: in the first month, he visits city $3$ and then city $2$, resting at city $2$; in the second month, he visits city $4$ and then city $1$, resting at city $1$; in the third month, he visits city $5$ and rests at city $5$.

There are many such sequences. Let $d_i$ be the absolute value of the difference between the happiness points and fatigue points gained during the $i$-th month of a given sequence. Let $c_k$ be the maximum value among $d_1, d_2, \ldots, d_m$ for the $k$-th sequence. Little L wants to choose a sequence such that $c_k$ is minimized among all possible sequences.

In fact, there may be multiple sequences that achieve the same minimum $c_k$. Since Little L loves programming, he has a bit of obsessive-compulsive disorder (though he thinks his OCD makes him shine), and he wants the sequence to be the lexicographically smallest among all those that achieve the minimum $c_k$.

Tip: Comparing the lexicographical order of two sequences means comparing the first element where they differ, e.g., $(1, 2, 3, 4) < (1, 2, 4, 3)$.

Input

The first line contains two space-separated positive integers $n$ and $m$, representing the number of cities and the number of months for the trip.

The next $n$ lines each contain two space-separated integers $a_i$ and $b_i$, where $a_i$ is the ID of the $i$-th city visited, and $b_i$ is $0$ or $1$. If $b_i=0$, the city $a_i$ has no attraction; if $b_i=1$, the city $a_i$ has an attraction.

All $a_i$ are distinct and $1 \le a_i \le n$, meaning $\{a_i\}$ is a permutation of $1, 2, \ldots, n$.

Output

Output the lexicographically smallest sequence $x_1, x_2, \ldots, x_m$ that minimizes the maximum monthly absolute difference between happiness and fatigue.

Examples

Input 1

8 3
2 0
3 1
4 1
1 0
5 0
6 1
7 1
8 0

Output 1

1 6 8

Note 1

In the first month, he gains 2 happiness and 2 fatigue points; in the second month, 1 happiness and 1 fatigue point; in the third month, 1 happiness and 1 fatigue point. The maximum absolute difference between fatigue and happiness over the 3 months is 0, which is the minimum possible.

Possible sequences include: - 1 6 8 - 3 6 8 - 3 1 8

Among these, 1 6 8 is lexicographically smallest.

Input 2

8 6 
2 0
3 1
4 1
1 0
5 0
6 1
7 1
8 0

Output 2

2 1 5 6 7 8

Note 2

In each of the 6 months, the absolute difference between fatigue and happiness is 1, so the maximum difference is 1, which is the minimum possible.

Subtasks

• For $10\%$ of the data, $n \le 10$;
• For $25\%$ of the data, $m \le 10$;
• For $30\%$ of the data, $n \le 100$;
• For $40\%$ of the data, $m \le 100$;
• For $40\%$ of the data, $n \le 1\,000$;
• For $55\%$ of the data, $n \le 180\,000$;
• For $100\%$ of the data, $n \le 500\,000$, $m \le 200\,000$.