F. Questions pack
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Alexander hosted tournaments in the sports version of the game "What? Where? When?" for a long time.

In sports version of "What? Where? When?" several teams of 6 people play simultaneously. The host asks a question, after which, within 60 seconds, the teams must come up with an answer to it and write it down on the answer form. After a minute to think, players have 10 seconds to hand over the forms to the moderator.

Sasha is collecting questions for a new game. The game consists of $$$R$$$ rounds, with $$$Q$$$ questions in each round. There is a database of $$$N$$$ questions; for each question, it is known how many teams tried to answer the question and how many teams answered it incorrectly. Based on this data, a question rating is calculated for each question: the proportion of incorrect answers to the question is counted, multiplied by 10000 and rounded down to an integer. The easiest question has the lowest rating. Sasha wants to form a pack of questions for the game according to the following rules:

  • There must be at least one question in the package with a rating less than $$$L$$$. This question is called "candle" and is answered correctly by almost all teams. If there are several candidates for such a question, then "candle" is the question with the lowest rating among the candidates. A question with a minimum rating in the database may not be a "candle".
  • There must be at least one question in the package with a rating of more than $$$C$$$. Such a question is called "coffin", and only the best teams answer it correctly. If there are several candidates for such a question, then "coffin" is the question with the highest rating among the candidates. The question with the highest rating in the database may not be "coffin".
  • The "candle" question should be in the first half of the game.
  • The "coffin" question should be in the middle of the game. If the number of questions in game is even, then the "coffin" can be any question in the middle.
  • Round ratings should strictly increase to the middle of the game (in the first half), then strictly decrease (in the second half). The rating of each round is the rounded down arithmetic mean of the round questions' ratings.
  • The game needs to be diverse. If we order all the questions in the game by rating $$$Q_1 \le Q_2 \le \dots \le Q_{RQ}$$$, then the complexity of any two consecutive questions $$$Q_i$$$ and $$$Q_{i+1}$$$ satisfies the inequality $$$Q_{i+1} - Q_i \ge D$$$, where $$$D$$$ is the diversity coefficient.
  • If there are more than 2 questions in a round, the question ratings cannot strictly increase or strictly decrease.
  • If you order all the questions in the game by rating $$$Q_1 \le Q_2 \le \dots \le Q_{RQ}$$$, then the complexity of any two consecutive questions $$$Q_i$$$ and $$$Q_{i+1}$$$ should not differ by more than $$$S$$$.

Help Sasha: form a pack of questions for the game, that satisfies the rules above.

Input

The first line of the input contains non-negative integers $$$N, R, Q, L, C, D, S$$$ in accordance with the statement ($$$1 \le N, R, Q \le 10^6$$$, $$$1 \le R \cdot Q \le 10^6$$$, $$$2 \le L, C \le 9999$$$, $$$L \lt C$$$, $$$1 \le D, S \le 10000$$$).

The following $$$N$$$ lines contain two non-negative integers $$$A_i, B_i$$$ — how many teams were asked the question and how many teams answered the question incorrectly ($$$0 \le B_i \le A_i \le 10^9$$$).

Output

If it is possible to form a package without breaking the rules, then output $$$R \cdot Q$$$ integers — the numbers of questions from the database in the order in which they should be asked in the game.

If there are multiple solutions print any of them.

If it is impossible to form a package, output 0.

Example
Input
10 3 2 4000 6000 100 5000
1000 100
1000 200
1000 300
1000 400
1000 500
1000 550
1000 600
1000 700
1000 850
1000 950
Output
4 3 8 7 6 5