Một cảng biển có \(m\) cầu cảng để tiếp nhận các tàu cập bến. Tại một thời điểm, mỗi cầu cảng chỉ có thể tiếp nhận không quá 1 tàu. Ban đầu các cầu cảng đều trống và có \(n\) tàu xin đăng ký cập bến, tàu thứ \(i\) muốn đậu ở cảng từ ngay sau thời điểm \(s_i\) tới hết thời điểm \(f_i\). Có thể coi thời gian tàu thứ \(i\) muốn đậu ở cảng là một khoảng \((s_i, f_i]\) trên trục thời gian. Tàu đã vào cầu cảng nào thì sẽ đậu ở đó trong suốt thời gian nằm cảng.

Yêu cầu: Hãy cho biết với \(m\) cầu cảng đã cho, có thể tiếp nhận tối đa bao nhiêu tàu và chỉ ra lịch trình tiếp nhận tại mỗi cầu cảng.

Input

• Dòng 1: Chứa hai số nguyên dương \(m, n \leq 10^5\).
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(s_i\), \(f_i\) (\(0 \leq s_i < f_i \leq 10^5\)).

Các số trên một dòng của Input/Output files được/phải ghi cách nhau ít nhất một dấu cách.

Output

• Dòng 1: Ghi số lượng tàu được tiếp nhận phục vụ.
• Dòng 2: Ghi \(n\) số nguyên, số thứ \(i\) là số hiệu cầu cảng sẽ tiếp nhận tàu thứ \(i\) trong trường hợp tàu thứ \(i\) được tiếp nhận, còn nếu tàu thứ \(i\) không được tiếp nhận thì số thứ \(i\) là \(0\).

Example

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

4
1 1 2 2 0

Scoring

• Subtask 1: \(m, n \leq 400\).
• Subtask 2: \(m, n \leq 10^4\).
• Subtask 3: \(m, n \leq 10^5\).

Nguồn: LHM