**Task statistics**

Number of users: 19

Number of users with 10 points: 6

Average result: 5.6316

# Trails [A]

### Memory limit: 32 MB

Byteasar is still playing with his plotter and printing bytecurves, see
the task Plotter.
(Recall that a bytecurve of order consists of segments of length each,
the first of them connects the points and , and between any two
consecutive segments the pen changes its direction by :
the -th () turn is to the right if and only if
for some integer and odd .)
Byteasar has noticed that he can draw beautiful trails with his plotter.
For this, before starting the plotter Byteasar sticks a piece of paper tape on the paper,
so that it covers a rectangle with opposite vertices at coordinates and .
After the plotter has completed printing, Byteasar can detach the tape and
admire the beautiful trails on it.
A *trail* is any connected curve of positive length plotted on the tape.

While waiting for the plotter to complete printing, Byteasar ponders how many trails will be plotted on the tape. Could you help him answer this question?

## Input

The first line of the standard input contains two integers, and (), where indicates the order of the bytecurve and indicates the number of queries. The following lines contain three integers , and (, ) each that provide the coefficients the glued tape.

## Output

Your program should output lines to the standard output - the answers to respective queries. Each line should hold a single integer - the number of trails drawn on the tape.

## Example

For the input data:

4 3 -4 1 0 -4 -1 -2 -2 0 -4

the correct result is:

2 1 0

*Task author: Tomasz Idziaszek.*