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

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

2. 操作 $q=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$：表示数组的长度 $n$，查询次数 $Q$，以及你需要统计的范围 $[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$。

测试样例

Input 1

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

Output 1

1

Input 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

Output 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 \le 5000$
• 另有 $30\%$ 的测试数据，满足 $q_i = 1$