적분

양의 정수 $n$에 대해 $[n]$은 실수 구간 $\{x : 0 \le x \le n\}$을 뜻한다. 함수 $f : [n] \to \mathbb{R}$은 일부만 정해져 있다. $[n]$의 부분집합 $S$에 속하는 점에서만 $f$의 값이 주어진다.

집합 $S$는 다음을 만족한다.

1. $S$의 모든 점은 정수다.
2. $[n]$의 양 끝점 $0$과 $n$은 둘 다 $S$에 속한다.

함수 $f$는 다음을 만족한다.

1. $[n]$의 정수점에서 $f$의 값은 정수다.
2. $S$의 이웃한 두 점 사이에서 $f$는 단조롭다. $S$에서 이웃한 두 점 $L < R$에 대해 $f(L) \le f(L+1) \le \cdots \le f(R)$ 또는 $f(L) \ge f(L+1) \ge \cdots \ge f(R)$이 성립한다.
3. $[n]$의 정수가 아닌 점 $x$에서 $f(x)$는 $f(\lfloor x \rfloor)$와 $f(\lceil x \rceil)$의 선형 보간으로 정해진다. 곧 $f(x) = (\lceil x \rceil - x) f(\lfloor x \rfloor) + (x - \lfloor x \rfloor) f(\lceil x \rceil)$이다.

$[n] \setminus S$의 정수점에서 $f$의 값은 마음대로 정할 수 있다. ($S$가 $[n]$의 정수점 전체를 포함할 수도 있다.) 주어진 $y$에 대해 $\int_0^n f(x)\,dx = y$, 곧 $0$과 $n$ 사이에서 $f$ 아래의 면적이 $y$가 되도록 값을 정할 수 있는지 판정하라.

입력은 여러 개의 테스트 케이스로 이루어지고 파일 끝에서 끝난다.

테스트 케이스의 첫 줄에는 세 정수 $N$, $M$, $Y$가 주어진다. 차례로 구간의 길이, 집합 $S$의 크기, $y$의 값이다. 이어지는 $M$개의 줄에는 $S$의 한 점에서 $f$의 값을 나타내는 두 정수 $X$와 $F$가 주어지고, $f(X) = F$를 뜻한다. $X$는 증가하는 순서로 주어지지 않는다.

제한

• $1 \le N \le 10^6$
• 모든 테스트 케이스의 $N$의 합은 $10^6$ 이하다
• $0 \le X \le N$이고, $M$개의 $X$는 서로 다른 정수이며 $0$과 $N$을 포함한다
• $0 \le F \le 10^6$, $F$는 정수
• $0 \le Y \le 10^9$, $Y$는 정수
• 위 조건을 지키면서 $[n] \setminus S$의 정수점에 값을 어떻게 정하더라도 $\int_0^n f(x)\,dx \le 10^9$이다

각 테스트 케이스마다 $x \in [n] \setminus S$인 정수점에 $f$의 값을 정해 $\int_0^n f(x)\,dx = y$, 곧 $0$과 $n$ 사이에서 $f$ 아래의 면적이 $y$가 되도록 만들 수 있는지 판정한다.

만들 수 없으면 문자 N만 있는 한 줄을 출력한다. 만들 수 있으면 문자 S를 출력하고 이어서 $x \in [n] \setminus S$인 정수점의 $f(x)$ 값을 $x$가 커지는 순서로 같은 줄에 출력한다. 맨 앞 문자와 각 값은 공백 하나로 구분한다. 답이 여러 개면 값의 수열이 사전순으로 가장 앞선 것을 출력한다.