흔적

바이트아사르는 여전히 플로터로 바이트커브를 그리며 놀고 있다. (바이트커브의 차수 $n$은 각각 길이가 $\sqrt{2}$인 $2^n$개의 선분으로 이루어진다. 첫 번째 선분은 두 점 $(0, 0)$과 $(1, 1)$을 잇고, 이웃한 두 선분 사이에서 펜은 방향을 $90^\circ$ 바꾼다. $i$번째 꺾임($1 \le i < 2^n$)이 오른쪽으로 꺾이는 것은, 어떤 음이 아닌 정수 $k$와 홀수 $l$에 대해 $i = 2^k(1 + 2l)$로 나타낼 수 있을 때, 그리고 오직 그때뿐이다.)

바이트아사르는 이 플로터로 아름다운 흔적을 그릴 수 있다는 것을 알아차렸다. 플로터를 켜기 전에 그는 종이 위에 종이테이프를 붙이는데, 이 테이프는 마주 보는 두 꼭짓점이 $(x_1, y)$와 $(x_2, y + 1)$인 직사각형을 덮는다. 플로터가 다 그린 뒤 그는 테이프를 떼어 그 위에 남은 흔적을 감상한다. 흔적이란 테이프 위에 그려진, 길이가 양수인 연결된 곡선을 말한다.

플로터가 끝나기를 기다리며, 바이트아사르는 테이프 위에 흔적이 몇 개나 남을지 궁금해한다. 이 질문에 답하여 그를 도와주자.

첫째 줄에 두 정수 $n$과 $m$ ($1 \le n, m \le 2000$)이 주어진다. $n$은 바이트커브의 차수, $m$은 질의의 개수이다. 이어지는 $m$개의 줄에는 각각 세 정수 $x_1$, $x_2$, $y$ ($-10^9 \le x_1, x_2, y \le 10^9$, $x_1 < x_2$)가 주어지며, 붙인 테이프 하나를 나타낸다.

$m$개의 줄을 출력한다. 각 줄에는 해당 질의에 대한 답, 즉 그 테이프 위에 그려진 흔적의 개수를 나타내는 정수 하나를 출력한다.