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\}. 
#include <bits/stdc++.h>
using namespace std;
long MOD = 998244353;
long n;
long p;
long* tree;
long long* lazy_add;
long long* lazy_multiply;
long bit_length(long value) {
  long res = 0;
  while (value) {
    res++;
    value >>= 1;
  }
  return res;
}
void wn(long& num, char* str) {
  long i = 0;
  if (num == 0) {
    str[i++] = '0';
    str[i] = '\0';
    puts(str);
    return;
  }
  while (num != 0) {
    int rem = num % 10;
    str[i++] = rem + 48;
    num /= 10;
  }
  str[i] = '\0';
  char* start = str;
  char* end = str + i - 1;
  char tmp;
  while (start < end) {
    tmp = *start;
    *start = *end;
    *end = tmp;
    start++;
    end--;
  }
  puts(str);
}
void ni(long& number) {
  register long c;
  number = 0;
  while (true) {
    c = getchar();
    if (c > 47 && c < 58) {
      number = c - 48;
      break;
    }
  }
  while (true) {
    c = getchar();
    if (c < 48 || c > 57) break;
    number = number * 10 + c - 48;
  }
}
void push_down(long node_min, long node_max, long node) {
  long node_diff = node_max - node_min;
  long long lazy_multiply_val = lazy_multiply[node];
  if (lazy_multiply_val != 1) {
    if (node_diff) {
      long left_node = node << 1;
      long right_node = left_node + 1;
      if (tree[left_node] && tree[left_node] == tree[right_node]) {
        tree[left_node] = tree[right_node] =
            (tree[left_node] * lazy_multiply_val) % MOD;
      } else {
        if (tree[left_node])
          tree[left_node] = (tree[left_node] * lazy_multiply_val) % MOD;
        if (tree[right_node])
          tree[right_node] = (tree[right_node] * lazy_multiply_val) % MOD;
      }
      if (node_diff > 2) {
        lazy_multiply[left_node] =
            (lazy_multiply[left_node] * lazy_multiply_val) % MOD;
        lazy_multiply[right_node] =
            (lazy_multiply[right_node] * lazy_multiply_val) % MOD;
        if (lazy_add[left_node] &&
            lazy_add[left_node] == lazy_add[right_node]) {
          lazy_add[left_node] = lazy_add[right_node] =
              (lazy_add[left_node] * lazy_multiply_val) % MOD;
        } else {
          if (lazy_add[left_node])
            lazy_add[left_node] =
                (lazy_add[left_node] * lazy_multiply_val) % MOD;
          if (lazy_add[right_node])
            lazy_add[right_node] =
                (lazy_add[right_node] * lazy_multiply_val) % MOD;
        }
      }
    }
    lazy_multiply[node] = 1;
  }
  long long lazy_add_val = lazy_add[node];
  if (lazy_add_val) {
    if (node_diff) {
      long left_node = node << 1;
      long right_node = left_node + 1;
      long add_value = (((node_diff + 1) * lazy_add_val) >> 1) % MOD;
      long new_value_left = (long)((tree[left_node] + add_value) % MOD);
      long new_value_right = (long)((tree[right_node] + add_value) % MOD);
      tree[left_node] = new_value_left;
      tree[right_node] = new_value_right;
      if (node_diff > 2) {
        lazy_add[left_node] += lazy_add_val;
        if (lazy_add[left_node] >= MOD) lazy_add[left_node] -= MOD;
        lazy_add[right_node] += lazy_add_val;
        if (lazy_add[right_node] >= MOD) lazy_add[right_node] -= MOD;
      }
    }
    lazy_add[node] = 0;
  }
}
void increment(long left, long right, long node_min, long node_max, long node) {
  if (left > node_max || right < node_min) return;
  if (node_min == node_max) {
    long new_value = tree[node] + 1;
    if (new_value >= MOD) new_value -= MOD;
    tree[node] = new_value;
    return;
  }
  if (left <= node_min && right >= node_max) {
    long node_diff = node_max - node_min;
    long new_value = (long)((tree[node] + (node_diff + 1)) % MOD);
    tree[node] = new_value;
    lazy_add[node]++;
    return;
  }
  if (lazy_add[node] != 0 || lazy_multiply[node] != 1)
    push_down(node_min, min(node_max, n), node);
  long left_node = node << 1;
  long right_node = left_node + 1;
  long mid_node = (node_min + node_max) >> 1;
  increment(left, right, node_min, mid_node, left_node);
  increment(left, right, mid_node + 1, node_max, right_node);
  long new_value = tree[left_node] + tree[right_node];
  if (new_value >= MOD) new_value -= MOD;
  tree[node] = new_value;
}
void twice(long left, long right, long node_min, long node_max, long node) {
  if (left > node_max || right < node_min) return;
  if (node_min == node_max) {
    tree[node] <<= 1;
    if (tree[node] >= MOD) tree[node] -= MOD;
    return;
  }
  if (left <= node_min && right >= node_max) {
    tree[node] <<= 1;
    if (tree[node] >= MOD) tree[node] -= MOD;
    lazy_multiply[node] <<= 1;
    if (lazy_multiply[node] >= MOD) lazy_multiply[node] -= MOD;
    lazy_add[node] <<= 1;
    if (lazy_add[node] >= MOD) lazy_add[node] -= MOD;
    return;
  }
  if (lazy_add[node] != 0 || lazy_multiply[node] != 1)
    push_down(node_min, node_max, node);
  long left_node = node << 1;
  long right_node = left_node + 1;
  long mid_node = (node_min + node_max) >> 1;
  twice(left, right, node_min, mid_node, left_node);
  twice(left, right, mid_node + 1, node_max, right_node);
  long new_value = tree[left_node] + tree[right_node];
  if (new_value >= MOD) new_value -= MOD;
  tree[node] = new_value;
}
long query(long left, long right, long node_min, long node_max, long node) {
  if (left > node_max || right < node_min) return 0;
  if (node_min == node_max) return tree[node];
  if (left <= node_min && right >= node_max) return tree[node];
  if (lazy_add[node] != 0 || lazy_multiply[node] != 1)
    push_down(node_min, node_max, node);
  long left_node = node << 1;
  long right_node = left_node + 1;
  long mid_node = (node_min + node_max) >> 1;
  long left_query = query(left, right, node_min, mid_node, left_node);
  long right_query = query(left, right, mid_node + 1, node_max, right_node);
  long new_value = (left_query + right_query);
  if (new_value >= MOD) {
    new_value = new_value - MOD;
  }
  return new_value;
}
long bisect_left(vector<long>* list, long& value) {
  vector<long>::iterator it = lower_bound(list->begin(), list->end(), value);
  return it - list->begin();
}
void removeRange(vector<long>* range_values, long a, long b) {
  range_values->erase(range_values->begin() + a, range_values->begin() + b);
}
void solve() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ifstream in("G:\\CodeForces\\981\\input.txt");
  long n_val, q;
  ni(n_val);
  ni(q);
  long ceil_sqrt_n = ceil(log2(n_val));
  n = (long)(pow(2, ceil_sqrt_n));
  p = 1 << bit_length((n)-1);
  long tree_len = p << 1;
  tree = new long[tree_len];
  lazy_add = new long long[tree_len];
  lazy_multiply = new long long[tree_len];
  for (int i = 0; i < tree_len; i++) {
    tree[i] = lazy_add[i] = 0;
    lazy_multiply[i] = 1;
  }
  vector<vector<long>*> ranges{NULL};
  ranges.resize(n + 1);
  long op;
  long q_l;
  long q_r;
  long q_v;
  char output_str[10];
  while (q-- != 0) {
    ni(op);
    ni(q_l);
    ni(q_r);
    if (op == 2) {
      long res = query(q_l, q_r, 1, n, 1);
      wn(res, output_str);
    } else {
      ni(q_v);
      if (ranges[q_v] == NULL) ranges[q_v] = new vector<long>;
      vector<long>* range_values = ranges[q_v];
      long start = q_l;
      long end = q_r;
      if (range_values->size() == 0 ||
          start > range_values->at(range_values->size() - 1))
        increment(start, end, 1, n, 1);
      else {
        long pos = start;
        long index = bisect_left(range_values, pos);
        bool empty = pos != range_values->at(index) && (index & 1) == 0;
        if (!empty && pos == range_values->at(index) && (index & 1) == 0)
          index += 1;
        while (pos <= end) {
          long range_end;
          if (empty) {
            range_end = index != range_values->size()
                            ? min(end, range_values->at(index) - 1)
                            : end;
            increment(pos, range_end, 1, n, 1);
          } else {
            range_end = index != range_values->size()
                            ? min(end, range_values->at(index))
                            : end;
            twice(pos, range_end, 1, n, 1);
          }
          pos = range_end + 1;
          index += 1;
          empty = !empty;
        }
      }
      if (range_values->size() == 0) {
        range_values->push_back(start);
        range_values->push_back(end);
      } else {
        long start_index = bisect_left(range_values, start);
        long end_index = bisect_left(range_values, end);
        bool start_empty = (start_index == range_values->size() ||
                            start != range_values->at(start_index)) &&
                           (start_index & 1) == 0;
        bool end_empty = (end_index == range_values->size() ||
                          end != range_values->at(end_index)) &&
                         (end_index & 1) == 0;
        if (!start_empty && !end_empty) {
          long start_segment = start_index >> 1;
          long end_segment = end_index >> 1;
          if (start_segment != end_segment)
            removeRange(range_values, start_index | 1, end_index | 1);
        } else if (start_empty && end_empty) {
          bool start_near_left = start_index != 0 &&
                                 start == range_values->at(start_index - 1) + 1;
          bool end_near_right = end_index != range_values->size() &&
                                end == range_values->at(end_index) - 1;
          if (start_index == end_index) {
            if (!start_near_left && !end_near_right) {
              range_values->emplace(range_values->begin() + end_index, end);
              range_values->emplace(range_values->begin() + start_index, start);
            } else if (start_near_left && end_near_right)
              removeRange(range_values, start_index - 1, start_index + 1);
            else if (start_near_left)
              range_values->at(start_index - 1) = end;
            else if (end_near_right)
              range_values->at(start_index) = start;
          } else {
            if (!start_near_left && !end_near_right) {
              range_values->at(start_index) = start;
              range_values->at(end_index - 1) = end;
              removeRange(range_values, start_index + 1, end_index - 1);
            } else if (start_near_left && end_near_right)
              removeRange(range_values, start_index - 1, end_index + 1);
            else if (start_near_left) {
              range_values->at(end_index - 1) = end;
              removeRange(range_values, start_index - 1, end_index - 1);
            } else if (end_near_right) {
              range_values->at(start_index) = start;
              removeRange(range_values, start_index + 1, end_index + 1);
            }
          }
        } else if (start_empty) {
          bool start_near_left = start_index != 0 &&
                                 start == range_values->at(start_index - 1) + 1;
          if (start_near_left)
            removeRange(range_values, start_index - 1, end_index | 1);
          else {
            range_values->at(start_index) = start;
            removeRange(range_values, start_index + 1, end_index | 1);
          }
        } else if (end_empty) {
          bool end_near_right = end_index != range_values->size() &&
                                end == range_values->at(end_index) - 1;
          if (end_near_right)
            removeRange(range_values, start_index | 1, end_index + 1);
          else {
            range_values->at(end_index - 1) = end;
            removeRange(range_values, start_index | 1, end_index - 1);
          }
        }
      }
    }
  }
}
int main() {
  solve();
  return 0;
}
