Maximize the Boasting Contest Winners

In an ICPC‐style contest, teams are ranked firstly by the number of solved problems (in descending order) and secondly by the total penalty (in ascending order). There are (n) elite contestants competing for glory over (m) minutes. In the beginning of minute (i) (with (0 \le i \le m-1)), the contestant with index (s_i) submits (t_i) wrong answers (each wrong answer attracts a penalty of (x) minutes) and then solves one problem. Thus, after that submission, the contestant’s solved count increases by 1 and the total penalty increases by (x\times t_i + i) minutes.

For each contestant (i) ((1 \le i \le n)), they make exactly (a_i) submissions (so that (\sum_{i=1}^{n}a_i=m)) and accumulate a total of (k_i) wrong answers over all submissions.

After a contestant finishes all their submissions, if they find that their score is uniquely first (i.e. no tie for first place) in the current scoreboard, they are said to have achieved a Boast-Worthy Contest (i.e. “爆切比赛”).

Your task is to construct two sequences ({s_i}{i=0}^{m-1}) and ({t_i}{i=0}^{m-1}) satisfying the following conditions:

1. For each contestant (i), they appear exactly (a_i) times in the sequence ({s_i}).
2. For each contestant (i), the sum of all (t_j) with (s_j=i) equals (k_i).
3. The sequences maximize the number of contestants who, immediately after finishing all their own submissions, find themselves uniquely at the top of the scoreboard.

It is guaranteed that (\sum_{i=1}^{n}a_i=m).

Scoring and Ranking Details:

• Contestants are ranked first by the number of solved problems (more is better) and then by total penalty (less is better).
• The penalty for a contestant is the sum of \(x\times (\text{wrong attempts in the submission}) + (\text{minute index of that submission})\) over all their submissions.

Note: You may output any valid sequences that satisfy the above conditions. If a contestant has the same solved count as another, only the one with the lower penalty is ranked first. Hence, if two contestants have the same (a_i) value, only the one whose submission block is scheduled earlier (thus incurring a lower final minute) can possibly achieve the boast‐worthy status.

Input/Output Format:

• Input: The first line contains three integers \(n\), \(m\) and \(x\) \( (1 \le n \le 10^5,\; 1 \le m \le 10^5, \; 1 \le x \le 10^5)\). Then \(n\) lines follow. The \(i\)th of these lines contains two integers \(k_i\) and \(a_i\) \( (0 \le k_i \le 10^9,\; 1 \le a_i \le m)\). It is guaranteed that \(\sum_{i=1}^{n}a_i=m\).
• Output: Output two lines. The first line contains \(m\) integers \(s_0, s_1, \ldots, s_{m-1}\), where each \(s_i\) (using 1-indexed contestant ids) indicates the contestant making a submission in minute \(i\). The second line contains \(m\) integers \(t_0, t_1, \ldots, t_{m-1}\) representing the number of wrong attempts submitted in that minute by the corresponding contestant. These sequences must satisfy the conditions described above and be constructed so as to maximize the number of "boast-worthy" contestants.

  inputFormat

  The first line contains three integers (n), (m), and (x). Each of the next (n) lines contains two integers (k_i) and (a_i) for the (i)th contestant. It is guaranteed that (\sum_{i=1}^{n} a_i = m).

  outputFormat

  Output two lines: the first line contains (m) integers representing the sequence ({s_i}) (contestant ids) for each minute from 0 to (m-1); the second line contains (m) integers representing the sequence ({t_i}) for the number of wrong attempts at that minute. These sequences must satisfy the input specified counts and maximize the number of contestants who, upon finishing their submissions, are uniquely ranked first.

  sample

  2 3 10
  2 1
  1 2

  1 2 2
  2 0 1

  </p>