Irregular Month Summation

You are given an integer N representing the number of months, and two integers A and B representing the number of days in the first and second month respectively. For i ≥ 3, the number of days in the i^th month is defined recursively by

$$M_i = M_{i-1} + M_{i-2}.$$

All months are 1-indexed.

You are also given Q queries. Each query consists of two integers L and R where you need to compute the sum of days from month L to month R (inclusive). Your task is to answer all the queries.

inputFormat

The input is read from stdin and has the following format:

• The first line contains three integers N, A, and B separated by spaces.
• The second line contains an integer Q, the number of queries.
• Each of the next Q lines contains two integers L and R separated by a space, representing a query.

outputFormat

For each query, output a single line to stdout containing the total number of days from month L to month R.

## sample

5 1 1
3
1 3
2 4
1 5

4
6
12

</p>