no tags

As you might already know, Ada the Ladybug is a farmer. Beside fruit and vegetable, Ada grows flowers. At the moment she plans to go to a competition with her dahlias. The evaluation of bunch of dahlias is simple: Jury sorts all dahlias by the diameters of blooms and takes the maximal difference between any two adjacent dahlias. This will be the score.

The problems is that Ada's flowers are not in sorted order and she wants to know what score she would get if the passes all flowers to jury. To make job easier for you (or at least Ada hopes so), she created a formula which will give you the diameters of blooms (0 to N-1) in actual order: Ai+1=(a*Ai+b)%c.

### Input

The first and the only line contains five integers (N,a,b,c,A0): 2 ≤ N ≤ 4*107, the number of flowers, and 0 ≤ a, b ≤ 1018, 1 ≤ c ≤ 1018, 0 ≤ A0 < c

### Output

Output the maximum difference of elements (if they would be sorted).

### Example Input

`10 2 3 31 7`

```8
```

### Example Input

```4 4 6 11 6
```

```2
```

### Example Input

```50 3 11 41 0
```

```8
```

### Example Input

```1000 666 777 1234567 11
```

```10817
```

### Example Input

```10000000 612 521 124578541254695 666666
```

### Example Output

```230017823
```