Problem: Write a program which manipulates a sequence $A$ = {$a_0, a_1, ..., a_{n-1}$} with the following operations:

* $update(s, t, x)$: change $a_s, a_{s+1}, ..., a_t$ to $x$.
* $getSum(s, t)$: print the sum of $a_s, a_{s+1}, ..., a_t$.



Note that the initial values of $a_i ( i = 0, 1, ..., n-1 )$ are 0.

Constraints

* $1 ≤ n ≤ 100000$
* $1 ≤ q ≤ 100000$
* $0 ≤ s ≤ t < n$
* $-1000 ≤ x ≤ 1000$

Input


$n$ $q$
$query_1$
$query_2$
:
$query_q$


In the first line, $n$ (the number of elements in $A$) and $q$ (the number of queries) are given. Then, $i$-th query $query_i$ is given in the following format:


0 $s$ $t$ $x$


or


1 $s$ $t$


The first digit represents the type of the query. '0' denotes $update(s, t, x)$ and '1' denotes $find(s, t)$.

Output

For each $getSum$ query, print the sum in a line.

Example

Input

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


Output

-5
1
6
8

Solution (in CPP):

Solution:
#include <algorithm>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <queue>
#include <stack>
#include <utility>
#include <vector>
using std::cerr;
using std::cin;
using std::cout;
using std::endl;




//see also: http://tsutaj.hatenablog.com/entry/2017/03/29/204841

template<typename VM,typename OM>
class LazySegmentTree{
protected:
  int                 range_;
  VM              value_identity_;
  OM              operator_identity_;
  std::vector<VM> value_tree_;
  std::vector<OM> lazy_tree_;

  virtual VM MergeValue(const VM& a, const VM& b)=0;
  virtual OM MergeOperator(const OM& target,const OM& effector)=0;
  virtual VM Operate(const VM& val, const OM& opl)=0;
  virtual OM GetOperator(const OM& opl, const int n)=0;

  VM InternalMerge(const VM& a, const VM& b){
    if(a==value_identity_){
      return b;
    }else if(b==value_identity_){
      return a;
    }else{
      return MergeValue(a,b);
    }
  }

  int Parent(const int child) const{
    return (child - 1) / 2;
  }

  int LeftChild(const int parent) const{
    return parent * 2 + 1;
  }

  int RightChild(const int parent) const{
    return parent * 2 + 2;
  }

  void Propagate(int node,int len){
    if(lazy_tree_[node]!=operator_identity_){
      if(node*2+2<range_*2){
        lazy_tree_[LeftChild(node)]=MergeOperator(lazy_tree_[LeftChild(node)],lazy_tree_[node]);
        lazy_tree_[RightChild(node)]=MergeOperator(lazy_tree_[RightChild(node)],lazy_tree_[node]);
      }

      value_tree_[node]=Operate(value_tree_[node],GetOperator(lazy_tree_[node],len));
      lazy_tree_[node]=operator_identity_;
    }
  }

  VM GetRangeOperation(int query_l, int query_r, int node, int l, int r){
    Propagate(node,r-l);
    if(r <= query_l || query_r <= l){
      return value_identity_;
    }else if(query_l <= l && r <= query_r){
      return value_tree_[node];
    }else{
      VM vl = GetRangeOperation(query_l, query_r, LeftChild(node), l,
                                    (l + r) / 2);
      VM vr = GetRangeOperation(query_l, query_r, RightChild(node),
                                    (l + r) / 2, r);
      return InternalMerge(vl, vr);
    }

  }

  VM Update(int a,int b, OM opr,int node,int l,int r){
    Propagate(node, r - l);
    if(r <= a || b <= l) return value_tree_[node];
    if(a <= l && r <= b){
      lazy_tree_[node] = MergeOperator(lazy_tree_[node],opr);
      Propagate(node, r - l);
      return Operate(value_tree_[node],GetOperator(lazy_tree_[node],r-l));
    }else{
      Update(a, b, opr, LeftChild(node), l, (l + r) / 2);
      Update(a, b, opr, RightChild(node), (l + r) / 2, r);
      value_tree_[node]= InternalMerge(value_tree_[LeftChild(node)],
                                       value_tree_[RightChild(node)]);
      return value_tree_[node];
    }
  }

public:

  /// \brief construct the segment tree.
  /// \param identity the element e s.t. a*e = e*a = a  (単位元)
  //FIXME: コンストラクタ中で仮想関数を使わないようにする
  LazySegmentTree(const VM& value_identity, const OM& operator_identity,
      int size): value_identity_(
      value_identity),operator_identity_(operator_identity){
    int sz = size;
    range_ = 1;
    while(range_ < sz){
      range_ *= 2;
    }
    value_tree_.resize(2 * range_ - 1, value_identity);
    lazy_tree_.resize(2*range_-1,operator_identity);

  }

  void Init(const std::vector<VM>& v){
    for(int i = 0; i < v.size(); i++){
      value_tree_[i + range_ - 1] = v[i];
    }
    for(int i = range_ - 2; i >= 0; i--){
      value_tree_[i] =
          InternalMerge(value_tree_[LeftChild(i)], value_tree_[RightChild(i)]);
    }
  }


  void Update(int a,int b, OM opr){
    Update(a,b,opr,0,0,range_);
  }

  /// \brief [l,r)に対して演算をした結果を返す
  /// \param l 範囲左端(lを含む)
  /// \param r 範囲右端(rを含まない)
  /// \return result

  VM GetResult(int l, int r){
    return GetRangeOperation(l, r, 0, 0, range_);
  }
};

// verify

class RSQTree:public LazySegmentTree<int64_t,int64_t>{
protected:

  int64_t MergeValue(const int64_t& a, const int64_t& b)override {
    return a+b;
  }
  int64_t MergeOperator(const int64_t& target,const int64_t& effector)override {
    if(effector==operator_identity_){
      return target;
    }else{
      return effector;
    }
  }
  int64_t Operate(const int64_t& val, const int64_t& opl)override {
    if(opl==operator_identity_){
      return val;
    }else{
      return opl;
    }
  }
  int64_t GetOperator(const int64_t& opl, const int n)override {
    return opl*(int64_t)n;
  }

public:
  RSQTree(int64_t n):LazySegmentTree(0,INT32_MAX,n){}

};


int main(void){
  int64_t n,q;
  cin>>n>>q;
  RSQTree tree(n+1);
  tree.Init(std::vector<int64_t>(n,0));
  for(int64_t i=0;i<q;i++){
    int64_t m;
    cin>>m;
    if(m==0){
      int64_t s,t,x;
      cin>>s>>t>>x;
      tree.Update(s,t+1,x);
    }else{
      int64_t s,t;
      cin>>s>>t;
      cout<< tree.GetResult(s, t + 1)<<endl;
    }
  }
}