# 饼干交换大会

- 参考时间限制：0.5 秒（参考环境：[评测环境与性能](../../../docs/评测环境与性能.md)；仅供预估）
- 实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 2 倍，按 0.5 秒的倍数向上取整；若平台仅支持更粗的粒度，再向上取整到平台可设置值。
- 内存限制：1024 MB

## 背景故事

茶会上的每位来宾都带了饼干，也报了自己最多能吃多少块。主持人宣布：“既然叫交换大会，就别坐下来把自己带的那盒吃完。”

于是，每块饼干只能从主人手中直接交给另一位来宾，不能转手，更不能绕一圈回到自己嘴里。来宾们不时修改携带数量和食量，主持人还会选一段相邻座位，估算这几个人内部最多能分掉多少块饼干。

这些都是纸上排练。每次估算结束，饼干一块也不会少。

(本故事由GPT-6 Astra重写)

## 形式化问题描述

有 $n$ 个参与者，依次编号为 $1$ 至 $n$ . 参与者 $i$ 的接收上限为 $d_i$（Demand），提供上限为 $s_i$（Supply），单位均为物品个数。物品只能从提供者直接交给接收者，且二者必须不同。两项上限都可以不全部使用。

按顺序处理 $m$ 次操作，每次属于以下三类之一：

1. `1 x d` ：令 $d_x=d$ .
2. `2 x s` ：令 $s_x=s$ .
3. `3 l r` ：只允许编号在 $[l,r]$ 内的参与者互相提供物品，求最大交付总量。

形式化地，对当前询问的每对不同参与者 $i,j$ ，选择非负整数 $f_{ij}$ 表示从 $i$ 交付给 $j$ 的物品数。要求每个提供者满足 $\sum_{j\ne i}f_{ij}\le s_i$ ，每个接收者满足 $\sum_{i\ne j}f_{ij}\le d_j$ ，并最大化 $\sum_{i\ne j}f_{ij}$ . 这里所有下标及求和均限定在 $[l,r]$ 内。

同一参与者可以同时提供和接收，两个不同参与者也可以互相提供。询问不消耗任何数量；只有前两类操作会修改状态。

## 输入格式

第一行两个整数 $n,m$ .

第二行 $2n$ 个整数 $d_1,s_1,d_2,s_2,\ldots,d_n,s_n$ .

接下来 $m$ 行，每行三个整数，表示一条操作。

## 输出格式

对每个第三类操作输出一行一个整数。若没有第三类操作，则不输出任何内容。

## 样例 1

### 输入

```text
3 5
1 1 2 2 2 3
3 1 3
3 1 2
1 1 2
3 1 3
3 1 2
```

### 输出

```text
5
2
6
3
```

### 解释

第一次询问可以交付 $5$ 块饼干：参与者 $1$ 向 $2$ 交付一块，参与者 $2$ 向 $3$ 交付两块，参与者 $3$ 分别向 $1$ 和 $2$ 各交付一块。

修改后，参与者 $1$ 的接收上限变成 $2$ ，两个范围的最大交付量分别增为 $6$ 和 $3$ .

## 样例 2

### 输入

```text
2 4
100 100 1 1
3 1 2
3 1 1
1 2 100
3 1 2
```

### 输出

```text
2
0
101
```

### 解释

第一次询问只有两人，双方各向对方交付一块饼干，总量为 $2$ . 单人范围不能向自己交付，答案为 $0$ .

修改后，参与者 $1$ 可以向 $2$ 交付 $100$ 块，参与者 $2$ 仍可以向 $1$ 交付一块，因此最后一次询问的答案为 $101$ .

## 数据范围与保证

- $1\le n,m\le300\,000$ .
- $0\le d_i,s_i,d,s\le1\,000\,000\,000$ ，均为整数。
- 修改操作满足 $1\le x\le n$ .
- 询问满足 $1\le l\le r\le n$ .

### 数据分组

| 分值比例 | 额外条件 |
| --- | --- |
| 10% | $n,m\le10$ ，所有数量不超过 $50$ |
| 10% | $n,m\le100$ |
| 20% | $n,m\le300$ |
| 20% | $n,m\le3\,000$ |
| 20% | $n,m\le50\,000$ |
| 20% | 无额外条件 |