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<iostream>
#include<vector>
#include<algorithm>
#include<utility>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define int long long
typedef long long ll;


int N, Q,_L,_R;
vector<int> a;
vector<__int128_t> x;
vector<__int128_t> s;
vector<__int128_t> t;
__int128_t B;
__int128_t calc(__int128_t X){
    for(int i=0;i<Q;i++){
        if(a[i] == 1)
        {
            if(X >= x[i]){
                X = (X + s[i]) * t[i];
            }
        }else{
            if(X <= x[i]){
                X = (X - s[i]) / t[i];
            }
        }
        X = min(X, B);
        X = max(X, -B);
    }
    return X;
}

signed main(){


    //cerr << (int) ( (__int128_t)-5 / 3) << endl;

    cin >> N >> Q >> _L >> _R;
    __int128_t L, R;
    L = _L;
    R = _R;
    vector<__int128_t> A(N);

    for(int i=0;i<N;i++){
        int a;
        cin >> a;
        A[i] = a;
    }    
    sort(A.begin(),A.end());
    a.resize(Q);
    x.resize(Q);
    s.resize(Q);
    t.resize(Q);
    for(int i=0;i<Q;i++){
        int _x,_s,_t;
        cin >> a[i] >> _x >> _s >> _t;
        x[i] = _x;
        s[i] = _s;
        t[i] = _t;
    }

    B = ((int)1 << 62);
    B *= 4;
    //cerr << (int)(B / 8) << endl; 
    __int128_t lo, hi;

    lo = (__int128_t)-1e10;
    hi = (__int128_t)1e10;

    while(hi - lo > 1){
        __int128_t m = (hi + lo) / 2;
        __int128_t t = calc(m);
        if(t >= L){
            hi = m;
        }else{
            lo = m;
        }
    }

    __int128_t LL = hi;

    
    lo = (__int128_t)-1e10;
    hi = (__int128_t)1e10;

    while(hi - lo > 1){
        __int128_t m = (hi + lo) / 2;
        __int128_t t = calc(m);

        //cerr << (int)m << " " << (int)t << " " << (int)R << endl;
        if(t <= R){
            lo = m;
        }else{
          //  cerr << "A"<<endl;
            hi = m;
        }
    }

    __int128_t RR = lo;
    //cerr << (int)LL <<" " << (int)RR << endl;
    int res = upper_bound(A.begin(), A.end(), RR) - lower_bound(A.begin(), A.end(), LL);
    cout << res << endl;
    
    return 0;
}