Sonya and Bitwise OR

Sonya has an array a_1, a_2, …, a_n consisting of n integers and also one non-negative integer x. She has to perform m queries of two types:

• 1 i y: replace i-th element by value y, i.e. to perform an operation a_{i} := y;
• 2 l r: find the number of pairs (L, R) that l≤ L≤ R≤ r and bitwise OR of all integers in the range [L, R] is at least x (note that x is a constant for all queries).

Can you help Sonya perform all her queries?

Bitwise OR is a binary operation on a pair of non-negative integers. To calculate the bitwise OR of two numbers, you need to write both numbers in binary notation. The result is a number, in binary, which contains a one in each digit if there is a one in the binary notation of at least one of the two numbers. For example, 10 OR 19 = 1010_2 OR 10011_2 = 11011_2 = 27.

Input

The first line contains three integers n, m, and x (1≤ n, m≤ 10^5, 0≤ x<2^{20}) — the number of numbers, the number of queries, and the constant for all queries.

The second line contains n integers a_1, a_2, …, a_n (0≤ a_i<2^{20}) — numbers of the array.

The following m lines each describe an query. A line has one of the following formats:

• 1 i y (1≤ i≤ n, 0≤ y<2^{20}), meaning that you have to replace a_{i} by y;
• 2 l r (1≤ l≤ r≤ n), meaning that you have to find the number of subarrays on the segment from l to r that the bitwise OR of all numbers there is at least x.

Output

For each query of type 2, print the number of subarrays such that the bitwise OR of all the numbers in the range is at least x.

Examples

Input

4 8 7 0 3 6 1 2 1 4 2 3 4 1 1 7 2 1 4 2 1 3 2 1 1 1 3 0 2 1 4

Output

5 1 7 4 1 4

Input

5 5 7 6 0 3 15 2 2 1 5 1 4 4 2 1 5 2 3 5 2 1 4

Output

9 7 2 4

Note

In the first example, there are an array [0, 3, 6, 1] and queries:

1. on the segment [1…4], you can choose pairs (1, 3), (1, 4), (2, 3), (2, 4), and (3, 4);
2. on the segment [3…4], you can choose pair (3, 4);
3. the first number is being replacing by 7, after this operation, the array will consist of [7, 3, 6, 1];
4. on the segment [1…4], you can choose pairs (1, 1), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), and (3, 4);
5. on the segment [1…3], you can choose pairs (1, 1), (1, 2), (1, 3), and (2, 3);
6. on the segment [1…1], you can choose pair (1, 1);
7. the third number is being replacing by 0, after this operation, the array will consist of [7, 3, 0, 1];
8. on the segment [1…4], you can choose pairs (1, 1), (1, 2), (1, 3), and (1, 4).

In the second example, there are an array [6, 0, 3, 15, 2] are queries:

1. on the segment [1…5], you can choose pairs (1, 3), (1, 4), (1, 5), (2, 4), (2, 5), (3, 4), (3, 5), (4, 4), and (4, 5);
2. the fourth number is being replacing by 4, after this operation, the array will consist of [6, 0, 3, 4, 2];
3. on the segment [1…5], you can choose pairs (1, 3), (1, 4), (1, 5), (2, 4), (2, 5), (3, 4), and (3, 5);
4. on the segment [3…5], you can choose pairs (3, 4) and (3, 5);
5. on the segment [1…4], you can choose pairs (1, 3), (1, 4), (2, 4), and (3, 4).

inputFormat

Input

The first line contains three integers n, m, and x (1≤ n, m≤ 10^5, 0≤ x<2^{20}) — the number of numbers, the number of queries, and the constant for all queries.

The second line contains n integers a_1, a_2, …, a_n (0≤ a_i<2^{20}) — numbers of the array.

The following m lines each describe an query. A line has one of the following formats:

• 1 i y (1≤ i≤ n, 0≤ y<2^{20}), meaning that you have to replace a_{i} by y;
• 2 l r (1≤ l≤ r≤ n), meaning that you have to find the number of subarrays on the segment from l to r that the bitwise OR of all numbers there is at least x.

outputFormat

Output

For each query of type 2, print the number of subarrays such that the bitwise OR of all the numbers in the range is at least x.

Examples

Input

4 8 7 0 3 6 1 2 1 4 2 3 4 1 1 7 2 1 4 2 1 3 2 1 1 1 3 0 2 1 4

Output

5 1 7 4 1 4

Input

5 5 7 6 0 3 15 2 2 1 5 1 4 4 2 1 5 2 3 5 2 1 4

Output

9 7 2 4

Note

In the first example, there are an array [0, 3, 6, 1] and queries:

1. on the segment [1…4], you can choose pairs (1, 3), (1, 4), (2, 3), (2, 4), and (3, 4);
2. on the segment [3…4], you can choose pair (3, 4);
3. the first number is being replacing by 7, after this operation, the array will consist of [7, 3, 6, 1];
4. on the segment [1…4], you can choose pairs (1, 1), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), and (3, 4);
5. on the segment [1…3], you can choose pairs (1, 1), (1, 2), (1, 3), and (2, 3);
6. on the segment [1…1], you can choose pair (1, 1);
7. the third number is being replacing by 0, after this operation, the array will consist of [7, 3, 0, 1];
8. on the segment [1…4], you can choose pairs (1, 1), (1, 2), (1, 3), and (1, 4).

In the second example, there are an array [6, 0, 3, 15, 2] are queries:

1. on the segment [1…5], you can choose pairs (1, 3), (1, 4), (1, 5), (2, 4), (2, 5), (3, 4), (3, 5), (4, 4), and (4, 5);
2. the fourth number is being replacing by 4, after this operation, the array will consist of [6, 0, 3, 4, 2];
3. on the segment [1…5], you can choose pairs (1, 3), (1, 4), (1, 5), (2, 4), (2, 5), (3, 4), and (3, 5);
4. on the segment [3…5], you can choose pairs (3, 4) and (3, 5);
5. on the segment [1…4], you can choose pairs (1, 3), (1, 4), (2, 4), and (3, 4).

样例

5 5 7
6 0 3 15 2
2 1 5
1 4 4
2 1 5
2 3 5
2 1 4

9
7
2
4

</p>