Time Limit: 2.0 s

Memory Limit: 256.0 MB

Description

In the magical world of Hogwarts, where spells and potions are part of everyday life, you are a wizard prodigy renowned for your exceptional skills in Arithmancy—the mystical study of numbers. One day, Professor Flitwick presents you with a mysterious task involving a magical array of enchanted numbers. This array is dynamic: its elements can change at any moment. To unlock the secret of a powerful spell, you must perform two types of magical operations on the array:

• Operation Type 1 (Format: 1 pos x):
  Given a position in the array, perform a bitwise XOR operation on the element with value x.

• Operation Type 2 (Format: 2 l r):
  Calculate the sum of the XORs of all possible subsequences within a specified segment of the array.

Professor Flitwick smiles and says, "This task will test your mastery of both magic and logic. Can you rise to the challenge and unlock the secrets of the magical array?"

Input

The first line contains two integers N and Q (1 <= N, Q <= 100,000) the size of the array and the number of queries.
The second line contains N integers (0 <= A[i] <= 1,000,000)
The next Q lines contain queries in the following format:

• 1 pos x (1 <= pos <= N, 0 <= x <= 1,000,000)
• 2 l r (1 <= l <= r <= N)

Output

For each query of type 2 l r, print the result modulo 1000000007.

Sample

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

12
12
28