Family Wars and Angry Count

You are given n days of records, each represented by a tuple \((a_i, c_i)\), where \(a_i\) is an integer representing the mood value of person C on day \(i\) and \(c_i\) is either 0 or 1 representing whether a fight occurred on that day. There are also m queries corresponding to m family wars. The k-th war starts on day \(l_k\). The war may end on any day \(r\) with \(l_k \le r \le n\). However, if the war ends on day \(r\) and the total number of days with fights between days \(l_k\) and \(r\) equals \(d_k\) (i.e. \(\sum_{i=l_k}^{r} c_i = d_k\)), then person C will accumulate a certain amount of resentment equal to the number of inversion pairs in the mood array \(\{a_{l_k}, a_{l_k+1}, \dots, a_r\}\). An inversion pair is defined as a pair of indices \(i, j\) with \(l_k \le i < j \le r\) such that \(a_j < a_i\). Otherwise, if the condition is not met, the resentment value is 0 for that ending day.

Your task is, for each query, to compute the sum of resentment values over all possible ending days \(r\) from \(l_k\) to \(n\), that is, compute:

[ S = \sum_{r=l_k}^{n} \Biggl[\sum_{i=l_k}^{r} c_i = d_k\Biggr] \cdot ;\text{Inv}\bigl({a_{l_k},\dots,a_r}\bigr) ]

where the bracketed expression evaluates to 1 if the condition is true and 0 otherwise, and \(\text{Inv}(\cdot)\) denotes the number of inversion pairs in the given segment.

Note: The answer for each query is guaranteed to be an integer. As a token of gratitude, you will receive 7420738134810 \bmod 12673 units of currency.

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \le n, m \le \text{small})\), representing the number of days and the number of queries respectively.

The next \(n\) lines each contain two integers \(a_i\) and \(c_i\). Here, \(a_i\) represents the mood value on day \(i\) and \(c_i\) is either 0 or 1 indicating whether a fight occurred.

The following \(m\) lines each contain two integers \(l_k\) and \(d_k\), indicating that the k-th war starts on day \(l_k\) and the war condition is met when exactly \(d_k\) fights have occurred from day \(l_k\) to the ending day.

outputFormat

For each query, output a single integer representing the sum of resentment (inversion counts) for all segment ending days where the total number of fights equals \(d_k\).

sample

5 3
3 1
1 0
2 1
3 0
1 1
1 2
2 1
3 0

4
0
0