UVA12490 Integral

给定一个正整数 $n$，记 $[n]$ 为集合 ${x:0\le x\le n}$。考虑一个函数 $f:[n]\to\R$，我们会在 $[n]$ 的某个子集 $S$ 上定义部分的 $f$，从而推广之。 集合 $S$ 满足下列的规则： 1. $S$ 中的元素都是整数。 2. $[n]$ 的边界值 $0,n$ 都在 $S$ 之内。 函数 $f$ 满足下列的条件： 1. $f$ 在 $[n]$ 的所有元素的取值都为整数。 2. 对于所有 $x\in([n]\backslash S)$，函数在区间 $[x-1,x+1]$ 是单调的。也即，$f(x-1)\le f(x)\le f(x+1)$ 和 $f(x-1)\ge f(x)\ge f(x+1)$ 中至少有一个是成立的。 3. 对于所有 $x\notin[n]$，$f(x)$ 的值通过 $f(\lfloor x\rfloor)$ 和 $f(\lceil x\rceil)$ 线性插值给出：$f(x)=(x-\lfloor x\rfloor)f(\lfloor x\rfloor)+(\lceil x\rceil-x)f(\lceil x\rceil)$。 我们仍然可以规定 $f$ 在 $[n]\backslash S$ 的取值（当然 $S$ 可以等于 $[n]$）。我们现在需要想法使 $\int_0^nf(x)\mathrm dx=y$。你的任务是判断这是否可能。

多组数据。每组数据第一行包含三个整数 $n,m,y$ 代表区间大小，子集 $S$ 的大小和 $y$ 的值。而后的 $m$ 行描述 $f$ 在 $S$ 上的值，每行包含两个整数 $x$ 和 $v$，代表 $f(x)=v$。$x$ 不一定单调递增。 $1\le n\le 10^6,0\le x\le n,x\in\Z,x\in S,0\le v\le 10^6,f\in \Z,0\le y\le 10^9,y\in \Z$

对于每组数据，判断是否存在对于 $x\in [n]\backslash S$ 的取值满足 $\int_0^nf(x)\mathrm dx=y$。如果不存在，输出一个 `N` 后换行；如果存在，先输出一个 `S `，而后输出所有 $x\in [n]\backslash S$ 上的 $f$ 的取值，升序输出。假若有多组答案，那么输出字典序最小的那个。