Competition#481

Competition

1 second
256 megabytes
Easy

There are teams invited to a competition. During the sponsor talk, every team must be present most of the time. If a team is absent for more than continuous minutes at any moment, this team will be disqualified.

The sponsor talk starts at time . Initially, at time , all teams are present.

You are given events. Each event is described by two integers time and idx:

When the event (\texttt{time}, \texttt{idx}) happens:

Between events, the state of each team (present or absent) does not change.

Let be the maximum time among all events. The sponsor talk ends at time . For each team, consider all its continuous absence intervals during the time segment . If there exists such an interval whose length is strictly greater than , then this team is disqualified. Being absent for exactly continuous minutes is allowed.

Determine which teams are disqualified.

Input

The first line contains three integers , , and (1 \le N \le 200000, 0 \le Q \le 200000, 1 \le X \le 10^9).

Each of the next lines contains two integers time and idx (0 \le \texttt{time} \le 10^9, 1 \le \texttt{idx} \le N) — one event.

Events are given in arbitrary order. For every team, no two events have the same time.

Output

In the first line, print the number of disqualified teams.

In the second line, print the indices of all disqualified teams in increasing order, separated by spaces.

Examples

Example 1

Loading
Loading

Note

In the example, N = 3, X = 4. All teams are present at time . The events in chronological order are:

  • time , team leaves;

  • time , team leaves;

  • time , team comes back;

  • time , team comes back.

The last event time is T = 8, so we consider the interval .

  • Team is absent from time to time (duration ). Since 5 > X = 4, team is disqualified.

  • Team is absent from time to time (duration ). This is also greater than , so team is disqualified.

  • Team never leaves, so it is always present and not disqualified.

Therefore, the disqualified teams are 1 and 2.