#include <bits/stdc++.h>
using namespace std;
namespace IO {
const unsigned int Buffsize = 1 << 15, Output = 1 << 23;
static char Ch[Buffsize], *S = Ch, *T = Ch;
inline char getc() {
  return ((S == T) && (T = (S = Ch) + fread(Ch, 1, Buffsize, stdin), S == T)
              ? 0
              : *S++);
}
static char Out[Output], *nowps = Out;
inline void flush() {
  fwrite(Out, 1, nowps - Out, stdout);
  nowps = Out;
}
template <typename T>
inline void read(T& x) {
  x = 0;
  static char ch;
  T f = 1;
  for (ch = getc(); !isdigit(ch); ch = getc())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getc()) x = x * 10 + (ch ^ 48);
  x *= f;
}
template <typename T>
inline void write(T x, char ch = '\n') {
  if (!x) *nowps++ = '0';
  if (x < 0) *nowps++ = '-', x = -x;
  static unsigned int sta[111], tp;
  for (tp = 0; x; x /= 10) sta[++tp] = x % 10;
  for (; tp; *nowps++ = sta[tp--] ^ 48)
    ;
  *nowps++ = ch;
}
}  // namespace IO
using namespace IO;
inline void file() {}
const int MAXN = 1 << 18;
static int n, m, X, N, a[MAXN], lg2[MAXN];
void init() {
  read(n), read(m), read(X);
  for (register int i = (1); i <= (n); ++i) read(a[i]);
  for (N = 2; N < n; N <<= 1)
    ;
  for (register int i = (1); i <= (N); ++i) lg2[i] = lg2[i >> 1] + 1;
}
namespace neko {
static vector<pair<int, int> > lp[MAXN << 1], rp[MAXN << 1];
static int lb[MAXN << 1], rb[MAXN << 1];
static long long ans[MAXN << 1];
inline int getps(int l, int r) {
  static int ls, rs;
  ls = l + N - 1, rs = r + N - 1;
  return ls >> lg2[ls ^ rs];
}
inline long long calc(int l, int r) {
  static int h, ls, rs, llim, rlim;
  h = getps(l, r), ls = h << 1, rs = h << 1 | 1;
  static long long sm;
  sm = 0ll;
  rlim = lp[rs].size() - 1, llim = rp[ls].size() - 1;
  for (register int i = 0, j = rlim; i <= llim && j >= 0; --j) {
    if (lp[rs][j].second > r) continue;
    while (i <= llim &&
           (rp[ls][i].second < l || (rp[ls][i].first | lp[rs][j].first) < X))
      ++i;
    if (i > llim) break;
    sm += 1ll * (rp[ls][i].second - (l - 1)) *
          ((j == rlim ? r + 1 : min(lp[rs][j + 1].second, r + 1)) -
           lp[rs][j].second);
  }
  return sm;
}
inline void pushup(int h) {
  lp[h] = lp[h << 1];
  static int it;
  it = lp[h << 1].back().first;
  for (auto v : lp[h << 1 | 1])
    if ((v.first | it) > it)
      lp[h].emplace_back(v.first | it, v.second), it |= v.first;
  rp[h] = rp[h << 1 | 1];
  it = rp[h << 1 | 1].back().first;
  for (auto v : rp[h << 1])
    if ((v.first | it) > it)
      rp[h].emplace_back(v.first | it, v.second), it |= v.first;
  ans[h] = calc(lb[h], rb[h]) + ans[h << 1] + ans[h << 1 | 1];
}
void make_tree(int h, int l, int r) {
  lb[h] = l, rb[h] = r;
  if (l == r) {
    lp[h].emplace_back(a[l], l), rp[h].emplace_back(a[l], l),
        ans[h] = a[l] >= X;
    return;
  }
  int mid = (l + r) >> 1;
  make_tree(h << 1, l, mid), make_tree(h << 1 | 1, mid + 1, r);
  pushup(h);
}
inline void modify(int x, int y) {
  static int ps;
  ps = x + N - 1;
  a[x] = y, ans[ps] = (a[x] >= X);
  lp[ps].clear(), rp[ps].clear();
  lp[ps].emplace_back(a[x], x), rp[ps].emplace_back(a[x], x);
  for (ps >>= 1; ps; ps >>= 1) pushup(ps);
}
long long Q(int L, int R) {
  int h = getps(L, R);
  if (L == lb[h] && R == rb[h]) return ans[getps(L, R)];
  return Q(L, rb[h << 1]) + Q(lb[h << 1 | 1], R) + calc(L, R);
}
}  // namespace neko
using namespace neko;
inline void solve() {
  make_tree(1, 1, N);
  static int opt, x, y;
  for (register int i = (1); i <= (m); ++i) {
    read(opt), read(x), read(y);
    if (opt == 1)
      modify(x, y);
    else
      write(Q(x, y));
  }
  flush();
}
int main() {
  init();
  solve();
  return 0;
}

### Prompt

In cpp, your task is to solve the following problem:

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). 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
namespace IO {
const unsigned int Buffsize = 1 << 15, Output = 1 << 23;
static char Ch[Buffsize], *S = Ch, *T = Ch;
inline char getc() {
  return ((S == T) && (T = (S = Ch) + fread(Ch, 1, Buffsize, stdin), S == T)
              ? 0
              : *S++);
}
static char Out[Output], *nowps = Out;
inline void flush() {
  fwrite(Out, 1, nowps - Out, stdout);
  nowps = Out;
}
template <typename T>
inline void read(T& x) {
  x = 0;
  static char ch;
  T f = 1;
  for (ch = getc(); !isdigit(ch); ch = getc())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getc()) x = x * 10 + (ch ^ 48);
  x *= f;
}
template <typename T>
inline void write(T x, char ch = '\n') {
  if (!x) *nowps++ = '0';
  if (x < 0) *nowps++ = '-', x = -x;
  static unsigned int sta[111], tp;
  for (tp = 0; x; x /= 10) sta[++tp] = x % 10;
  for (; tp; *nowps++ = sta[tp--] ^ 48)
    ;
  *nowps++ = ch;
}
}  // namespace IO
using namespace IO;
inline void file() {}
const int MAXN = 1 << 18;
static int n, m, X, N, a[MAXN], lg2[MAXN];
void init() {
  read(n), read(m), read(X);
  for (register int i = (1); i <= (n); ++i) read(a[i]);
  for (N = 2; N < n; N <<= 1)
    ;
  for (register int i = (1); i <= (N); ++i) lg2[i] = lg2[i >> 1] + 1;
}
namespace neko {
static vector<pair<int, int> > lp[MAXN << 1], rp[MAXN << 1];
static int lb[MAXN << 1], rb[MAXN << 1];
static long long ans[MAXN << 1];
inline int getps(int l, int r) {
  static int ls, rs;
  ls = l + N - 1, rs = r + N - 1;
  return ls >> lg2[ls ^ rs];
}
inline long long calc(int l, int r) {
  static int h, ls, rs, llim, rlim;
  h = getps(l, r), ls = h << 1, rs = h << 1 | 1;
  static long long sm;
  sm = 0ll;
  rlim = lp[rs].size() - 1, llim = rp[ls].size() - 1;
  for (register int i = 0, j = rlim; i <= llim && j >= 0; --j) {
    if (lp[rs][j].second > r) continue;
    while (i <= llim &&
           (rp[ls][i].second < l || (rp[ls][i].first | lp[rs][j].first) < X))
      ++i;
    if (i > llim) break;
    sm += 1ll * (rp[ls][i].second - (l - 1)) *
          ((j == rlim ? r + 1 : min(lp[rs][j + 1].second, r + 1)) -
           lp[rs][j].second);
  }
  return sm;
}
inline void pushup(int h) {
  lp[h] = lp[h << 1];
  static int it;
  it = lp[h << 1].back().first;
  for (auto v : lp[h << 1 | 1])
    if ((v.first | it) > it)
      lp[h].emplace_back(v.first | it, v.second), it |= v.first;
  rp[h] = rp[h << 1 | 1];
  it = rp[h << 1 | 1].back().first;
  for (auto v : rp[h << 1])
    if ((v.first | it) > it)
      rp[h].emplace_back(v.first | it, v.second), it |= v.first;
  ans[h] = calc(lb[h], rb[h]) + ans[h << 1] + ans[h << 1 | 1];
}
void make_tree(int h, int l, int r) {
  lb[h] = l, rb[h] = r;
  if (l == r) {
    lp[h].emplace_back(a[l], l), rp[h].emplace_back(a[l], l),
        ans[h] = a[l] >= X;
    return;
  }
  int mid = (l + r) >> 1;
  make_tree(h << 1, l, mid), make_tree(h << 1 | 1, mid + 1, r);
  pushup(h);
}
inline void modify(int x, int y) {
  static int ps;
  ps = x + N - 1;
  a[x] = y, ans[ps] = (a[x] >= X);
  lp[ps].clear(), rp[ps].clear();
  lp[ps].emplace_back(a[x], x), rp[ps].emplace_back(a[x], x);
  for (ps >>= 1; ps; ps >>= 1) pushup(ps);
}
long long Q(int L, int R) {
  int h = getps(L, R);
  if (L == lb[h] && R == rb[h]) return ans[getps(L, R)];
  return Q(L, rb[h << 1]) + Q(lb[h << 1 | 1], R) + calc(L, R);
}
}  // namespace neko
using namespace neko;
inline void solve() {
  make_tree(1, 1, N);
  static int opt, x, y;
  for (register int i = (1); i <= (m); ++i) {
    read(opt), read(x), read(y);
    if (opt == 1)
      modify(x, y);
    else
      write(Q(x, y));
  }
  flush();
}
int main() {
  init();
  solve();
  return 0;
}

```