You are given an array, , consisting of integers.

A segment, , is beautiful if and only if the bitwise AND of all numbers in with indices in the inclusive range of is not greater than . In other words, segment is beautiful if .

You must answer queries. Each query, , consists of integers: , , and . The answer for each is the number of beautiful segments such that and .

Input Format

The first line contains two space-separated integers, (the number of integers in ) and (the number of queries).

The second line contains space-separated integers, where the integer denotes the element of array .

Each line of the subsequent lines contains space-separated integers, , , and , respectively, describing query .

Constraints

  • holds for test cases worth at least of the problem's score.
  • holds for test cases worth at least of the problem's score.

Output Format

Print lines, where the line contains the number of beautiful segments for query .

Sample Input

5 3
1 2 7 3 4
1 5 3
2 4 6
3 5 2

Sample Output

13
5
2

Explanation

The beautiful segments for all queries are listed below.

Query 0: The beautiful segments are .

Query 1: The beautiful segments are .

Query 2: The beautiful segments are .

Line: 1 Col: 1
  1. Challenge Walkthrough
    Let's walk through this sample challenge and explore the features of the code editor.1 of 6
  2. Review the problem statement
    Each challenge has a problem statement that includes sample inputs and outputs. Some challenges include additional information to help you out.2 of 6
  3. Choose a language
    Select the language you wish to use to solve this challenge.3 of 6
  4. Enter your code
    Code your solution in our custom editor or code in your own environment and upload your solution as a file.4 of 6
  5. Test your code
    You can compile your code and test it for errors and accuracy before submitting.5 of 6
  6. Submit to see results
    When you're ready, submit your solution! Remember, you can go back and refine your code anytime.6 of 6
  1. Check your score