Histogram Sequence 4

시간 제한1초메모리 제한1024 MB

요약

N, A, L, R이 주어질 때 높이가 [L,R] 범위에 있고 내부 최대 직사각형 넓이가 정확히 A인 히스토그램을 만든다.

난이도: 보통10점 중 7점
유형: 그리디, 배열, 구현, 수학
정답자: 아직 제출이 없습니다

문제

You had a histogram made of $N$ axis-parallel rectangles sharing a common baseline: the $i$ -th rectangle from the left had a width $1$ and an integer height $H\_i$ .

Sadly, you lost your histogram! Moreover, you even forgot what your histogram looked like — the heights of the rectangles of the histogram. What you remember is the maximum area $A$ of the axis-parallel rectangle inside the histogram, and the fact that $L\le H\_i\le R$ for every $H\_i$ .

Your goal is to recover the histogram by finding any histogram satisfying all the requirements that you remember. As your memory might not be perfect, there may be no histogram satisfying the requirements.

입력

The first and only line contains four space-separated integers, $N$ , $A$ , $L$ , $R$ .

출력

If there is no histogram satisfying the requirements, output NO.

Otherwise, output YES in the first line. In the second line, output $N$ integers in a single line, where the $i$ -th value is the height $H\_i$ of the $i$ -th rectangle. If there are multiple answers, print any.

제한

$1\le N\le 500\\, 000$
$0\le A\le 10^{18}$
$0\le L\le R\le 10^{18}$

힌트

A histogram with heights $3,7,6,8,5,5$ is shown below. The maximum area rectangle inside the histogram has an area of $25$ .

예제3

예제 1
입력
```
6 25 2 10
```
예상 출력
```
YES
3 7 6 8 5 5
```
예제 2
입력
```
1 0 0 1000000000000000000
```
예상 출력
```
YES
0
```
예제 3
입력
```
1 8213912883 0 28318
```
예상 출력
```
NO
```