Problem Description

You are playing a “multi-character romance simulation game” and are trying to romance $N$ characters at the same time. For the $i$-th character, there are two key values:

• $a_i$: her tolerance toward you;
• $b_i$: her expectation of you.

Initially, the status of all characters is given and identical: $a_i = A, b_i = B$ ($1\le i \le N$).

Next, you will perform $Q$ actions. Each action is one of the following three types:

• $1\ r\ x$: you “mess up collectively” with the first $r$ characters, causing their tolerance to decrease.

  That is, for all $i$ ($1\leq i\leq r$), $a_{i} \gets \min \{ a_{i}, x \}$.

• $2\ l\ x$: you give gifts to the $l$-th through the $N$-th characters, causing their expectations to increase.

  That is, for all $i$ ($l\leq i \leq N$), $b_{i} \gets \max \{ b_{i}, x \}$.

• $3\ l\ r$: query the “Shura Index” of the $l$-th through the $r$-th characters.

  The “Shura Index” is defined as $\sum_{i=l}^r |a_{i}-b_{i}|$.

Input Format

The first line contains three integers $N, A$ and $B$ ($1\le N\le 5 \times 10^5, -10^9\le A,B\le 10^9$), separated by a single space, representing the number of characters, the initial tolerance value, and the initial expectation value.

The second line contains an integer $Q$ ($1\le Q\le 5 \times 10^5$), indicating the number of actions.

The next $Q$ lines each contain three integers separated by a single space. These three integers correspond to one of the following cases, representing one action:

• $1\ r\ x$ ($1\le r\le N, -10^9 \le x \le 10^9$), meaning that for all $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$), meaning that for all $i$ ($l\leq i \leq N$), $b_{i} \gets \max \{ b_{i}, x \}$.
• $3\ l\ r$ ($1\le l\le r\le N$), meaning to query the “Shura Index” $\sum_{i=l}^r |a_{i}-b_{i}|$ for the $l$-th through the $r$-th characters.

Output Format

For each action that queries the “Shura Index”, output one line containing one integer, representing the value of the “Shura Index”.

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

Hint

Translated by ChatGPT 5