Problem: B: AddMulSubDiv

Problem Statement

You have an array A of N integers. A_i denotes the i-th element of A.

You have to process one of the following queries Q times:

* Query 1: The query consists of non-negative integer x, and two positive integers s, t. For all the elements greater than or equal to x in A, you have to add s to the elements, and then multiply them by t. That is, an element with v (v \geq x) becomes t(v + s) after this query.


* Query 2: The query consists of non-negative integer x, and two positive integers s, t. For all the elements less than or equal to x in A, you have to subtract s from the elements, and then divide them by t. If the result is not an integer, you truncate it towards zero. That is, an element with v (v \leq x) becomes $\mathrm{trunc}$ ( \frac{v - s}{t} ) after this query, where $\mathrm{trunc}$ ( y ) is the integer obtained by truncating y towards zero.


* "Truncating towards zero" means converting a decimal number to an integer so that if x = 0.0 then 0 , otherwise an integer whose absolute value is the maximum integer no more than |x| and whose sign is same as x. For example, truncating 3.5 towards zero is 3, and truncating -2.8 towards zero is -2.



After applying Q queries one by one, how many elements in A are no less than L and no more than R?

Input


N Q L R
A_1 A_2 ... A_N
q_1 x_1 s_1 t_1
:
q_Q x_Q s_Q t_Q


* The first line contains four integers N, Q, L, and R. N is the number of elements in an integer array A, Q is the number of queries, and L and R specify the range of integers you want to count within after the queries.
* The second line consists of N integers, the i-th of which is the i-th element of A.
* The following Q lines represent information of queries. The j-th line of them corresponds to the j-th query and consists of four integers q_j, x_j, s_j, and t_j. Here, q_j = 1 stands for the j-th query is Query 1, and q_j = 2 stands for the j-th query is Query 2. x_j, s_j, and t_j are parameters used for the j-th query.



Constraints

* 1 \leq N \leq 2 \times 10^5
* 1 \leq Q \leq 2 \times 10^5
* -2^{63} < L \leq R < 2^{63}
* 0 \leq |A_i| \leq 10^9
* q_j \in \\{ 1, 2 \\}
* 0 \leq x_j < 2^{63}
* 1 \leq s_j, t_j \leq 10^9
* Inputs consist only of integers.
* The absolute value of any element in the array dosen't exceed 2^{63} at any point during query processing.



Output

Output the number of elements in A that are no less than L and no more than R after processing all given queries in one line.

Sample Input 1


3 3 3 10
1 -2 3
1 2 2 3
2 20 1 3
2 1 20 5


Output for Sample Input 1


1





Example

Input

3 3 3 10
1 -2 3
1 2 2 3
2 20 1 3
2 1 20 5


Output

1

Solution (in CPP):

Solution:
#include <cstdio>
#include <climits>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

__int128 div_floor(__int128 x, __int128 y) {
  if (x >= 0) return x / y;
  // x < 0
  if (x % y == 0) return x / y;
  return x/y - 1;
}

__int128 div_ceil(__int128 x, __int128 y) {
  if (x >= 0) return (__int128(x)+y-1) / y;
  if (x % y == 0) return x / y;
  return x/y + 1;
}

int main(){
  long long N, q, L0, R0;
  cin >> N >> q >> L0 >> R0;
  __int128 L = L0;
  __int128 R = R0;
  vector<long long> A(N);
  for(int i = 0; i < N; ++i){
    cin >> A[i];
  }
  //fprintf(stderr, "%lld %lld %lld %lld (NqLR)\n", N, q, L, R);
  vector<long long> Q(q), X(q), S(q), T(q);
  for(int i = 0; i < q; ++i){
    cin >> Q[i] >> X[i] >> S[i] >> T[i];
  }
  for(int i = q-1; i >= 0; --i){
    //fprintf(stderr, "%lld %lld %lld %lld (qxst)\n", Q[i], X[i], S[i], T[i]);
    if(Q[i] == 1){
      // R = R/T[i] - S[i];
      // L = (L+T[i]-1)/T[i] - S[i];
      __int128 R_ = div_floor(R, T[i]) - S[i];
      __int128 L_ = div_ceil(L, T[i]) - S[i];
      //fprintf(stderr,"R_ = %lld, L_ = %lld, X[i] = %lld\n",R_,L_, X[i]);
      if(R_ > X[i]) R = R_;
      else if(R > X[i]) R = X[i];
      if(L_ > X[i]) L = L_;
      else if(L > X[i]) L = X[i];
    }else{
      __int128 R_ = R*T[i];
      __int128 L_ = L*T[i];
      if(R_ >= 0) R_ += T[i]-1;
      if(L_ <= 0) L_ -= T[i]-1;
      R_ += S[i];
      L_ += S[i];
      if(R_ < X[i]) R = R_;
      else if(R < X[i]) R = X[i];
      if(L_ < X[i]) L = L_;
      else if(L < X[i]) L = X[i];
    }

    R = min<__int128>(R, LLONG_MAX);
    L = max<__int128>(L, LLONG_MIN+1);
    //cerr << L << " " << R << endl;
  }
  //cerr << L << " " << R << endl;
  int ans = 0;
  for(auto a : A){
    if(a >= L and a <= R)
      ++ans;
  }
  cout << ans << endl;
}