Range Product Queries Modulo

Given an array \(a\) of length \(n\), answer \(q\) queries. Each query provides two indices \(l\) and \(r\), and you are to compute
\[ \prod_{i=l}^r a_i \bmod p, \]
where \(p = 1,145,141\).

The input begins with two integers \(n\) and \(q\). The next line contains \(n\) integers representing the array \(a\). Each of the following \(q\) lines contains two integers \(l\) and \(r\).

inputFormat

Input Format:

• The first line contains two space-separated integers \(n\) and \(q\).
• The second line contains \(n\) space-separated integers, which are the elements of array \(a\).
• Each of the next \(q\) lines contains two space-separated integers \(l\) and \(r\) representing a query.

outputFormat

Output Format:

• For each query, output a single line containing the value of \(\prod_{i=l}^r a_i \bmod p\).

sample

5 3
1 2 3 4 5
1 3
2 4
1 5

6
24
120