8280번 - Trails 다국어

Byteasar is still playing with his plotter and printing bytecurves, see the task Plotter. (Recall that a bytecurve of order n consists of 2ⁿ segments of length √2 each, the first of them connects the points (0, 0) and (1, 1), and between any two consecutive segments the pen changes its direction by 90°: the i-th (1 ≤ i < 2ⁿ) turn is to the right if and only if i = 2^k(1+2l) for some integer k and odd l.) 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 (x₁, y) and (x₂, y+1). 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, n and m (1 ≤ n, m ≤ 2000), where n indicates the order of the bytecurve and m indicates the number of queries. The following m lines contain three integers x₁, x₂ and y (-10⁹ ≤ x₁, x₂, y ≤ 10⁹, x₁ < x₂) each that provide the coefficients the glued tape.

Your program should output m 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.