Subinterval Value Sum Query

You are given three integer sequences: \(a_1, a_2, \dots, a_n\), \(b_1, b_2, \dots, b_n\) and \(c_1, c_2, \dots, c_n\). The value of a subinterval \([l,r]\) is defined as:

\[ V(l, r) = \Bigl(\bigwedge_{i=l}^{r} a_i\Bigr) \times \Bigl(\bigvee_{i=l}^{r} b_i\Bigr) \times \gcd(c_l, c_{l+1}, \dots, c_r), \]

where \(\bigwedge\) denotes the bitwise AND, \(\bigvee\) denotes the bitwise OR, and \(\gcd\) is the greatest common divisor.

You are also given \(m\) queries. Each query supplies an interval \([l, r]\) and asks you to compute the sum of \(V(l',r')\) over all subintervals \([l', r']\) satisfying \(l \le l' \le r' \le r\).

inputFormat

The first line contains two integers \(n\) and \(m\) \(\,(1 \le n \le 3000,\, 1 \le m \le 10^5)\), representing the length of the sequences and the number of queries.

The second line contains \(n\) integers: \(a_1, a_2, \dots, a_n\).

The third line contains \(n\) integers: \(b_1, b_2, \dots, b_n\).

The fourth line contains \(n\) integers: \(c_1, c_2, \dots, c_n\).

Each of the next \(m\) lines contains two integers \(l\) and \(r\) \((1 \le l \le r \le n)\) describing a query.

outputFormat

For each query output a single integer — the sum of values of all subintervals \([l', r']\) within \([l, r]\).

sample

3 2
1 3 2
2 3 1
2 4 6
1 2
2 3

46
60