#include <bits/stdc++.h>
namespace IO {
int double_len(6);
bool spacebar_can_see(1);
template <typename T>
class Number {
 public:
  unsigned int len;
  int hex;
  T number;
  inline Number(T number = 0, int hex = 10, int len = 0)
      : number(number), hex(hex), len(len) {}
  inline operator T() { return number; }
};
inline bool CanSee(char ch) {
  return spacebar_can_see ? (31 < ch && ch < 127) : (32 < ch && ch < 127);
}
inline bool IsNumber(char ch) { return (47 < ch && ch < 58); }
static const int IN_BUF = 1 << 23, OUT_BUF = 1 << 23;
inline char GetChar() {
  static char buf[IN_BUF], *ps = buf, *pt = buf;
  if (ps == pt) {
    ps = buf;
    pt = buf + fread(buf, 1, IN_BUF, stdin);
  }
  return ps == pt ? EOF : *ps++;
}
inline void PutChar(char ch) {
  static char pbuf[OUT_BUF], *pp = pbuf;
  struct Flusher {
    ~Flusher() { fwrite(pbuf, 1, pp - pbuf, stdout); }
  };
  static Flusher out_put_flusher;
  if (pp == pbuf + OUT_BUF) {
    fwrite(pbuf, 1, OUT_BUF, stdout);
    pp = pbuf;
  }
  *pp++ = ch;
}
char read_ch = '\n';
template <class T>
inline T ReadInt() {
  register T x(0);
  register bool f(1);
  while (!IsNumber(read_ch)) {
    if (read_ch == 45) {
      f = 0;
    }
    read_ch = GetChar();
  }
  while (IsNumber(read_ch)) {
    x = (x << 1) + (x << 3) + (read_ch ^ 48);
    read_ch = GetChar();
  }
  return f ? x : -x;
}
template <class T>
inline T ReadUInt() {
  register T x(0);
  while (!IsNumber(read_ch)) {
    read_ch = GetChar();
  }
  while (IsNumber(read_ch)) {
    x = (x << 1) + (x << 3) + (read_ch ^ 48);
    read_ch = GetChar();
  }
  return x;
}
inline double ReadDouble() {
  register long long int_num(ReadInt<long long>());
  if (read_ch == 46) {
    register double pow10(1.0), result(0);
    read_ch = GetChar();
    while (IsNumber(read_ch)) {
      pow10 /= 10.0;
      result += pow10 * (read_ch ^ 48);
      read_ch = GetChar();
    }
    return int_num + (int_num < 0 ? -result : result);
  } else {
    return (double)int_num;
  }
}
inline void ReadT(int &x) { x = ReadInt<int>(); }
inline void ReadT(long long &x) { x = ReadInt<long long>(); }
inline void ReadT(bool &x) { x = ReadUInt<bool>(); }
inline void ReadT(unsigned int &x) { x = ReadUInt<unsigned int>(); }
inline void ReadT(unsigned long long &x) { x = ReadUInt<unsigned long long>(); }
inline void ReadT(double &x) { x = ReadDouble(); }
inline void ReadT(char &s) {
  for (; !CanSee(read_ch) && (~read_ch); read_ch = GetChar())
    ;
  s = read_ch;
  read_ch = 10;
}
inline void ReadT(char *s) {
  register int len(0);
  for (; !CanSee(read_ch) && (~read_ch); read_ch = GetChar())
    ;
  for (; CanSee(read_ch) && (~read_ch); read_ch = GetChar()) {
    s[len++] = read_ch;
  }
  s[len] = 0;
  read_ch = 10;
}
template <typename T>
inline void ReadT(Number<T> &x) {
  ReadT(x.number);
}
template <typename T>
inline void Read(T &t) {
  ReadT(t);
}
template <typename T, typename... Args>
void Read(T &t, Args &...args) {
  ReadT(t);
  Read(args...);
}
const char NUMBER[36] = {48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 65, 66,
                         67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78,
                         79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90};
template <typename T>
void WriteInt(T x) {
  if (x < 0) {
    PutChar(45);
    x = -x;
  }
  if (9 < x) {
    WriteInt(x / 10);
  }
  PutChar(x % 10 ^ 48);
}
template <typename T>
void WriteUInt(T x) {
  if (9 < x) {
    WriteInt(x / 10);
  }
  PutChar(x % 10 ^ 48);
}
template <typename T>
void WriteKInt(T x, int hex, int len) {
  if (x < 0) {
    PutChar(45);
    --len;
    x = -x;
  }
  if (hex <= x || 1 < len) {
    WriteKInt(x / hex, hex, len - 1);
  }
  PutChar(NUMBER[x % hex]);
}
template <typename T>
void WriteUKInt(T x, int hex, int len) {
  if (hex <= x || 1 < len) {
    WriteKInt(x / hex, hex, len - 1);
  }
  PutChar(NUMBER[x % hex]);
}
inline void WriteDouble(double x, int len) {
  if (x < 0) {
    x = -x;
    PutChar(45);
  }
  WriteUInt((unsigned long long)x);
  if (len) {
    x -= (int)x;
    PutChar(46);
    while (len--) {
      x *= 10;
      if (!(unsigned long long)x) {
        PutChar(48);
      }
    }
    WriteUInt((unsigned long long)x);
  }
}
inline void WriteT(int x) { WriteInt<int>(x); }
inline void WriteT(long long x) { WriteInt<long long>(x); }
inline void WriteT(bool x) { WriteUInt<bool>(x); }
inline void WriteT(unsigned int x) { WriteUInt<unsigned int>(x); }
inline void WriteT(unsigned long long x) { WriteUInt<unsigned long long>(x); }
inline void WriteT(double x) { WriteDouble(x, double_len); }
inline void WriteT(char *s) {
  int len(strlen(s));
  while (len--) {
    PutChar(*s++);
  }
}
inline void WriteT(const char *s) {
  while (*s) {
    PutChar(*s++);
  }
}
inline void WriteT(char x) { PutChar(x); }
template <typename T>
inline void WriteT(Number<T> x) {
  if (typeid(T) == typeid(int) || typeid(T) == typeid(long long)) {
    WriteKInt(x.number, x.hex, x.len);
    return;
  }
  if (typeid(T) == typeid(unsigned int) ||
      typeid(T) == typeid(unsigned long long)) {
    WriteKInt(x.number, x.hex, x.len);
    return;
  }
  WriteT("Can't write this type.");
}
template <typename T>
inline void Write(T t) {
  WriteT(t);
}
template <typename T, typename... Args>
void Write(T t, Args... args) {
  WriteT(t);
  Write(args...);
}
inline void Writeln() { PutChar(10); }
template <typename T>
inline void Writeln(T t) {
  WriteT(t);
  PutChar(10);
}
template <typename... Args>
inline void Writeln(Args... args) {
  Write(args...);
  PutChar(10);
}
template <typename... Args>
inline void WriteExit(Args... args) {
  Write(args...);
  PutChar(10);
  exit(0);
}
}  // namespace IO
using namespace std;
using namespace IO;
const int MAXN = 1e5 + 5;
int n, m, x;
int arr[MAXN];
namespace SGT {
struct SegmentTree {
  int cntl, cntr;
  int numl[21];
  int lenl[21];
  int numr[21];
  int lenr[21];
  long long sum = 0;
  SegmentTree(int kind = 0) { sum = -1 * kind; }
} sgt[MAXN << 2], for_make, null(1);
inline SegmentTree Merge(SegmentTree lson, SegmentTree rson) {
  if (lson.sum == -1) {
    return rson;
  }
  if (rson.sum == -1) {
    return lson;
  }
  for_make = lson;
  for_make.sum += rson.sum;
  register int now = lson.numl[lson.cntl];
  for (int i = 0; i <= rson.cntl; ++i) {
    if ((now | rson.numl[i]) == now) {
      for_make.lenl[for_make.cntl] += rson.lenl[i];
    } else {
      for_make.lenl[++for_make.cntl] = rson.lenl[i];
      for_make.numl[for_make.cntl] = now | rson.numl[i];
      now |= rson.numl[i];
    }
  }
  now = rson.numr[for_make.cntr = rson.cntr];
  for (int i = 0; i <= rson.cntr; ++i) {
    for_make.numr[i] = rson.numr[i];
    for_make.lenr[i] = rson.lenr[i];
  }
  for (int i = 0; i <= lson.cntr; ++i) {
    if ((now | lson.numr[i]) == now) {
      for_make.lenr[for_make.cntr] += lson.lenr[i];
    } else {
      for_make.lenr[++for_make.cntr] = lson.lenr[i];
      for_make.numr[for_make.cntr] = now | lson.numr[i];
      now |= lson.numr[i];
    }
  }
  now = rson.cntl;
  register long long sumlen = rson.lenl[now];
  for (int i = 0; i <= lson.cntr; ++i) {
    if (x <= (lson.numr[i] | rson.numl[now])) {
      while (now && x <= (lson.numr[i] | rson.numl[now - 1])) {
        sumlen += rson.lenl[--now];
      }
      for_make.sum += 1ll * lson.lenr[i] * sumlen;
    }
  }
  return for_make;
}
inline void PushUp(int now) {
  sgt[now] = Merge(sgt[(now << 1)], sgt[(now << 1 | 1)]);
}
void Build(int now = 1, int left = 1, int right = n) {
  if (left == right) {
    sgt[now].numl[sgt[now].cntl = 0] = sgt[now].numr[sgt[now].cntr = 0] =
        arr[left];
    sgt[now].lenl[0] = sgt[now].lenr[0] = 1;
    sgt[now].sum = x <= arr[left];
    return;
  }
  Build((now << 1), left, ((left + right) >> 1));
  Build((now << 1 | 1), ((left + right) >> 1) + 1, right);
  PushUp(now);
}
void Updata(int place, int num, int now = 1, int left = 1, int right = n) {
  if (place < left || right < place) {
    return;
  }
  if (left == right) {
    sgt[now].numl[sgt[now].cntl = 0] = sgt[now].numr[sgt[now].cntr = 0] = num;
    sgt[now].lenl[0] = sgt[now].lenr[0] = 1;
    sgt[now].sum = x <= num;
    return;
  }
  Updata(place, num, (now << 1), left, ((left + right) >> 1));
  Updata(place, num, (now << 1 | 1), ((left + right) >> 1) + 1, right);
  PushUp(now);
}
SegmentTree Query(int now_left, int now_right, int now = 1, int left = 1,
                  int right = n) {
  if (now_right < left || right < now_left) {
    return null;
  }
  if (now_left <= left && right <= now_right) {
    return sgt[now];
  }
  return Merge(
      Query(now_left, now_right, (now << 1), left, ((left + right) >> 1)),
      Query(now_left, now_right, (now << 1 | 1), ((left + right) >> 1) + 1,
            right));
}
}  // namespace SGT
int main() {
  Read(n, m, x);
  for (int i = 1; i <= n; ++i) {
    Read(arr[i]);
  }
  SGT::Build();
  int opt, l, r, x, y;
  for (int i = 1; i <= m; ++i) {
    Read(opt);
    if (opt == 1) {
      Read(x, y);
      SGT::Updata(x, y);
    }
    if (opt == 2) {
      Read(l, r);
      Writeln(SGT::Query(l, r).sum);
    }
  }
  return 0;
}

### Prompt

Your challenge is to write a Cpp solution to 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>
namespace IO {
int double_len(6);
bool spacebar_can_see(1);
template <typename T>
class Number {
 public:
  unsigned int len;
  int hex;
  T number;
  inline Number(T number = 0, int hex = 10, int len = 0)
      : number(number), hex(hex), len(len) {}
  inline operator T() { return number; }
};
inline bool CanSee(char ch) {
  return spacebar_can_see ? (31 < ch && ch < 127) : (32 < ch && ch < 127);
}
inline bool IsNumber(char ch) { return (47 < ch && ch < 58); }
static const int IN_BUF = 1 << 23, OUT_BUF = 1 << 23;
inline char GetChar() {
  static char buf[IN_BUF], *ps = buf, *pt = buf;
  if (ps == pt) {
    ps = buf;
    pt = buf + fread(buf, 1, IN_BUF, stdin);
  }
  return ps == pt ? EOF : *ps++;
}
inline void PutChar(char ch) {
  static char pbuf[OUT_BUF], *pp = pbuf;
  struct Flusher {
    ~Flusher() { fwrite(pbuf, 1, pp - pbuf, stdout); }
  };
  static Flusher out_put_flusher;
  if (pp == pbuf + OUT_BUF) {
    fwrite(pbuf, 1, OUT_BUF, stdout);
    pp = pbuf;
  }
  *pp++ = ch;
}
char read_ch = '\n';
template <class T>
inline T ReadInt() {
  register T x(0);
  register bool f(1);
  while (!IsNumber(read_ch)) {
    if (read_ch == 45) {
      f = 0;
    }
    read_ch = GetChar();
  }
  while (IsNumber(read_ch)) {
    x = (x << 1) + (x << 3) + (read_ch ^ 48);
    read_ch = GetChar();
  }
  return f ? x : -x;
}
template <class T>
inline T ReadUInt() {
  register T x(0);
  while (!IsNumber(read_ch)) {
    read_ch = GetChar();
  }
  while (IsNumber(read_ch)) {
    x = (x << 1) + (x << 3) + (read_ch ^ 48);
    read_ch = GetChar();
  }
  return x;
}
inline double ReadDouble() {
  register long long int_num(ReadInt<long long>());
  if (read_ch == 46) {
    register double pow10(1.0), result(0);
    read_ch = GetChar();
    while (IsNumber(read_ch)) {
      pow10 /= 10.0;
      result += pow10 * (read_ch ^ 48);
      read_ch = GetChar();
    }
    return int_num + (int_num < 0 ? -result : result);
  } else {
    return (double)int_num;
  }
}
inline void ReadT(int &x) { x = ReadInt<int>(); }
inline void ReadT(long long &x) { x = ReadInt<long long>(); }
inline void ReadT(bool &x) { x = ReadUInt<bool>(); }
inline void ReadT(unsigned int &x) { x = ReadUInt<unsigned int>(); }
inline void ReadT(unsigned long long &x) { x = ReadUInt<unsigned long long>(); }
inline void ReadT(double &x) { x = ReadDouble(); }
inline void ReadT(char &s) {
  for (; !CanSee(read_ch) && (~read_ch); read_ch = GetChar())
    ;
  s = read_ch;
  read_ch = 10;
}
inline void ReadT(char *s) {
  register int len(0);
  for (; !CanSee(read_ch) && (~read_ch); read_ch = GetChar())
    ;
  for (; CanSee(read_ch) && (~read_ch); read_ch = GetChar()) {
    s[len++] = read_ch;
  }
  s[len] = 0;
  read_ch = 10;
}
template <typename T>
inline void ReadT(Number<T> &x) {
  ReadT(x.number);
}
template <typename T>
inline void Read(T &t) {
  ReadT(t);
}
template <typename T, typename... Args>
void Read(T &t, Args &...args) {
  ReadT(t);
  Read(args...);
}
const char NUMBER[36] = {48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 65, 66,
                         67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78,
                         79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90};
template <typename T>
void WriteInt(T x) {
  if (x < 0) {
    PutChar(45);
    x = -x;
  }
  if (9 < x) {
    WriteInt(x / 10);
  }
  PutChar(x % 10 ^ 48);
}
template <typename T>
void WriteUInt(T x) {
  if (9 < x) {
    WriteInt(x / 10);
  }
  PutChar(x % 10 ^ 48);
}
template <typename T>
void WriteKInt(T x, int hex, int len) {
  if (x < 0) {
    PutChar(45);
    --len;
    x = -x;
  }
  if (hex <= x || 1 < len) {
    WriteKInt(x / hex, hex, len - 1);
  }
  PutChar(NUMBER[x % hex]);
}
template <typename T>
void WriteUKInt(T x, int hex, int len) {
  if (hex <= x || 1 < len) {
    WriteKInt(x / hex, hex, len - 1);
  }
  PutChar(NUMBER[x % hex]);
}
inline void WriteDouble(double x, int len) {
  if (x < 0) {
    x = -x;
    PutChar(45);
  }
  WriteUInt((unsigned long long)x);
  if (len) {
    x -= (int)x;
    PutChar(46);
    while (len--) {
      x *= 10;
      if (!(unsigned long long)x) {
        PutChar(48);
      }
    }
    WriteUInt((unsigned long long)x);
  }
}
inline void WriteT(int x) { WriteInt<int>(x); }
inline void WriteT(long long x) { WriteInt<long long>(x); }
inline void WriteT(bool x) { WriteUInt<bool>(x); }
inline void WriteT(unsigned int x) { WriteUInt<unsigned int>(x); }
inline void WriteT(unsigned long long x) { WriteUInt<unsigned long long>(x); }
inline void WriteT(double x) { WriteDouble(x, double_len); }
inline void WriteT(char *s) {
  int len(strlen(s));
  while (len--) {
    PutChar(*s++);
  }
}
inline void WriteT(const char *s) {
  while (*s) {
    PutChar(*s++);
  }
}
inline void WriteT(char x) { PutChar(x); }
template <typename T>
inline void WriteT(Number<T> x) {
  if (typeid(T) == typeid(int) || typeid(T) == typeid(long long)) {
    WriteKInt(x.number, x.hex, x.len);
    return;
  }
  if (typeid(T) == typeid(unsigned int) ||
      typeid(T) == typeid(unsigned long long)) {
    WriteKInt(x.number, x.hex, x.len);
    return;
  }
  WriteT("Can't write this type.");
}
template <typename T>
inline void Write(T t) {
  WriteT(t);
}
template <typename T, typename... Args>
void Write(T t, Args... args) {
  WriteT(t);
  Write(args...);
}
inline void Writeln() { PutChar(10); }
template <typename T>
inline void Writeln(T t) {
  WriteT(t);
  PutChar(10);
}
template <typename... Args>
inline void Writeln(Args... args) {
  Write(args...);
  PutChar(10);
}
template <typename... Args>
inline void WriteExit(Args... args) {
  Write(args...);
  PutChar(10);
  exit(0);
}
}  // namespace IO
using namespace std;
using namespace IO;
const int MAXN = 1e5 + 5;
int n, m, x;
int arr[MAXN];
namespace SGT {
struct SegmentTree {
  int cntl, cntr;
  int numl[21];
  int lenl[21];
  int numr[21];
  int lenr[21];
  long long sum = 0;
  SegmentTree(int kind = 0) { sum = -1 * kind; }
} sgt[MAXN << 2], for_make, null(1);
inline SegmentTree Merge(SegmentTree lson, SegmentTree rson) {
  if (lson.sum == -1) {
    return rson;
  }
  if (rson.sum == -1) {
    return lson;
  }
  for_make = lson;
  for_make.sum += rson.sum;
  register int now = lson.numl[lson.cntl];
  for (int i = 0; i <= rson.cntl; ++i) {
    if ((now | rson.numl[i]) == now) {
      for_make.lenl[for_make.cntl] += rson.lenl[i];
    } else {
      for_make.lenl[++for_make.cntl] = rson.lenl[i];
      for_make.numl[for_make.cntl] = now | rson.numl[i];
      now |= rson.numl[i];
    }
  }
  now = rson.numr[for_make.cntr = rson.cntr];
  for (int i = 0; i <= rson.cntr; ++i) {
    for_make.numr[i] = rson.numr[i];
    for_make.lenr[i] = rson.lenr[i];
  }
  for (int i = 0; i <= lson.cntr; ++i) {
    if ((now | lson.numr[i]) == now) {
      for_make.lenr[for_make.cntr] += lson.lenr[i];
    } else {
      for_make.lenr[++for_make.cntr] = lson.lenr[i];
      for_make.numr[for_make.cntr] = now | lson.numr[i];
      now |= lson.numr[i];
    }
  }
  now = rson.cntl;
  register long long sumlen = rson.lenl[now];
  for (int i = 0; i <= lson.cntr; ++i) {
    if (x <= (lson.numr[i] | rson.numl[now])) {
      while (now && x <= (lson.numr[i] | rson.numl[now - 1])) {
        sumlen += rson.lenl[--now];
      }
      for_make.sum += 1ll * lson.lenr[i] * sumlen;
    }
  }
  return for_make;
}
inline void PushUp(int now) {
  sgt[now] = Merge(sgt[(now << 1)], sgt[(now << 1 | 1)]);
}
void Build(int now = 1, int left = 1, int right = n) {
  if (left == right) {
    sgt[now].numl[sgt[now].cntl = 0] = sgt[now].numr[sgt[now].cntr = 0] =
        arr[left];
    sgt[now].lenl[0] = sgt[now].lenr[0] = 1;
    sgt[now].sum = x <= arr[left];
    return;
  }
  Build((now << 1), left, ((left + right) >> 1));
  Build((now << 1 | 1), ((left + right) >> 1) + 1, right);
  PushUp(now);
}
void Updata(int place, int num, int now = 1, int left = 1, int right = n) {
  if (place < left || right < place) {
    return;
  }
  if (left == right) {
    sgt[now].numl[sgt[now].cntl = 0] = sgt[now].numr[sgt[now].cntr = 0] = num;
    sgt[now].lenl[0] = sgt[now].lenr[0] = 1;
    sgt[now].sum = x <= num;
    return;
  }
  Updata(place, num, (now << 1), left, ((left + right) >> 1));
  Updata(place, num, (now << 1 | 1), ((left + right) >> 1) + 1, right);
  PushUp(now);
}
SegmentTree Query(int now_left, int now_right, int now = 1, int left = 1,
                  int right = n) {
  if (now_right < left || right < now_left) {
    return null;
  }
  if (now_left <= left && right <= now_right) {
    return sgt[now];
  }
  return Merge(
      Query(now_left, now_right, (now << 1), left, ((left + right) >> 1)),
      Query(now_left, now_right, (now << 1 | 1), ((left + right) >> 1) + 1,
            right));
}
}  // namespace SGT
int main() {
  Read(n, m, x);
  for (int i = 1; i <= n; ++i) {
    Read(arr[i]);
  }
  SGT::Build();
  int opt, l, r, x, y;
  for (int i = 1; i <= m; ++i) {
    Read(opt);
    if (opt == 1) {
      Read(x, y);
      SGT::Updata(x, y);
    }
    if (opt == 2) {
      Read(l, r);
      Writeln(SGT::Query(l, r).sum);
    }
  }
  return 0;
}

```