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<string>
#include<vector>
#include<algorithm>

using namespace std;

#define int long long

#define q first.first
#define x first.second
#define s second.first
#define t second.second

vector<int> A, B;
vector<pair<pair<int,int>,pair<int,int>>> query;
int N, Q, L, R;

int check(int num){
	if(num < 0) return (int)(1ull<<63);
	if(num >= N) return (int)(~(1ull<<63));
	
	int v = A[num];
	
	for(int i = 0; i < Q; i++){
		if(query[i].q == 1){
			if(query[i].x <= v){
				v = query[i].t*(query[i].s+v);
			}
		} else if(query[i].q == 2){
			if(query[i].x >= v){
				v = (v-query[i].s)/query[i].t;
			}
			
		}
		// cout<<"v = "<<v<<endl;
	}
	
	return v;
}

signed main(){

	int al, ar;
	// cout<<(int)(1ull<<63)<<endl;
	// cout<<(int)(~(1ull<<63))<<endl;
	// cout<<(int)(-2.8)<<endl;
	// cout<<(int)(-3/2)<<endl;
	
	cin>>N>>Q>>L>>R;
	
	A.assign(N, 0);
	query.assign(Q, {});
	
	for(int i = 0; i < N; i++){
		cin>>A[i];
	}
	
	B = A;
	
	sort(A.begin(), A.end());
	A.erase(unique(A.begin(), A.end()), A.end());
	
	// for(){
	// }
	for(int i = 0; i < Q; i++){
		
		cin>>query[i].q>>query[i].x>>query[i].s>>query[i].t;
	}
	
	// for(int i = 0; i < N; i++){
		// cout<<"i = "<<i<<" "<<check(i)<<endl;
	// }
	N = A.size();
	
	int l = -1, r = N+1, m;
	
	while(l + 1 < r){
		m = (l+r)/2;
		
		// cout<<l<<" "<<m<<" "<<r<<endl;
		// string hogehoge;
		// cin>>hogehoge;
		
		if(check(m) > R){
			r = m;
		} else {
			l = m;
		}
	}
	
	ar = l;
	
	l = -1, r = N+1, m;
	
	while(l + 1 < r){
		m = (l+r)/2;
		
		if(check(m) >= L){
			r = m;
		} else {
			l = m;
		}
	}
	
	al = r;
	
	// cout<<ar-al<<endl;
	
	int con = 0;
	
	//cout<<"N = "<<N<<endl;
	for(int i = 0; i < B.size(); i++){// cout<<i<<endl;
		//cout<<ar<<" "<<al<<endl;
		
		if(ar == -1 || al == N){ //cout<<"D"<<endl;
		} else if(ar == N && al == -1){ cout<<"A"<<endl;
			con++;
		} else if(A[al] <= B[i] && ar == N){ //cout<<"B"<<endl;
			con++;
		} else if(al == -1 && B[i] <= A[ar]){ //cout<<"C"<<endl;
			con++;
		} else if(A[al] <= B[i] && B[i] <= A[ar]){
			//cout<<A[al]<<" <= "<<B[i]<<" <= "<<A[ar]<<endl;
			con++;
		} else {
			//cout<<"E"<<endl;
			//cout<<A[al]<<" <= "<<B[i]<<" <= "<<A[ar]<<endl;
		}
	}
	cout<<con<<endl;
	return 0;
}