Trails

Time limit1sMemory limit128 MB

Summary

For each axis-aligned unit-height tape, count the connected pieces of the bytecurve of order n that lie inside the rectangle.

Level: Hard8 of 10
Topics: Divide and conquer, Recursion, Math, Geometry
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Hint

Examples1

Example 1
Input
```
4 3
-4 1 0
-4 -1 -2
-2 0 -4
```
Expected output
```
2
1
0
```