Trails

Byteasar is still playing with his plotter and printing bytecurves. (Recall that a bytecurve of order $n$ consists of $2^n$ segments, each of length $\sqrt{2}$. The first segment connects the points $(0, 0)$ and $(1, 1)$, and between any two consecutive segments the pen turns by $90^\circ$: the $i$-th turn (for $1 \le i < 2^n$) is to the right if and only if $i = 2^k(1 + 2l)$ for some non-negative integer $k$ and odd $l$.)

Byteasar has noticed that he can draw beautiful trails with his plotter. Before starting the plotter, he sticks a piece of paper tape on the paper so that it covers the rectangle whose opposite corners are $(x_1, y)$ and $(x_2, y + 1)$. After the plotter finishes, he peels off the tape and admires the trails left on it. A trail is any connected curve of positive length drawn on the tape.

While waiting for the plotter to finish, Byteasar wonders how many trails will end up on the tape. Help him answer this question.

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 2000$): the order of the bytecurve and the number of queries. Each of the next $m$ lines contains three integers $x_1$, $x_2$ and $y$ ($-10^9 \le x_1, x_2, y \le 10^9$, $x_1 < x_2$), describing one glued tape.

Print $m$ lines, one per query. Each line contains a single integer: the number of trails drawn on the corresponding tape.