Distance Sum on a Generalized Segment Tree

A generalized segment tree is built on the interval \([1,n]\) in the following way: For an interval \([l,r]\), if \(l=r\) a leaf node is created. Otherwise, we choose an integer \(m\) satisfying \(l \le m < r\) (in our problem the standard choice is used, i.e. \(m=\lfloor (l+r)/2 \rfloor\)) and recursively build the left child on \([l, m]\) and the right child on \([m+1, r]\). It can be proved that such a full binary tree always has exactly \(2n-1\) nodes. The nodes are labeled in preorder (the root is labeled 1, then its left subtree, then its right subtree).

For any interval \([l,r]\) with \(1 \le l \le r \le n\), its cover \(S_{[l,r]}\) is defined as the minimal set of nodes (with pairwise disjoint intervals) in the segment tree whose union equals exactly \([l,r]\). This is the same operation as the lazy propagation interval cover in segment trees.

For two nodes \(u\) and \(v\) in the tree, the distance \(d(u,v)\) is defined as the number of edges on the unique path between them.

You are given the integer \(n\) and the corresponding generalized segment tree built on \([1,n]\) (with the standard choice of splitting \((m=\lfloor (l+r)/2 \rfloor)\) so that the tree has \(2n-1\) nodes labeled in preorder). Then, you are given \(m\) queries. Each query consists of three integers \(u, l, r\) (with \(1 \le u \le 2n-1\) and \(1 \le l \le r \le n\)). For each query, compute:

[ \sum_{v \in S_{[l,r]}} d(u, v) ]

That is, for the query you must find the set of nodes \(S_{[l,r]}\) covering the interval \([l,r]\) and then sum the distances from the given node \(u\) to each node in \(S_{[l,r]}\).

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \le n \le 10^5,\; 1 \le m \le 10^5)\) representing the number of leaves and the number of queries, respectively. The next \(m\) lines each contain three integers \(u, l, r\) representing a query. It is guaranteed that \(1 \le u \le 2n-1\) and \(1 \le l \le r \le n\).

outputFormat

For each query, output one integer representing the value of \(\sum_{v \in S_{[l,r]}} d(u, v)\).

sample

4 1
1 2 3

4