Shelter Planning

In the mystical land of Gensokyo, the area known as Human Realm (人间之里) is considered the safest haven for humans. However, when abnormal phenomena (异变) occur, even this sanctuary is not immune to unexpected disasters. In such instances, a shelter must be built at an optimal location to minimize the inconvenience to the residents.

The Human Realm is abstracted as a one‐dimensional coordinate axis. There are n houses built on this axis, located at coordinates \(x_1, x_2, \dots, x_n\). The i-th house accommodates \(v_i\) residents.

When an abnormal event occurs, a contiguous range of houses (i.e. all houses whose coordinates lie in some interval) are affected. A shelter can then be built at any coordinate \(z\). The "inconvenience" of placing a shelter at \(z\) is defined as the sum of distances each affected resident has to travel, i.e. the sum \(\sum v_i \cdot |x_i - z|\) over all affected houses. (For example, if only house \(i\) is affected, then the inconvenience is \(v_i \cdot |x_i - z|\).)

Because the layout of the houses and the number of residents in each house can change over time, you need to process m operations. Each operation is one of the following two types:

• Query: 1 l r — This represents a hypothetical scenario where all houses whose coordinates lie in the interval \([l,r]\) are affected. You must determine the minimum possible inconvenience over all choices of \(z\) (i.e. the optimal shelter location). Note that this query does not permanently change anything.
• Update: 2 a b c — This updates the information of the a-th house: its coordinate is changed to \(b\) and the number of residents becomes \(c\). (Note that the index a refers to the house number, not the coordinate.)

Hint: For a set of affected houses with coordinates \(x_i\) and weights (number of residents) \(v_i\), the function \(\sum v_i |x_i - z|\) is minimized when \(z\) is chosen to be the weighted median of the \(x_i\). In other words, if you sort the affected houses by their coordinates and let the total weight be \(W\), then the optimal \(z\) is the smallest \(x_i\) for which the cumulative weight is at least \(\frac{W}{2}\) (or more precisely, at least \(\frac{W+1}{2}\) when dealing with integers).

inputFormat

The input begins with a line containing two integers \(n\) and \(m\) — the number of houses and the number of operations, respectively.

The second line contains \(n\) integers \(x_1, x_2, \dots, x_n\) where \(x_i\) is the coordinate of the i-th house.

The third line contains \(n\) integers \(v_1, v_2, \dots, v_n\) where \(v_i\) is the number of residents in the i-th house.

Each of the next \(m\) lines represents an operation and is in one of the following two formats:

• 1 l r for a query operation.
• 2 a b c for an update operation.

Note: In query operations, the affected houses are hypothetical and do not change the data for subsequent queries. Update operations permanently change the data for the specified house.

outputFormat

For each query operation (lines that start with 1), output a single line containing the minimum inconvenience value for that operation.

sample

5 5
1 3 6 10 15
2 1 3 1 2
1 2 10
2 3 7 2
1 2 10
1 1 20
1 8 12

7
7
35
0

</p>