Segmented Sieve

Problem Description

Given two numbers $l, r$, find all primes $p$ in the range $l \sim r$.

To keep the output from being too large and to prevent precomputing answers from a table, you are also given $a, b$; output the XOR sum of $(a \cdot p + b) \bmod 2^{32}$ over all such primes.

Input Format

The first line contains four integers $l, r, a, b$.

Output Format

Output one integer: the answer.

Sample Input

1 100 1 0

Sample Output

64

Constraints

For all data, $1 \leq l \leq r \leq 10^{14}$, $0 \leq a, b < 2^{32}$, $r - l \leq 10^7$.