#include <bits/stdc++.h>
using namespace std;
const double pi = 3.141592653589793238462643383279;
const double log23 = 1.58496250072115618145373894394781;
const double eps = 1e-10;
const long long INF = 1e18 + 239;
const long long prost = 239;
const int two = 2;
const int th = 3;
const long long MOD = 1e9 + 7;
const long long MOD2 = MOD * MOD;
const int BIG = 1e9 + 239;
const int alf = 26;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
const int dxo[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int dyo[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
const int dig = 10;
const string str_alf = "abcdefghijklmnopqrstuvwxyz";
const string str_alf_big = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const int day[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int digarr[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
const int bt = 31;
template <typename T>
inline T gcd(T a, T b) {
  return a ? gcd(b % a, a) : b;
}
template <typename T>
inline T lcm(T a, T b) {
  return (a / gcd(a, b)) * b;
}
inline bool is_down(char x) { return ('a' <= x && x <= 'z'); }
inline bool is_upper(char x) { return ('A' <= x && x <= 'Z'); }
inline bool is_digit(char x) { return ('0' <= x && x <= '9'); }
long long power(long long a, int k) {
  long long ans = 1;
  while (k) {
    if (k & 1) ans = (ans * a) % MOD;
    ans = (ans * ans) % MOD;
    k >>= 1;
  }
  return ans;
}
mt19937 rnd(239);
const int M = 2 * 1e5 + 239;
const int N = 2 * 1e3 + 239;
const int L = 20;
const int T = (1 << 19);
const int B = trunc(sqrt(M)) + 1;
const int X = 1e4 + 239;
const long long D = 998244353;
struct dsu {
  vector<int> parent, rg, r;
  dsu() { parent = rg = r = {}; }
  dsu(int n) {
    parent.resize(n);
    rg.resize(n);
    r.resize(n);
    for (int i = 0; i < n; i++) parent[i] = i, r[i] = 0, rg[i] = i + 1;
  }
  int find_set(int a) {
    if (parent[a] == a) return a;
    return parent[a] = find_set(parent[a]);
  }
  void merge_set(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a == b) return;
    if (r[a] > r[b]) swap(a, b);
    rg[b] = max(rg[b], rg[a]);
    parent[a] = b;
    if (r[a] == r[b]) r[b]++;
  }
  bool is_connect(int a, int b) { return find_set(a) == find_set(b); }
  int getnxt(int a) { return rg[find_set(a)]; }
};
long long tree[T];
long long a[T], b[T];
inline void build(int i, int l, int r) {
  a[i] = 1;
  b[i] = 0;
  tree[i] = 0;
  if (r - l == 1) return;
  int mid = (l + r) >> 1;
  build(2 * i + 1, l, mid);
  build(2 * i + 2, mid, r);
}
inline void push(int i, int l, int r) {
  tree[i] = (tree[i] * a[i] + b[i] * (long long)(r - l)) % D;
  if (r - l != 1) {
    a[2 * i + 1] = (a[2 * i + 1] * a[i]) % D;
    b[2 * i + 1] = (b[2 * i + 1] * a[i] + b[i]) % D;
    a[2 * i + 2] = (a[2 * i + 2] * a[i]) % D;
    b[2 * i + 2] = (b[2 * i + 2] * a[i] + b[i]) % D;
  }
  a[i] = 1;
  b[i] = 0;
}
inline void change(int i, int l, int r, int ql, int qr, int t) {
  push(i, l, r);
  if (qr <= l || r <= ql) return;
  if (ql <= l && r <= qr) {
    if (t == 0) {
      a[i] = (a[i] * 2LL) % D;
      b[i] = (b[i] * 2LL) % D;
    } else {
      b[i] = (b[i] + 1) % D;
    }
    push(i, l, r);
    return;
  }
  int mid = (l + r) >> 1;
  change(2 * i + 1, l, mid, ql, qr, t);
  change(2 * i + 2, mid, r, ql, qr, t);
  tree[i] = (tree[2 * i + 1] + tree[2 * i + 2]) % D;
}
inline long long getsum(int i, int l, int r, int ql, int qr) {
  push(i, l, r);
  if (qr <= l || r <= ql) return 0;
  if (ql <= l && r <= qr) return tree[i];
  int mid = (l + r) >> 1;
  return (getsum(2 * i + 1, l, mid, ql, qr) +
          getsum(2 * i + 2, mid, r, ql, qr)) %
         D;
}
int n, q;
vector<vector<int> > qr;
vector<vector<int> > vx(M);
vector<vector<pair<int, int> > > seg(M);
vector<vector<bool> > used(M);
vector<dsu> d;
inline void upd(int x, int l, int r) {
  vector<int> nw;
  int i = lower_bound(seg[x].begin(), seg[x].end(), make_pair(l, 0)) -
          seg[x].begin();
  while (i < seg[x].size()) {
    if (seg[x][i].second > r) break;
    if (used[x][i]) {
      i = d[x].getnxt(i);
      continue;
    }
    nw.push_back(i);
    i = d[x].getnxt(i);
  }
  for (int i : nw) change(0, 0, n, seg[x][i].first, seg[x][i].second + 1, 1);
  vector<int> a;
  a.push_back(l);
  for (int i : nw) {
    a.push_back(seg[x][i].first - 1);
    a.push_back(seg[x][i].second + 1);
  }
  a.push_back(r);
  for (int i = 0; i < a.size(); i += 2) {
    if (a[i] > a[i + 1]) continue;
    change(0, 0, n, a[i], a[i + 1] + 1, 0);
  }
  for (int i : nw) {
    used[x][i] = true;
    if (i != 0 && used[x][i - 1]) d[x].merge_set(i - 1, i);
    if (i != (int)seg[x].size() - 1 && used[x][i + 1]) d[x].merge_set(i, i + 1);
  }
}
inline long long gett(int l, int r) { return getsum(0, 0, n, l, r + 1); }
int main() {
  cin.sync_with_stdio(0);
  cin >> n >> q;
  for (int i = 0; i < q; i++) {
    int t;
    cin >> t;
    if (t == 1) {
      int l, r, x;
      cin >> l >> r >> x;
      l--, r--, x--;
      qr.push_back({l, r, x});
      vx[x].push_back(l);
      vx[x].push_back(r);
    } else {
      int l, r;
      cin >> l >> r;
      l--, r--;
      qr.push_back({l, r});
    }
  }
  d.resize(n);
  for (int i = 0; i < n; i++) {
    sort(vx[i].begin(), vx[i].end());
    vx[i].resize(unique(vx[i].begin(), vx[i].end()) - vx[i].begin());
    for (int x = 0; x < vx[i].size(); x++) {
      seg[i].push_back(make_pair(vx[i][x], vx[i][x]));
      if (x + 1 != vx[i].size())
        if (vx[i][x + 1] - vx[i][x] != 1)
          seg[i].push_back(make_pair(vx[i][x] + 1, vx[i][x + 1] - 1));
    }
    used[i].assign(seg[i].size(), false);
    d[i] = dsu(seg[i].size());
  }
  build(0, 0, n);
  for (int z = 0; z < q; z++) {
    if (qr[z].size() == 3)
      upd(qr[z][2], qr[z][0], qr[z][1]);
    else
      cout << gett(qr[z][0], qr[z][1]) << "\n";
  }
  return 0;
}

### Prompt

Your task is to create a cpp solution to the following problem:

In the School of Magic in Dirtpolis a lot of interesting objects are studied on Computer Science lessons.

Consider, for example, the magic multiset. If you try to add an integer to it that is already presented in the multiset, each element in the multiset duplicates. For example, if you try to add the integer 2 to the multiset \{1, 2, 3, 3\}, you will get \{1, 1, 2, 2, 3, 3, 3, 3\}. 

If you try to add an integer that is not presented in the multiset, it is simply added to it. For example, if you try to add the integer 4 to the multiset \{1, 2, 3, 3\}, you will get \{1, 2, 3, 3, 4\}.

Also consider an array of n initially empty magic multisets, enumerated from 1 to n.

You are to answer q queries of the form "add an integer x to all multisets with indices l, l + 1, …, r" and "compute the sum of sizes of multisets with indices l, l + 1, …, r". The answers for the second type queries can be large, so print the answers modulo 998244353.

Input

The first line contains two integers n and q (1 ≤ n, q ≤ 2 ⋅ 10^{5}) — the number of magic multisets in the array and the number of queries, respectively.

The next q lines describe queries, one per line. Each line starts with an integer t (1 ≤ t ≤ 2) — the type of the query. If t equals 1, it is followed by three integers l, r, x (1 ≤ l ≤ r ≤ n, 1 ≤ x ≤ n) meaning that you should add x to all multisets with indices from l to r inclusive. If t equals 2, it is followed by two integers l, r (1 ≤ l ≤ r ≤ n) meaning that you should compute the sum of sizes of all multisets with indices from l to r inclusive.

Output

For each query of the second type print the sum of sizes of multisets on the given segment.

The answers can be large, so print them modulo 998244353.

Examples

Input

4 4
1 1 2 1
1 1 2 2
1 1 4 1
2 1 4


Output

10


Input

3 7
1 1 1 3
1 1 1 3
1 1 1 2
1 1 1 1
2 1 1
1 1 1 2
2 1 1


Output

4
8

Note

In the first example after the first two queries the multisets are equal to [\{1, 2\},\{1, 2\},\{\},\{\}], after the third query they are equal to [\{1, 1, 2, 2\},\{1, 1, 2, 2\},\{1\},\{1\}].

In the second example the first multiset evolves as follows: 

\{\} → \{3\} → \{3, 3\} → \{2, 3, 3\} → \{1, 2, 3, 3\} → \{1, 1, 2, 2, 3, 3, 3, 3\}. 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const double pi = 3.141592653589793238462643383279;
const double log23 = 1.58496250072115618145373894394781;
const double eps = 1e-10;
const long long INF = 1e18 + 239;
const long long prost = 239;
const int two = 2;
const int th = 3;
const long long MOD = 1e9 + 7;
const long long MOD2 = MOD * MOD;
const int BIG = 1e9 + 239;
const int alf = 26;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
const int dxo[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int dyo[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
const int dig = 10;
const string str_alf = "abcdefghijklmnopqrstuvwxyz";
const string str_alf_big = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const int day[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int digarr[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
const int bt = 31;
template <typename T>
inline T gcd(T a, T b) {
  return a ? gcd(b % a, a) : b;
}
template <typename T>
inline T lcm(T a, T b) {
  return (a / gcd(a, b)) * b;
}
inline bool is_down(char x) { return ('a' <= x && x <= 'z'); }
inline bool is_upper(char x) { return ('A' <= x && x <= 'Z'); }
inline bool is_digit(char x) { return ('0' <= x && x <= '9'); }
long long power(long long a, int k) {
  long long ans = 1;
  while (k) {
    if (k & 1) ans = (ans * a) % MOD;
    ans = (ans * ans) % MOD;
    k >>= 1;
  }
  return ans;
}
mt19937 rnd(239);
const int M = 2 * 1e5 + 239;
const int N = 2 * 1e3 + 239;
const int L = 20;
const int T = (1 << 19);
const int B = trunc(sqrt(M)) + 1;
const int X = 1e4 + 239;
const long long D = 998244353;
struct dsu {
  vector<int> parent, rg, r;
  dsu() { parent = rg = r = {}; }
  dsu(int n) {
    parent.resize(n);
    rg.resize(n);
    r.resize(n);
    for (int i = 0; i < n; i++) parent[i] = i, r[i] = 0, rg[i] = i + 1;
  }
  int find_set(int a) {
    if (parent[a] == a) return a;
    return parent[a] = find_set(parent[a]);
  }
  void merge_set(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a == b) return;
    if (r[a] > r[b]) swap(a, b);
    rg[b] = max(rg[b], rg[a]);
    parent[a] = b;
    if (r[a] == r[b]) r[b]++;
  }
  bool is_connect(int a, int b) { return find_set(a) == find_set(b); }
  int getnxt(int a) { return rg[find_set(a)]; }
};
long long tree[T];
long long a[T], b[T];
inline void build(int i, int l, int r) {
  a[i] = 1;
  b[i] = 0;
  tree[i] = 0;
  if (r - l == 1) return;
  int mid = (l + r) >> 1;
  build(2 * i + 1, l, mid);
  build(2 * i + 2, mid, r);
}
inline void push(int i, int l, int r) {
  tree[i] = (tree[i] * a[i] + b[i] * (long long)(r - l)) % D;
  if (r - l != 1) {
    a[2 * i + 1] = (a[2 * i + 1] * a[i]) % D;
    b[2 * i + 1] = (b[2 * i + 1] * a[i] + b[i]) % D;
    a[2 * i + 2] = (a[2 * i + 2] * a[i]) % D;
    b[2 * i + 2] = (b[2 * i + 2] * a[i] + b[i]) % D;
  }
  a[i] = 1;
  b[i] = 0;
}
inline void change(int i, int l, int r, int ql, int qr, int t) {
  push(i, l, r);
  if (qr <= l || r <= ql) return;
  if (ql <= l && r <= qr) {
    if (t == 0) {
      a[i] = (a[i] * 2LL) % D;
      b[i] = (b[i] * 2LL) % D;
    } else {
      b[i] = (b[i] + 1) % D;
    }
    push(i, l, r);
    return;
  }
  int mid = (l + r) >> 1;
  change(2 * i + 1, l, mid, ql, qr, t);
  change(2 * i + 2, mid, r, ql, qr, t);
  tree[i] = (tree[2 * i + 1] + tree[2 * i + 2]) % D;
}
inline long long getsum(int i, int l, int r, int ql, int qr) {
  push(i, l, r);
  if (qr <= l || r <= ql) return 0;
  if (ql <= l && r <= qr) return tree[i];
  int mid = (l + r) >> 1;
  return (getsum(2 * i + 1, l, mid, ql, qr) +
          getsum(2 * i + 2, mid, r, ql, qr)) %
         D;
}
int n, q;
vector<vector<int> > qr;
vector<vector<int> > vx(M);
vector<vector<pair<int, int> > > seg(M);
vector<vector<bool> > used(M);
vector<dsu> d;
inline void upd(int x, int l, int r) {
  vector<int> nw;
  int i = lower_bound(seg[x].begin(), seg[x].end(), make_pair(l, 0)) -
          seg[x].begin();
  while (i < seg[x].size()) {
    if (seg[x][i].second > r) break;
    if (used[x][i]) {
      i = d[x].getnxt(i);
      continue;
    }
    nw.push_back(i);
    i = d[x].getnxt(i);
  }
  for (int i : nw) change(0, 0, n, seg[x][i].first, seg[x][i].second + 1, 1);
  vector<int> a;
  a.push_back(l);
  for (int i : nw) {
    a.push_back(seg[x][i].first - 1);
    a.push_back(seg[x][i].second + 1);
  }
  a.push_back(r);
  for (int i = 0; i < a.size(); i += 2) {
    if (a[i] > a[i + 1]) continue;
    change(0, 0, n, a[i], a[i + 1] + 1, 0);
  }
  for (int i : nw) {
    used[x][i] = true;
    if (i != 0 && used[x][i - 1]) d[x].merge_set(i - 1, i);
    if (i != (int)seg[x].size() - 1 && used[x][i + 1]) d[x].merge_set(i, i + 1);
  }
}
inline long long gett(int l, int r) { return getsum(0, 0, n, l, r + 1); }
int main() {
  cin.sync_with_stdio(0);
  cin >> n >> q;
  for (int i = 0; i < q; i++) {
    int t;
    cin >> t;
    if (t == 1) {
      int l, r, x;
      cin >> l >> r >> x;
      l--, r--, x--;
      qr.push_back({l, r, x});
      vx[x].push_back(l);
      vx[x].push_back(r);
    } else {
      int l, r;
      cin >> l >> r;
      l--, r--;
      qr.push_back({l, r});
    }
  }
  d.resize(n);
  for (int i = 0; i < n; i++) {
    sort(vx[i].begin(), vx[i].end());
    vx[i].resize(unique(vx[i].begin(), vx[i].end()) - vx[i].begin());
    for (int x = 0; x < vx[i].size(); x++) {
      seg[i].push_back(make_pair(vx[i][x], vx[i][x]));
      if (x + 1 != vx[i].size())
        if (vx[i][x + 1] - vx[i][x] != 1)
          seg[i].push_back(make_pair(vx[i][x] + 1, vx[i][x + 1] - 1));
    }
    used[i].assign(seg[i].size(), false);
    d[i] = dsu(seg[i].size());
  }
  build(0, 0, n);
  for (int z = 0; z < q; z++) {
    if (qr[z].size() == 3)
      upd(qr[z][2], qr[z][0], qr[z][1]);
    else
      cout << gett(qr[z][0], qr[z][1]) << "\n";
  }
  return 0;
}

```