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:

#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#endif
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>
#include <cmath>

using std::cout;
using std::cin;
using std::endl;


#define __int128 int64_t

__int128 A[200100];
int qtype[200100];
__int128 qx[200100];
__int128 qs[200100];
__int128 qt[200100];

const int64_t INF = 2000000000;
const int64_t INFINF = (((uint64_t)(1) << 63) - 1);

int main()
{

	int N, Q;
	__int128 L, R;

	cin >> N >> Q >> L >> R;

	for (int i = 0; i < N; ++i) {
		cin >> A[i];
	}

	for (int i = 0; i < Q; ++i) {
		cin >> qtype[i] >> qx[i] >> qs[i] >> qt[i];
	}

	//L以上になる条件
	int64_t ok_range = INF, ng_range = -INF;
	while (std::abs(ok_range - ng_range) > 1) {
		auto mid = (ok_range + ng_range) / 2;

		auto nowpos = mid;
		for (int i = 0; i < Q; ++i) {
			if (qtype[i] == 1) {
				if (qx[i] <= nowpos) {
					nowpos = qt[i] * (nowpos + qs[i]);
				}
			}
			else {
				if (nowpos <= qx[i]) {
					nowpos = (nowpos - qs[i])/ qt[i];
				}
			}
		}
		if (L <= nowpos) {
			ok_range = mid;
		}
		else {
			ng_range = mid;
		}
	}
	auto LLL = ok_range;

	//R以下になる条件
	ok_range = -INF, ng_range = INF;
	while (std::abs(ok_range - ng_range) > 1) {
		auto mid = (ok_range + ng_range) / 2;

		auto nowpos = mid;
		for (int i = 0; i < Q; ++i) {
			if (qtype[i] == 1) {
				if (qx[i] <= nowpos) {
					nowpos = qt[i] * (nowpos + qs[i]);
				}
			}
			else {
				if (nowpos <= qx[i]) {
					nowpos = (nowpos - qs[i]) / qt[i];
				}
			}
		}
		if (nowpos <= R) {
			ok_range = mid;
		}
		else {
			ng_range = mid;
		}
	}
	auto RRR = ok_range;

	int count = 0;
	for (int i = 0; i < N; ++i) {
		if (LLL <= A[i] && A[i] <= RRR) {
			++count;
		}
	}
	cout << count << endl;
}