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?
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.
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.