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

Source: aizu | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
import bisect
(n, Q, L, R) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
p = []
for i in range(Q):
	p.append(tuple(map(int, input().split())))

def f(z):
	for (q, x, s, t) in p:
		if q == 1:
			if z >= x:
				z = t * (z + s)
		elif z <= x:
			if z - s < 0:
				z = -(abs(z - s) // t)
			else:
				z = (z - s) // t
	return z
ng = pow(2, 63)
ok = -ng
for i in range(100):
	mid = (ok + ng) // 2
	if f(mid) <= R:
		ok = mid
	else:
		ng = mid
right = ok
ok = pow(2, 63)
ng = -ok
for i in range(100):
	mid = (ok + ng) // 2
	if f(mid) >= L:
		ok = mid
	else:
		ng = mid
left = ok
k1 = bisect.bisect_left(a, left)
k2 = bisect.bisect_right(a, right)
print(k2 - k1)


from collections import defaultdict, deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def I():
	return int(sys.stdin.readline())

def LS():
	return [list(x) for x in sys.stdin.readline().split()]

def S():
	res = list(sys.stdin.readline())
	if res[-1] == '\n':
		return res[:-1]
	return res

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]
sys.setrecursionlimit(1000000)
mod = 1000000007

def A():
	n = I()
	a = LI()
	s = sum([i % 2 for i in a])
	if s in (0, n):
		print(0)
	else:
		print(n - 2 + s % 2)
	return

def B():
	(n, Q, L, R) = LI()
	a = LI()
	a.sort()
	query = LIR(Q)
	l = -1
	r = n
	while r - l > 1:
		m = l + r >> 1
		am = a[m]
		for (q, x, s, t) in query:
			if q == 1:
				if am < x:
					continue
				am += s
				am *= t
			else:
				if am > x:
					continue
				am -= s
				if am < 0:
					am = -(-am // t)
				else:
					am //= t
		if am < L:
			l = m
		else:
			r = m
	left = r
	l = 0
	r = n
	while r - l > 1:
		m = l + r >> 1
		am = a[m]
		for (q, x, s, t) in query:
			if q == 1:
				if am < x:
					continue
				am += s
				am *= t
			else:
				if am > x:
					continue
				am -= s
				if am < 0:
					am = -(-am // t)
				else:
					am //= t
		if am <= R:
			l = m
		else:
			r = m
	print(r - left)
	return

def C():
	n = I()
	return

def D():
	n = I()
	return

def E():
	n = I()
	return

def F():
	n = I()
	return

def G():
	n = I()
	return

def H():
	n = I()
	return

def I_():
	n = I()
	return

def J():
	n = I()
	return
B()