The following problem was asked in a hiring challenge : -

Given an array $$$A$$$ of $$$N$$$ elements. All elements are distinct. The array is $$$1$$$-indexed.

You have $$$Q$$$ queries to answer. In the $$$i_{th}$$$ query, you are given three values $$$(X[i], L[i], R[i])$$$ and you should find the index $$$K$$$ such that

• $$$L[i]<=K<=R[i]$$$ and

• $$$A[K] \oplus X[i]$$$ is minimum where $$$\oplus$$$ is the bitwise XOR.

It is guaranteed that the value of $$$K$$$ will be unique for each query.

You task is to print the sum of the indices $$$K$$$ among all queries. Since the answer might be large, return it modulo $$$10^9+7$$$.

Constraints

$$$0<=N<10^5\newline0<=A[i]<=10^5\newline1<=Q<=10^5\newline0<=X[i]<=10^6\newline1<=L[i]<=R[i]<=N$$$