Problems
Отрезок и квадраты
Отрезок и квадраты
Задана прямоугольная система координат и квадратная сетка, состоящая из \textbf{N^2} квадратов со сторонами, параллельными осям координат. Квадрат \textbf{S_ij} (\textbf{i},\textbf{j}=\{\textbf{1}...\textbf{N}\}) имеет вершины с координатами (\textbf{K}·\textbf{i}-\textbf{K}, \textbf{K}·\textbf{j}-\textbf{K}), (\textbf{K}·\textbf{i}-\textbf{K}, \textbf{K}·\textbf{j}), (\textbf{K}·\textbf{i}, \textbf{K}·\textbf{j}-\textbf{K}), (\textbf{K}·\textbf{i}, \textbf{K}·\textbf{j}).
Проводится отрезок, соединяющий точку на левой границе сетки (\textbf{0},\textbf{W}) с точкой на правой границе (\textbf{K}·\textbf{N},\textbf{E}). Требуется определить количество квадратов сетки, которые имеют хотя бы одну общую точку с этим отрезком.
\InputFile
Входной файл содержит целые числа \textbf{N}, \textbf{W}, \textbf{E}, \textbf{K}, разделенные пробелами (\textbf{1} ≤ \textbf{N}, \textbf{K} ≤ \textbf{10^2000}, \textbf{0} ≤ \textbf{W}, \textbf{E} ≤ \textbf{K}·\textbf{N}).
\OutputFile
Выведите количество квадратов, пересекающихся с отрезком хотя бы в одной точке.
Input example #1
3 50 150 100
Output example #1
4