F. MPFT
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Teralem joined a group chat, which can hold at most $$$N$$$ members. When the group is full and a person is still trying to join the group, the member whose latest message is the earliest will be kicked out, allowing the new comer to join.

However, this rule made the members in the group sending messages all the time in fear of being kicked out. Soon the group is filled with meaningless messages. To make the situation better, another rule is made: once a member has sent $$$K$$$ messages in the latest time period of $$$T$$$ (including the beginning moment and the ending moment), the member is kicked out immediately.

Please notice:

  • When a member joins the group, a "hello" message is automatically sent. So it can be guaranteed that any member in the group will have the latest message.
  • If a person was kicked out and rejoined the group during the latest time period of $$$T$$$, only the messages after the person's latest joining will be counted (including the "hello" message).

Suppose the group is empty in the beginning. A series of events will be given in order of time, which can be either a person joinning the group or a person sending a message. Please output every kickouts in order of time and the members in the group after the last event.

Input

The first line contains four integers $$$N, M, T, K$$$ $$$(1\leq N \leq 10^6, 1\leq M \leq 10^6, 1\leq T \leq 10^9, 1\leq K \leq 10^6)$$$. The meanings of $$$N, M, K$$$ are as above. $$$M$$$ represents the number of the given events.

The following $$$M$$$ lines describe the given events. The $$$i$$$-th line contains two integers $$$t_i, p_i$$$ $$$(1\leq t_i \leq 10^9, 1 \leq p_i \leq 10^6)$$$. If the person $$$p_i$$$ was in the group at the moment before $$$t_i$$$, it means the person $$$p_i$$$ sent a message at time $$$t_i$$$, otherwise it means the person $$$p_i$$$ joined the group at time $$$t_i$$$. It is guaranteed that $$$t_i \lt t_{i+1}$$$ for $$$1\leq i \lt M$$$.

Output

The first line contains two integers $$$A, B$$$, representing the number of kickouts and the number of members in the group in the end repectively.

The following $$$A$$$ lines each contains two positive integers representing the time of the kickout and the person been kicked out repectively. The kickout time must be strictly monotonically increasing.

The following line contains $$$B$$$ positive integers, representing the members in the group finally. You can output in any order.

Example
Input
4 5 1 2
1 2
2 3
3 4
4 4
5 1
Output
1 3
4 4
1 3 2