Отрезок и квадраты#1133
В прямоугольной системе координат задана квадратная сетка, состоящая из \textbf{N}^2 квадратов со сторонами, параллельными координатным осям. Каждый квадрат \textbf{S}_{ij} (\textbf{i},\textbf{j} = 1,\ldots,\textbf{N}) имеет вершины в точках (\textbf{K}\cdot\textbf{i}-\textbf{K},\ \textbf{K}\cdot\textbf{j}-\textbf{K}), (\textbf{K}\cdot\textbf{i}-\textbf{K},\ \textbf{K}\cdot\textbf{j}), (\textbf{K}\cdot\textbf{i},\ \textbf{K}\cdot\textbf{j}-\textbf{K}) и (\textbf{K}\cdot\textbf{i},\ \textbf{K}\cdot\textbf{j}).
Проведён отрезок из точки на левой границе сетки в точку (\textbf{K}\cdot\textbf{N}, \textbf{E}) на правой границе. Определите, сколько квадратов сетки имеют с этим отрезком хотя бы одну общую точку.
Во входных данных содержатся целые числа , , , , разделённые пробелами, где 1 \leq \textbf{N}, \textbf{K} \leq 10^{2000} и 0 \leq \textbf{W}, \textbf{E} \leq \textbf{K}\cdot\textbf{N}.
Выведите количество квадратов, которые пересекаются с отрезком хотя бы в одной точке.
Example 1