题目描述

你正在一款「多角色恋爱养成游戏」中，同时尝试攻略 $N$ 位角色。对第 $i$ 位角色来说，有两个关键数值：

• $a_i$：她对你的容忍度；
• $b_i$：她对你的期待值。

初始时，所有角色的状态给定且相同：$a_i = A,b_i = B$（$1\le i \le N$）。

接下来你会进行 $Q$ 次行动，行动为如下三种之一：

• $1\ r\ x$，你在前 $r$ 位角色那里「集体翻车」，导致她们的容忍度下降。

  即对于所有的 $i$（$1\leq i\leq r$），$a_{i} \gets \min \{ a_{i}, x \}$。

• $2\ l\ x$，你给第 $l$ 位到第 $N$ 位角色送礼物，导致她们的期待值提高。

  即对于所有的 $i$（$l\leq i \leq N$），$b_{i} \gets \max \{ b_{i}, x \}$。

• $3\ l\ r$，查询第 $l$ 位到第 $r$ 位角色的「修罗指数」。

  「修罗指数」定义为 $\sum_{i=l}^r |a_{i}-b_{i}|$。

输入格式

输入的第一行，包含三个整数 $N,A$ 和 $B$（$1\le N\le 5 \times 10^5,-10^9\le A,B\le 10^9$），用一个空格分隔，分别表示角色个数、容忍度初始值和期待值初始值。

第二行包含一个整数 $Q$（$1\le Q\le 5 \times 10^5$），表示行动次数。

接下来 $Q$ 行，每行三个整数，用一个空格分隔。这三个整数为如下三种情况中的一种，表示一次行动：

• $1\ r\ x$（$1\le r\le N, -10^9 \le x \le 10^9$），表示对于所有的 $i$（$1\leq i\leq r$），$a_{i} \gets \min \{ a_{i}, x \}$。
• $2\ l\ x$（$1\le l\le N, -10^9 \le x \le 10^9$），表示对于所有的 $i$（$l\leq i \leq N$），$b_{i} \gets \max \{ b_{i}, x \}$。
• $3\ l\ r$（$1\le l\le r\le N$），表示查询第 $l$ 位到第 $r$ 位角色的「修罗指数」$\sum_{i=l}^r |a_{i}-b_{i}|$。

输出格式

对于每个查询「修罗指数」的行动，输出一行，包含一个整数，表示「修罗指数」的值。

11 38 11
21
3 4 7
2 3 23
3 2 6
2 9 29
3 3 4
1 11 13
3 2 7
1 1 38
3 1 8
1 9 11
3 2 8
1 11 33
3 1 10
2 9 25
3 2 10
1 10 31
3 1 3
1 3 39
3 3 8
2 7 21
3 5 9

108
87
30
52
64
72
106
106
12
72
66