题目描述

一条虫洞可以看成一条被划分为 N 个等长扇区的线段，扇区从 1 到 N 编号，飞船必须按编号从小到大依次穿过这些扇区。

由于时空扰动，飞船在一个星历年中至少穿过 p 个扇区，至多穿过 q 个扇区。每个扇区必须完整地在同一年内穿过。

舰长需要向联邦报告每个扇区是在第几年穿过的，但由于干扰，联邦只收到其中 M 条传输。每条传输形如 s t，表示扇区 s 是在第 t 年穿过的。

请在满足所有已知传输的前提下，求飞船穿过全部 N 个扇区最多需要多少年，并输出一种字典序最小的年份序列。

输入格式

第一行包含四个整数 N p q M。

接下来 M 行，每行包含两个整数 s t，表示收到的一条传输。

题面说明这些传输按年份和扇区的递增顺序给出。

输出格式

第一行输出一个正整数 A，表示最多需要的星历年数。

第二行输出 N 个整数，第 i 个整数表示扇区 i 被穿过的年份。要求在所有能达到最大年份数的合法方案中，输出字典序最小的年份序列。

数据范围与约定

• 2 <= N <= 100000；
• 2 <= p < q <= N；
• 1 <= M <= N；
• 每个扇区必须完整地在同一年内穿过；
• 第一年的扇区数和最后一年的扇区数也都必须在 [p, q] 内；
• 保证输入一定有解；
• 30 分：N <= 100，q <= 50；
• 70 分：N <= 30000，q <= 300；
• 100 分：N <= 100000。

样例 1

5 2 3 1
2 1

2
1 1 1 2 2

样例 2

7 2 5 2
2 1
6 3

3
1 1 1 2 2 3 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