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:
idx is the index of a team (1 \le \texttt{idx} \le N),
time is the time of the event (in minutes, 0 \le \texttt{time} \le 10^9).
When the event (\texttt{time}, \texttt{idx}) happens:
if team idx is currently present, it leaves (becomes absent);
if team idx is currently absent, it comes back (becomes present).
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.
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.
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.
Example 1
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.