Problem D
Nasa

Hypothetically, we can consider the wormhole as a straight segment divided into $N$ equal length sectors numbered from 1 to $N$ that the astronaut ship will follow exactly in that order. Depending on the time space distortions encountered, the ship can go through at least $p$ sectors and no more than $q$ sectors within a sidereal year (UTC - Coordinated Universal Time). For each sector, the captain Pipo has to inform the Nasa about the year he was in. Due to interference reasons, the data transmission is deficient. Thus, the Nasa does not receive information from all $N$ sectors.

Given the description of $M$ transmissions received by the Nasa of the form: $s$ $t$, where $s$ is the index of a sector, and $t$ is the year it is traveled, your task is to determine the maximum number of years in which the wormhole formed by $N$ sectors numbered from 1 to $N$. You are also asked to describe the sequence of years $y_1,y_2,\ldots ,y_ N$ where $y_ i$ indicates the year when the ship is in the sector $i$, $i=1\ldots N$.

Input

The first line contains 4 natural numbers $N, p, q$ and $M$ separated by a space, with the meaning in the statement. The following $M$ lines describe the corresponding $M$ transmissions received by the Nasa in the ascending order of years and sectors.

Output

There are two lines. The first line contains a natural number $A$, which is the maximum number of sidereal years required for the $N$ sectors. The second line contains the sequence $y_1,y_2,\ldots ,y_ N$. If there are different such sequences, write out the one with the minimum lexicographic order.

Specification

• $2 \leq N \leq 100000$;

• $2 \leq p <q \leq N$;

• $1 \leq M \leq N$;

• each sector must be fully covered within the same sidereal year;

• the entire journey must be traveled to a whole number of years (i.e.: the passage of at least $p$ sectors and no more than $q$ sectors is valid for the first and last year);

• there is always a solution for each input data.

Sample Clarification

In the samples below,

• In the first sample, we know that the second sector is in the first year.

  1 1 2 2 3 can not be a solution because in the 3rd year there are not at least 2 sectors traveled as required.

  It takes 2 years to complete all 5 sectors.

  The first 3 sectors will be covered in the first year, the next two sectors in the second year.

• In the second sample, it takes 3 years to complete all 7 sectors.

  The first 3 sectors will be covered in the first year, the next two sectors in the second year, and the last two sectors in the third year.

• In the third sample, it takes 5 years to go through all 16 sectors.

5 2 3 1
2 1

2
1 1 1 2 2

7 2 5 2
2 1
6 3

3
1 1 1 2 2 3 3

16 3 4 2
5 2
15 5

5
1 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5