题目背景

小C有一个整数序列，他需要对这个序列进行一系列复杂的操作，最后统计特定范围内的元素个数。这可难倒了他，快来帮帮他吧！

题目描述

小C有一个长度为 $n$ 的整数序列 $a_1, a_2, \cdots, a_n$，他需要处理 $Q$ 次操作，操作共分为以下两类：

1. 操作 1：包含一个非负整数 $x$ 和两个正整数 $s$ 和 $t$。对于所有大于或等于 $x$ 的元素，需要先将其加上 $s$，然后再乘以 $t$。即对于一个值为 $v$ 且满足 $v \geq x$ 的元素，在此操作后它变为：

   $$t(v + s)$$

2. 操作 2：包含一个非负整数 $x$ 和两个正整数 $s$ 和 $t$。对于所有小于或等于 $x$ 的元素，需要先将其减去 $s$，然后再除以 $t$，并向零截断。即对于一个值为 $v$ 且满足 $v \leq x$ 的元素，在此操作后它变为：

   $$\text{trunc}\left( \frac{v - s}{t} \right)$$

其中，$\text{trunc}(y)$ 表示向零截断 $y$ 得到的整数。“向零截断”意味着直接去掉小数部分，使结果向零靠近。例如，截断 $3.5$ 得到 $3$，而截断 $-2.8$ 得到 $-2$。

在依次应用了 $Q$ 次操作之后，请问数组中有多少元素在 $L$ 到 $R$ 的范围内（即满足 $L \leq a_i \leq R$）？

输入格式

第一行包含四个整数 $n, Q, L, R$，分别表示数组的长度、操作的次数、以及需要统计的范围 $[L, R]$。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示数组 $a$ 的初始状态。

接下来 $Q$ 行，每行包含四个整数 $q_i, x_i, s_i, t_i$，表示第 $i$ 次操作的类型和参数。

输出格式

输出一行一个整数，表示在处理完所有操作后，数组中满足 $L \leq a_i \leq R$ 的元素个数。

样例 #1

样例输入 #1

3 3 3 10
1 -2 3
1 2 2 3
2 20 1 3
2 1 20 5

样例输出 #1

1

样例 #2

样例输入 #2

10 10 -344 949304959823841996
-3322545 4925407 1739804 2427239 -5261662 -5616033 -8030330 6212172 8586142 5029512
1 16392506 3 3
1 32437 46 3
1 27923410 74 5
1 579357460 33 5
2 2620867453 17 1
2 3538613740 16 1
1 3046695459 20 3
1 2820482772 12 2
1 3554938917 20 5
2 91948363102 2 1

样例输出 #2

6

数据范围与提示

对于全部测试数据，保证：

• $1 \leq n, Q \leq 2 \times 10^5$
• $-2^{63} < L \leq R < 2^{63}$
• $0 \leq |a_i| \leq 10^9$
• $q_i \in \{1, 2\}$
• $0 \leq x_i < 2^{63}$
• $1 \leq s_i, t_i \leq 10^9$
• 在处理操作的过程中，数组中任何元素的绝对值不会超过 $2^{63}$。

部分测试点约定：

• 对于 $40\%$ 的测试数据，满足 $n, Q \leq 5000$；
• 另有 $30\%$ 的测试数据，满足 $q_i = 1$（即只有操作 1）。