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<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
#define inf (int)(1e9+7)
#define abs(x) (x >= 0 ? x : -(x))
#define ceil(a, b) a / b + !!(a % b)
template<typename T1, typename T2> inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }
ll pow(ll a, int b) { return b ? pow(a * a, b / 2) * (b % 2 ? a : 1) : 1; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }



int n, Q;
ll l, r;
vector<pair<pair<int, ll>, pii> > v;
vector<int> a;

ll calc(ll A) {
    for (auto &p: v) {
        int q, s, t;
        ll x;
        tie(q, x) = p.first;
        tie(s, t) = p.second;
        if (q == 1) {
            if (A < x) continue;
            A = 1LL * t * (A + s);
        } else {
            if (A > x) continue;
            A = (A - s) / t;
        }
    }
    return A;
}

void small() {
    ll A = a[0];
    
    A = calc(A);
    
    if (l <= A && A <= r) cout << 1 << '\n';
    else cout << 0 << '\n';
}

int main() {
    cin >> n >> Q >> l >> r;
    
    a.resize(n);
    rep(i, n) cin >> a[i];
    sort(all(a));
    
    
    rep(i, Q) {
        int q, s, t; ll x;
        cin >> q >> x >> s >> t;
        v.eb(make_pair(make_pair(q, x), pii(s, t)));
    }
    
    if (n == 1) {
        small();
        return 0;
    }
    
    // l
    int L = -1, R = n - 1;
    while (true) {
        int mid = (L + R) / 2;
        ll A = a[mid];
        A = calc(A);
        
        if (A < l) {
            L = mid;
        } else {
            R = mid;
        }
        if (L + 1 == R) break;
    }
    int tmpR = R;
    
    // r
    L = 0; R = n;
    while (true) {
        int mid = (L + R) / 2;
        ll A = a[mid];
        A = calc(A);
        
        if (A > r) {
            R = mid;
        } else {
            L = mid;
        }
        if (L + 1 == R) break;
    }
    // cout << L << " " << tmpR << '\n';
    
    if (L == tmpR) {
        ll A = a[L];
        A = calc(A);
        
        if (l <= A && A <= r) cout << 1 << endl;
        else cout << 0 << endl;
        return 0;
    }
    
    cout << L - tmpR + 1 << endl;
}