Segment Tree#5952
Sign in

Segment Tree

1.5 seconds
64 megabytes
Medium

You are given an array of elements a_0, a_1, \ldots, a_{255}, which is initially filled with zeros. You are required to support two types of operations on this array: range addition and range sum query.

The range addition operation is described as \textbf{Add}(L, R, value), which means you need to add to each element a_L, a_{L+1}, \ldots, a_R of the array. The range sum operation is described as \textbf{Get}(L, R) and should return \sum_{i=L}^{R} a_i.

For efficiency of input and output, the first operation is always \textbf{Add}(L, R, 1) using given values and . Each subsequent operation is of the form

\textbf{Add}(\min(L_{\text{new}}, R_{\text{new}}), \max(L_{\text{new}}, R_{\text{new}}), 1),

where L_{\text{new}} and R_{\text{new}} are computed as follows:

L_{\text{new}} = \textbf{Get}(\min(L, R), \max(L, R)) \bmod p,
R_{\text{new}} = 255 - \textbf{Get}(\min(L, R), \max(L, R)) \bmod p,

where indicates taking the remainder after division by .

After each such operation, update L := L_{\text{new}} and R := R_{\text{new}}.

Input

The only line of the input contains four integers , , , (1 \leq q \leq 5 \cdot 10^6,\ 0 \leq L \leq R \leq 255,\ 1 \leq p \leq 125), where is the number of operations, and are initial values, and is the modulus.

Output

Print the value of \textbf{Get}(0, 255) after all operations have been performed.

Examples

Example 1

Loading
Loading