Similar Number

Time Limit: 5000 Ms

Memory Limit: 65535 Kb


We can call two numbers “similar” if their lengths are equal and we can make a number ‘’similar’’ through swapping some digits of itself. For instance, 123 is similar to 321 but 12 is not similar to 120.

A sequence can be called “similar sequence” if this sequence has only one pair of ‘’similar’’ numbers.

Now, Zero writes a series of integers and he needs you to answer his queries online. For each query, he gives you two integers l and r, which represent the two endpoints of a segment. He wants to know how many successive subsequences are “similar sequences”.


There are multiple test cases.

In the first line of every test case there are two integers n (0<n<=100000) and m (0<=m<=100000), meaning that the sequence contains n integers and m queries.

   The next line contains n integers a[i] (1<=i<=n, a[i] <= 109), which represent the intergers in the sequence.

After that, there are m lines, each line containing two integers l and r.

Zero thinks that it is too simple for him to solve this problem, so he sets a variable k. In the beginning of each test case, k = 0. For each query, he sets l = l + k and r = r - k, Zero guarantees that 0<l<=r<=n, then make k the answer of this query.

The input ends with EOF.


For each query, output an integer, and there is no blank line after each test.

Sample Input

5 5
2 2 2 2 2 
1 4
1 8
1 4
1 6
-1 5

Sample Output





2013 ACM-ICPC China Nanjing Invitational Prog