Weird Decimal XOR

For example, Yellow is two steps from Red, so composing Orange with Yellow gives Blue, which is two steps after Orange.

For two one-digit decimal numbers $x,y$, define their weird decimal XOR $x\diamond y$ as follows.

• The color of the result is the composition of the colors of $x$ and $y$.
• The state of the result is the bitwise XOR of the states of $x$ and $y$.

For example, $3$ is Orange with state $1$, while $6$ is Blue with state $0$. Composing Orange and Blue gives Purple, and $1\mathbin{\mathrm{XOR}}0=1$, so $3\diamond6=9$.

Extend the operation to nonnegative integers with multiple decimal digits. A missing higher digit is treated as $0$. The weird decimal XOR of two integers is obtained by independently applying the one-digit operation at every decimal position.

For example, the tens digit satisfies $3\diamond6=9$ and the ones digit satisfies $7\diamond8=5$, so $37\diamond68=95$.

When the operation is applied more than once, evaluate it from left to right. Thus,

You are given a sequence $A_1,A_2,\cdots,A_N$. Each query consists of two integers $L,R$. For each query, count the ordered pairs of integers $(l,r)$ satisfying both conditions below.

• $L\le l\le r\le R$.
• $A_l\diamond A_{l+1}\diamond\cdots\diamond A_r=0$.

Each case is given in the following format:

$N\ Q$ $A_1\ A_2\ \cdots\ A_N$ $L_1\ R_1$ $L_2\ R_2$ $\vdots$ $L_Q\ R_Q$

The $q$-th query asks about the interval $[L_q,R_q]$.

Do not print an additional separator between test cases.