题目描述

同余的定义式为 $a≡b(\text {mod } m)$ ，意思是 $a$ 对 $m$ 取余的结果和 $b$ 对 $m$ 取余的结果相同，也即 $a\%m=b\%m$。

现在，你要求出有多少个 $x_i$($l≤x_i ≤r$ 且 $x_i$ 为整数 ) 满足：$x_i≡y(\text {mod } k)$ 。

输入格式

一行 $4$ 个整数，分别代表 $l、r、y、k$ 。

输出格式

一行一个整数，代表符合题目要求的 $x_i$ 的个数。

1 100 2 3

33

97700130 98700130 2 275

3636

数据规模与约定

对于 $30\%$ 的数据：$k=1$。

对于 $80\%$ 的数据：$r−l≤10^6$。

对于 $100\%$ 的数据：$1≤l≤r\le2^{63}-1,0≤y<k≤10^{12}$。