Subinterval Value Sum Query

Given three sequences \(a_1, a_2, \dots, a_n\), \(b_1, b_2, \dots, b_n\) and \(c_1, c_2, \dots, c_n\), define the value of an interval \([l, r]\) as:

\[\Big(\bigwedge_{i=l}^{r} a_i\Big) \times \Big(\bigvee_{i=l}^{r} b_i\Big) \times \Big(\gcd_{i=l}^{r} c_i\Big)\]

Here, \(\bigwedge\) denotes the bitwise AND, \(\bigvee\) denotes the bitwise OR, and \(\gcd\) is the greatest common divisor of the corresponding segment.

You are also given \(m\) queries. Each query provides an interval \([l, r]\). For each query, you must compute the sum of the values of all subintervals \([l', r']\) with \(l \le l' \le r' \le r\).

Note: All formulas must be expressed in LaTeX format.

inputFormat

The first line contains two integers \(n\) and \(m\) \( (1 \leq n, m \leq 300)\), representing the size 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 following \(m\) lines contains two integers \(l\) and \(r\) (1-indexed), representing a query interval.

outputFormat

For each query, output a single line containing the sum of the values of all subintervals within the given range.

sample

3 2
1 2 3
1 2 3
1 2 3
1 2
1 3

9
42